Selma Belhadj Amor

Samir M Perlaza
email: samir.perlaza@inria.fr

Fundamental Limits of Simultaneous Energy and Information Transmission

In this paper, existing results regarding the fundamental limits of simultaneous energy and information transmission in wireless networks are reviewed. In point-to-point channels, the fundamental limits on the information rate given a minimum energy rate constraint are fully characterized by the notion of information-energy capacity function introduced by Varshney in 2008. In a centralized multi-user channel, the fundamental limits on the information rates given a minimum energy rate constraint are described by the notion of informationenergy capacity region introduced by Fouladgar and Simeone in 2012. Alternatively, in a decentralized multi-user channel, the authors have recently introduced the notion of informationenergy Nash region to describe these fundamental limits. All these fundamental limits reveal the intrinsic trade-off between the two conflicting tasks of information and energy transmission.

I. INTRODUCTION

Efficient energy utilization is among the main challenges of future communication networks in order to extend their lifetime and to reduce operating costs. Networks rely generally on battery-dependent devices. In some cases, such batterydependency is relevant to such an extent that the battery lifetime is the network lifetime as well. This is typically the case of wireless sensor networks. Once sensors are deployed, their batteries become generally inaccessible and cannot be recharged or replaced. Within this context, wireless energy transmission becomes an alternative to eliminate the need for in situ battery recharging. Nonetheless, for decades, the traditional engineering perspective was to design separately information transmission systems and energy transmission systems. However, this approach has been shown to be suboptimal [START_REF] Varshney | On energy/information cross-layer architectures[END_REF] due to the fact that a radio frequency (RF) signal carries both energy and information. From this standpoint, a variety of modern wireless systems and proposals question the conventional separation approach and suggest that RF signals can be simultaneously used for information and energy transmission [START_REF] Bi | Wireless powered communication: opportunities and challenges[END_REF].

Typical examples of communications technologies already exploiting this principle are radio frequency identification (RFID) devices and power line communications. Beyond the existing applications, simultaneous energy and information transmission (SEIT) appears as a promising technology for a variety of emerging applications including low-power shortrange communication systems, sensor networks, machine-tomachine networks and body-area networks, among others [START_REF] Krikidis | Simultaneous wireless information and power transfer in modern communication systems[END_REF]. When a communication system involves sending energy along with information, it should be designed to simultaneously meet two goals: (a) To reliably transmit energy at a given rate with a sufficiently small probability of energy outage; and (b) To reliably transmit information at a given rate with a sufficiently small probability of error. However, these two tasks are usually conflicting. In fact, from a global perspective, imposing a constraint on an energy rate impacts deeply the overall performance of the network components. An object of central interest in this perspective is the informationenergy capacity region which is the set of all informationenergy rate tuples at which reliable transmission of information/energy is possible. The achievability of such tuples is subject to the existence of central controller that determines a network operating point and imposes the transmit or receive configuration that should be adopted by each network component. However, in a decentralized network, each network component is an autonomous decision maker that aims to maximize its own individual reward by appropriately choosing a particular transmit or receive configuration. From this perspective, the individual choice of each component does not necessarily achieve the capacity of the network. Hence, only the information-energy rate tuples that are stable can be possible asymptotic operating points in a decentralized network. Stability can be understood in the sense of Nash [START_REF] Nash | Equilibrium points in n-person games[END_REF]. That is, none of the network components is able to increase its own reward by unilaterally changing its own configuration. This paper reviews the existing results regarding the fundamental limits of SEIT in wireless networks. These fundamental limits are characterized in terms of informationenergy capacity function introduced by Varshney [START_REF] Varshney | Transporting information and energy simultaneously[END_REF] in pointto-point channels and in terms of information-energy capacity region introduced by Fouladgar and Simeone [START_REF] Fouladgar | On the transfer of information and energy in multi-user systems[END_REF] in centralized multi-user channels. Alternatively, in a decentralized multiuser channel, these fundamental limits are described by the information-energy Nash region recently introduced by the authors [START_REF] Belhadj Amor | Decentralized simultaneous energy and information transmission in multiple access channels[END_REF]. The main focus will be on the Gaussian multiaccess channel as a basic setup to capture the key aspects of the intrinsic information-energy trade-off in multi-user channels. However, most of the results continue to hold for more general network structures.

II. POINT-TO-POINT INFORMATION-ENERGY TRADE-OFF

In a point-to-point communication, information and energy transmission are subject to a trade-off between the information rate (bits per channel use) and the energy rate (energy units per channel use). This is evidenced for instance in the constraints induced by the choice of a given modulation [START_REF] Popovski | Interactive joint transfer of energy and information[END_REF]. Consider the transmission of a 4-PAM signal over a point-to-point channel in the alphabet {-2, -1, 1, 2}. If there is no received energy rate constraint, one can clearly convey up to 2 bits/ch.use by using all symbols of the constellation. However, if one requires the received energy rate to be for instance the maximum possible, the maximum transferable information rate is 1 bit/ch.use using only the most energetic symbols.

A. Discrete Memoryless Channels

A discrete memoryless channel (DMC) with energy harvester (EH) is characterized by a finite input alphabet X , two finite output alphabets Y and S, and a conditional probability distribution P Y S|X . Let n denote the transmission blocklength. At each time t ∈ {1, . . . , n}, if the input symbol x t ∈ X is transmitted, the probability of observing the channel output y t ∈ Y at the receiver and the additional output s t ∈ S at the EH is P Y S|X (y t , s t |x t ). In the following, there is no particular assumption on the joint distribution P Y S .

Within this context, two main tasks are to be simultaneously accomplished: information transmission and energy transmission.

1) Information Transmission: The goal of information transmission is that, over n channel uses, the transmitter conveys a message M to the receiver at rate R bits per channel use. The message M is uniformly distributed over the set M {1, . . . , 2 nR }. The channel input at time t is

X t = ϕ (n) t (M ), t ∈ {1, . . . , n}, (1)
for some encoding function ϕ

(n) t of the form ϕ (n) t : M → R.
The receiver observes the random sequence Y n and uses it to estimate the message M by means of an appropriate decoding rule

M (n) = Φ (n) (Y n ) of the form Φ (n) : Y n → M.
The average probability of error is given by

P (n) error (R) Pr( M (n) = M ). (2)
2) Energy Transmission: At each time t, the energy that can be harvested from the output letter s t is given by ω(s t ) for a given energy function ω : S → R + . For the n-length sequence s n , the harvested energy is ω(s n ) = n t=1 ω(s t ) (Note that the harvested energy can also be written as a function of the input sequence). The expected energy rate (in energy-units per channel use) at the EH is given by

B (n) 1 n n t=1 E S [ω(S t )]. (3)
The goal of energy transmission is to guarantee that the expected energy rate B (n) is not less than a given target energy transmission rate B satisfying 0 < B B. Here B is the maximum feasible energy rate. The probability of energy outage is defined as follows:

P (n) outage (B) = Pr B (n) < B -, (4)
for some > 0 arbitrarily small.

3) Simultaneous Energy and Information Transmission:

The DMC is said to operate at the information-energy rate pair (R, B) ∈ R 2 + when the transmitter and the receiver use a transmit-receive configuration such that: (i) information transmission occurs at rate R with probability of error arbitrarily close to zero; and (ii) energy transmission occurs at a rate not smaller than B with energy-outage probability arbitrarily close zero. Under these conditions, the information-energy rate pair (R, B) is said to be achievable.

Definition 1 (Achievable Information-Energy Rates). The (R, B) ∈ R 2
+ is achievable if there exists a sequence of encoding and decoding functions {ϕ

(n) t } n t=1 , Φ (n) ∞
n=1 such that both the average error probability and the energy-outage probability tend to zero as the blocklength n tends to infinity. That is,

lim sup n→∞ P (n) error (R) =0, and (5)
lim sup n→∞ P (n) outage (B)=0. (6)
Often, increasing the energy rate implies decreasing the information rate and vice versa. This trade-off is accurately modeled by the notion of information-energy capacity function. The goal is set to maximize the information rate under a minimum received energy rate constraint.

Definition 2 (Information-Energy Capacity Function). Let b ∈ [0, B] denote the minimum energy rate that must be guaranteed at the input of the EH. For each blocklength n, define the function C (n) (b) as follows:

C (n) (b) max X n :B (n) b I(X n ; Y n ), (7)
where I(X n ; Y n ) denotes the mutual information between X n and Y n and the maximization is over all the length-n input sequences X n for which the expected energy rate B (n) is not smaller than b. The information-energy capacity function for a minimum energy rate b is defined as

C(b) lim sup n→∞ 1 n C (n) (b). (8)
Theorem 1 (Information Capacity Under Minimum Energy Rate (Theorem 1 in [START_REF] Varshney | Transporting information and energy simultaneously[END_REF])). The supremum over all achievable information rates in the DMC under a minimum energy rate b in energy-units per channel use is given by C(b) in bits per channel use.

4) Examples:

This subsection reviews some closed-form expressions (provided in [START_REF] Varshney | Transporting information and energy simultaneously[END_REF]) of the information-energy capacity function to better illustrate the optimal trade-offs between information and energy rates in the considered point-to-point channels. Three binary channels are considered for the special case in which the receiver and the EH observe the same output sequence, i.e., at each time t, S t = Y t . Thus, the channel law reduces to P Y |X .

In a noiseless binary channel, the information-energy capacity function for a minimum energy rate b is

C(b) = 1, if 0 b 1 2 , H 2 (b), if 1 2 b 1, (9)
where H 2 (•) is the binary entropy function. For any 0 b 1 2 the energy rate constraint is vacuous and equiprobable inputs achieve capacity. However, when 1 2 b 1, the capacityachieving distribution is Bernouilli with parameter b. Note that the capacity is monotonically decreasing with b. Hence, the more energy is requested, the more the transmitter is forced to use the most energetic symbol which reduces the information rate.

In a binary symmetric channel with cross-over probability p, the information-energy capacity function for a minimum energy rate b is

C(b) = 1 -H 2 (p), if 0 b 1 2 and H 2 (b) -H 2 (p), if 1 2 b 1 -p. ( 10
)
In the energy-unconstrained problem, equiprobable inputs are capacity-achieving and yield an energy rate of 1 2 . For any 0 b 1 2 , the energy rate constraint is vacuous. For b > 1 2 , the distribution must be perturbed so that the symbol 1 is transmitted more frequently to increase the energy rate. The maximum energy rate that is feasible is 1-p, when 1 is always transmitted.

In the Z-channel with 1 to 0 cross-over probability , i.e., the binary DMC with P Y |X = 1 0 1 -, the information-energy capacity function for a minimum energy rate b is

C(b) = C(0), if 0 b (1 -)π * and H 2 (b) -b 1-H 2 ( ), if (1 -)π * b 1 -, (11)
where C(0) denotes the capacity of this channel [START_REF] Golomb | The limiting behavior of the Z-channel[END_REF] given by

C(0) = log 2 1 - 1 1-+ 1-. (12)
The capacity-achieving input distribution is Bernouilli with parameter

π * = 1- 1 + (1 -) 1- . ( 13
)
The three examples show that the more stringent the energy rate constraint is, the more the transmitter needs to adapt its optimal strategy and switch over to using the most energetic symbol.

B. Gaussian Memoryless Channel

The results in [START_REF] Varshney | Transporting information and energy simultaneously[END_REF] extend directly to memoryless continuous alphabet channels. In the memoryless Gaussian channel with EH, at each channel use t ∈ {1, . . . , n}, if X t denotes the real symbol sent by the transmitter, the receiver observes the real channel output

Y t = h 1 X t + Z t , (14)
and the EH observes

S t = h 2 X t + Q t , (15)
with h 1 and h 2 constant non-negative channel coefficients satisfying the L 2 -norm condition: h 2 1, with h (h 1 , h 2 ) T to ensure the principle of energy conservation. The noise sequences Z t and Q t are identically distributed standard real Gaussian variables. The output energy function for this channel is given by ω(s) s 2 and the input sequence {X t } n t=1 satisfies an average input power constraint

1 n n t=1 E X 2 t P, (16)
with P the average transmit power in energy-units per channel use. The channel is fully described by the signal to noise ratios (SNRs) defined as SNR i h 2 i P , for i ∈ {1, 2}, given the normalization over the noise powers.

In the memoryless Gaussian channel, the alphabets are continuous. Nonetheless, information transmission and energy transmission can be described similarly to the DMC (where the finite input and output alphabets are replaced by R). The achievability, the information-energy capacity region, and the information capacity function can be defined similarly to the DMC when taking into account the average input power constraint P .

The information capacity of the Gaussian channel without minimum energy rate constraint is C(0, P ) = 1 2 log 2 (1 + SNR 1 ) and the maximum energy rate which can be achieved at the input of the EH is B 1 + SNR 2 .

For any 0 b 1+SNR 2 , the information-energy capacity function is

C(b, P ) = max X:E[X 2 ]≤P and E[S 2 ] b I(X; Y ). ( 17
)
Following similar steps as in [START_REF] Varshney | Transporting information and energy simultaneously[END_REF] and [START_REF] Smith | The information capacity of amplitude-and varianceconstrained scalar Gaussian channels[END_REF], it can be shown that

C(b, P ) = 1 2 log 2 (1 + SNR 1 ) , (18)
which equals the capacity of the Gaussian channel without EH under average input-power constraint P , achieved using zeromean Gaussian inputs with variance P . Thus in this case for any feasible energy rate 0 b 1 + SNR 2 the informationoptimal strategy is unchanged.

In the Gaussian channel with peak power constraint, depending on the value of the amplitude constraint, a tradeoff between the information and energy rates may be observed (See [START_REF] Varshney | Transporting information and energy simultaneously[END_REF] and [START_REF] Smith | The information capacity of amplitude-and varianceconstrained scalar Gaussian channels[END_REF]).

III. MULTI-USER SIMULTANEOUS ENERGY AND INFORMATION TRANSMISSION Unlike point-to-point setups, multi-user SEIT requires generally additional transmitter cooperation/coordination to increase the energy rate at the input of the EH. Consider a network in which a given transmitter simultaneously transmits energy to an EH and information to a receiver. If this transmitter is required to deliver an energy rate that is less than what it is able to deliver by only transmitting information, it is able to fulfill the task independently of the behavior of the other transmitters since it can use all its power budget to maximize its information transmission rate and it is still able to meet the energy rate constraint. Alternatively, when the requested energy rate is higher than what it is able to deliver by only transmitting information, its behavior is totally dependent on the behavior of the other transmitters. In this case, the minimum energy rate constraint drastically affects the way that the transmitters interact with each other. More critical scenarios are the case in which the requested energy rate is more than what all transmitters are able to deliver by simultaneously transmitting information using all the available individual power budgets. In these cases, none of them can unilaterally ensure reliable energy transmission at the requested rate. Hence, the transmitters must engage in a mechanism through which an energy rate that is higher than the energy delivered by exclusively transmitting informationcarrying signals is ensured at the EH. This suggests for instance, the use of power splits in which the transmitted symbols have an information-carrying and an energy-carrying components. The latter typically consists of signals that are known at all devices and can be constructed such that the energy captured at the EH is maximized. Moreover, the information-energy trade-off takes different facets depending on whether or not the network is centralized. In the former, there exists a central controller that determines an operating point and indicates to each transmitter and its corresponding receiver(s) the appropriate transmit-receive configuration to achieve such a point. In the latter, each network component is considered to be autonomous and seeks to determine its own transmit-receive configuration in order to maximize its individual benefit. Clearly, the operating points of the network are significantly different depending on the degree of control over all devices. That is, in a centralized network, all achievable information-energy rates are feasible operating points as the base-station can impose a particular operating point via a signaling system. However, in a fully decentralized network, only stable operating points are feasible, as each device tunes its transmit-receive configuration aiming at maximizing its own individual performance.

To understand the optimal behavior of SEIT in a multi-user network, an important scenario to look at is the multi-access channel (MAC) with an EH. From an information theoretic viewpoint, the information-energy trade-off was studied by Fouladgar et al. [START_REF] Fouladgar | On the transfer of information and energy in multi-user systems[END_REF] in the discrete memoryless two-user MAC. Recently, Belhadj Amor et al. studied SEIT in the centralized Gaussian MAC (G-MAC) with and without channel-output feedback [START_REF] Belhadj Amor | Feedback enhances simultaneous information and energy transmission in multiple access channels[END_REF], [START_REF] Belhadj Amor | Simultaneous energy and information transmission in Gaussian multiple access channels[END_REF] as well as in the decentralized G-MAC [START_REF] Belhadj Amor | Decentralized simultaneous energy and information transmission in multiple access channels[END_REF].

A. Gaussian Multi-Access Channel

Consider the channel model described in section II-B with two transmitters. Transmitters 1 and 2 wish to send two independent messages M 1 and M 2 to the single receiver at rates R 1 and R 2 . This channel model is called two-user memoryless Gaussian multiple access channel (G-MAC) with an EH. Transmitter i has an input power constraint P i and channel coefficients h 1i and h 2i to the receiver and the EH, respectively. These channel coefficients satisfy the L 2 -norm condition: ∀j ∈ {1, 2}, h j 2 1, with h j (h j1 , h j2 ) T in order to meet the energy conservation principle and SNR ji , with ∀(i, j) ∈ {1, 2} 2 are defined as: SNR ji |h ji | 2 P i . Encoding, decoding, probability of error, probability of energy outage, and achievability can be defined analogously to the Gaussian point-to-point channel when taking into account the considerations described above. The energy rate at the input of the EH cannot exceed the maximum feasible value given by B 1 + SNR 21 + SNR 22 + 2 √ SNR 21 SNR 22 . This can be achieved when the transmitters use all their power budgets to send fully correlated channel inputs. In the sequel, let b ∈ [0, 1 + SNR 21 + SNR 22 + 2 √ SNR 21 SNR 22 ] be the minimum energy rate required at the input of the EH.

B. Centralized SEIT in G-MAC

In a centralized G-MAC, the fundamental limits of the information-energy trade-off are fully characterized by the information-energy capacity region with a minimum energy rate constraint b, i.e., the closure of all achievable informationenergy rate triplets (R 1 , R 2 , B), is described by the following theorem.

Theorem 2 (Information-Energy Capacity Region with Minimum Energy Rate b (Theorem 1 in [START_REF] Belhadj Amor | Decentralized simultaneous energy and information transmission in multiple access channels[END_REF])). The informationenergy capacity region E b (SNR 11 , SNR 12 , SNR 21 , SNR 22 ) of the G-MAC with minimum energy rate constraint b is given by the set of all non-negative information-energy rate triplets (R 1 , R 2 , B) that satisfy

R 1 1 2 log 2 (1 + β 1 SNR 11 ) , (19a)
R 2 1 2 log 2 (1 + β 2 SNR 12 ) , (19b)
R 1 + R 2 1 2 log 2 1 + β 1 SNR 11 + β 2 SNR 12 , (19c) b
B 1 + SNR 21 + SNR 22 +2 (1 -β 1 )SNR 21 (1 -β 2 )SNR 22 , (19d)
with (β 1 , β 2 ) ∈ [0, 1] 2 .
The terms β 1 and β 2 in (19) might be interpreted as the fractions of power that transmitter 1 and transmitter 2 allocate for information transmission, respectively. The remaining fraction of power (1β i ) is allocated by transmitter i for exclusively transmitting energy to the EH by sending common randomness known non-causally to all terminals. For any (R 1 , R 2 , B), whenever the energy rate B is smaller than the energy rate required to guarantee reliable communications at the information rates R 1 and R 2 , the energy rate constraint is vacuous since it is always satisfied and each transmitter can exclusively use its available power budget to increase its information rate, i.e, β 1 = β 2 = 1. Alternatively, when the energy rate B is higher than what is strictly necessary to guarantee reliable communication, the transmitters face a trade-off between information and energy rates. Often, increasing the energy rate implies decreasing the information rates and viceversa.

C. Decentralized SEIT in G-MAC

In a decentralized G-MAC, the aim of transmitter i, for i ∈ {1, 2}, is to autonomously choose its transmit configuration s i in order to maximize its information rate R i , while guaranteeing a minimum energy rate b at the EH. The receiver is assumed to adopt a fixed decoding strategy that is known in advance to both transmitters. The choice of the transmit configuration of each transmitter is subject to the choice of the other transmitter as both of them must guarantee the minimum energy constraint; and at the same time, depending on the decoding scheme at the receiver, the information-carrying signal of one transmitter is interference to the other transmitter.

The competitive interaction of the two transmitters and the receiver in the decentralized G-MAC with minimum energy constraint b can be modeled by the following game in normal form: G(b) = K, {A k } k∈K , {u k } k∈K , where b is a parameter of the game, the set K = {1, 2} is the set of players (transmitters 1 and 2), and the sets A 1 and A 2 are their sets of actions. An action s i ∈ A i of a player i ∈ K is basically its transmit configuration. The utility function of transmitter i is u

i : A 1 × A 2 → R + and it is defined as ui(s1, s2) = Ri(s1, s2), if P (n) error (R1, R2) < and P (n) outage (b) < δ -1, otherwise, (20)
where > 0 and δ > 0 are arbitrarily small numbers and R i (s 1 , s 2 ) (written as R i for simplicity) denotes an information rate achievable with the configurations s 1 and s 2 . Note that the utility is -1 when either the error probability or the energy outage probability is not arbitrarily small. This is meant to favor the action profiles in which there is no information transmission (information rate and error probability are zero) but there is energy transmission (probability of energy outage can be made arbitrarily close to zero), over the actions in which the information rate is zero but the energy constraint is not satisfied. Note that there might exist several transmit configurations that achieve the same triplet (R 1 , R 2 , B) and distinction is made only when needed.

The fundamental limits of SEIT in the decentralized G-MAC are fully characterized the η-Nash equilibrium [START_REF] Nash | Equilibrium points in n-person games[END_REF] (η-NE) information-energy region, with η 0 arbitrarily small. This region corresponds to the set of information-energy rate triplets (R 1 , R 2 , B) that are achievable and stable in the G-MAC where stability is considered in the sense of Nash [START_REF] Nash | Equilibrium points in n-person games[END_REF]. More specifically, an action profile (a transmit configuration) (s * 1 , s * 2 ) is an η-NE, if none of the transmitters can increase its own information rate by more than η bits per channel use by changing its own transmit configuration and keeping the average error probability and the energy outage probability arbitrarily close to zero.

The η-NE information-energy region of the game G(b) when the receiver uses single-user decoding (SUD), denoted by N SUD (b), is described by the following theorem. Let SIC(i → j) denote the case in which the receiver uses successive interference cancellation (SIC) with decoding order: transmitter i before transmitter j, with i ∈ {1, 2}. In this case, the η-NE information-energy region of the game G(b), denoted by N SIC(i→j) (b), is described by the following theorem.

0 R 1 = 1 2 log 2 1 + β 1 SNR 11 1 + β 2 SNR 12 , ( 21a
) 0 R 2 = 1 2 log 2 1 + β 2 SNR 12 1 + β 1 SNR 11 , (21b)
0 R i = 1 2 log 2 1 + β i SNR 1i 1 + β j SNR 1j , ( 23a
) 0 R j = 1 2 log 2 (1 + β j SNR 1j ) , (23b) b
B 1 + SNR 21 + SNR 22 +2 (1 -β 1 )SNR 21 (1 -β 2 )SNR 22 , (23c)
where

β 1 = β 2 = 1 when b ∈ [0, 1 + SNR 21 + SNR 22 ] and (β 1 , β 2 ) satisfy b = 1 + SNR 21 + SNR 22 + 2 (1 -β 1 )SNR 21 (1 -β 2 )SNR 22 (24) when b ∈ (1 + SNR 21 + SNR 22 , 1 + SNR 21 + SNR 22 + 2 √ SNR 21 SNR 22 ].
Let N (b) denote the η-NE region of the game G(b) when the receiver uses any time-sharing between the previous decoding techniques. The set N (b) is defined as:

N (b) = Closure N SUD (b) ∪ N SIC(1→2) (b) ∪ N SIC(2→1) (b) .
(25) That is, if the receiver performs any time-sharing combination between SUD, SIC(1 → 2), and SIC(2 → 1) then the transmitters can use the same time-sharing combination between their corresponding η-Nash equilibria strategies to achieve any point inside N (b). IV. DISCUSSION In point-to-point channels, depending on the channel model, the trade-off between information and energy rates is not always observed (e.g., Gaussian channel with peak power constraint [START_REF] Varshney | Transporting information and energy simultaneously[END_REF], [START_REF] Smith | The information capacity of amplitude-and varianceconstrained scalar Gaussian channels[END_REF]). In G-MACs, SEIT induces additional transmitter cooperation to meet the energy rate constraints. This cooperation is usually not natural especially when the transmitters do not share common information and are not co-located. In this sense, it seems likely that providing additional means of cooperation would result in a significant performance enhancement of SEIT. From this standpoint, exploring the benefits induced by cooperation techniques such as channeloutput feedback and conferencing in SEIT for the two-user G-MAC is really promising, especially in terms of energy transmission. Recently, Belhadj Amor et al. have shown that channel-output feedback can provide a multiplicative factor to the energy rate without any decrease on the information rates [START_REF] Belhadj Amor | Feedback enhances simultaneous information and energy transmission in multiple access channels[END_REF]. This surprising result is mainly due to the additional correlation that can be induced among the signals of all the transmitters via feedback in order to increase the energy that can be collected at a given EH. This reasoning is valid for multi-access channels with an arbitrary number of users and it also applies to other multi-user setups such as the broadcast and interference channels.

Theorem 3

 3 (η-NE Information-Energy Region of the Game G(b) with SUD (Theorem 2 in [11])). The set N SUD (b) of η-NEs of the game G(b) is contains all information-energy rate-triplets (R 1 , R 2 , B) which satisfy:

Theorem 4

 4 (η-NE Information-Energy Region of the Game G(b) with SIC (Theorem 3 in [11])). The set N SIC(i→j) (b) contains all information-energy rate-triplets (R 1 , R 2 , B) satisfying:

Fig. 1

 1 shows the projection of the regions described in Theorem 3 and Theorem 4 as well as the convex hull of these regions for a symmetric G-MAC with SNR 11 = SNR 12 = SNR 21 = SNR 22 = 10 (EH and receiver are co-located). Note that for all b 1 + SNR 21 + SNR 22 , both transmitters use the whole available power for information transmission (see the figure on the left). Alternatively, when b > 1+SNR 21 +SNR 22 , both transmitters use the minimum energy needed to make the energy-outage probability arbitrarily close to zero and seek for the largest possible information transmission rates (See the figure on the right). One of the main observations is that the existence of an η-NE, with η arbitrarily small, is always guaranteed as long as the SEIT problem is feasible, that is, b 1 + SNR 21 + SNR 22 + 2 √ SNR 21 SNR 22 since N (b) = ∅.

Fig. 1 .

 1 Fig. 1. Projection of the sets N SUD (b), N SIC(i→j) (b), and N (b) (blue region) over the R 1 -R 2 plane for different values of b. The information capacity region is also plotted as a reference (white region inside solid lines) for SNR 11 = SNR 12 = SNR 21 = SNR 22 = 10.

  SNR 21 + SNR 22 + 2 (1β 1 )SNR 21 (1β 2 )SNR 22 (22) when b ∈ (1 + SNR 21 + SNR 22 , 1 + SNR 21 + SNR 22 + 2 √ SNR 21 SNR 22 ].

b B 1 + SNR 21 + SNR 22 +2 (1β 1 )SNR 21 (1β 2 )SNR 22 , (

21c

)

where

β 1 = β 2 =

1 when b ∈ [0, 1 + SNR 21 + SNR 22 ] and (β 1 , β 2 ) satisfy b = 1 +

This research is supported in part by the European Commission under Marie Skłodowska-Curie Individual Fellowship No. 659316 (CYBERNETS).


Thomas Durt
email: thomas.durt@centrale-marseille.fr

Generalized guidance equation for peaked quantum solitons and effective gravity

HAL is a

gravitational interaction has also been reported between two droplets. In [START_REF] Couder | Walking droplets, a form of wave-particle duality at macroscopic scale[END_REF] for instance we can read: ...We find that, depending on the value of d, (d represents here the impact parameter of the collision)the interaction is either repulsive or attractive. When repulsive, the drops follow two approximately hyperbolic trajectories. When attractive, there is usually a mutual capture of the two walkers into an orbital motion similar to that of twin stars ...

Our study was motivated by the double solution program [START_REF] Bacciagaluppi | Quantum Theory at the Crossroads: Reconsidering the 1927 Solvay Conference[END_REF][START_REF] De Broglie | Une tentative d'interprétation causale et non linéaire de la mécanique ondulatoire: la théorie de la double solution[END_REF][START_REF] De Broglie | Interpretation of quantum mechanics by the double solution theory Annales de la Fondation Louis de Broglie[END_REF] of Louis de Broglie, according to which the quantum wave function, solution of the linear Schrödinger equation does not contain all elements of reality concerning the quantum system. In de Broglie's view, particles would consist of a peaked concentration of energy that would coexist with the linear wave function, and the latter would guide the former according to the de Broglie-Bohm guidance equation. Our work consists of an attempt to realize de Broglie's program by adding another ingredient to it, which is that we suppose the existence of a non-linear self focusing potential [START_REF] Bacciagaluppi | Quantum Theory at the Crossroads: Reconsidering the 1927 Solvay Conference[END_REF] of gravitational nature which prohibits the spreading of the peaked soliton (solitary wave) representing the particle. Therefore we assume that the system evolves in time according to the non-linear equation [START_REF] Arriola | A Variational Approach to the Schrödinger-Poisson System: Asymptotic Behaviour, Breathers, and Stability[END_REF].

i ∂Ψ(t, x) ∂t = -2 ∆Ψ(t, x) 2m + V L (t, x)Ψ(t, x) + V NL (Ψ)Ψ(t, x), [START_REF] Arriola | A Variational Approach to the Schrödinger-Poisson System: Asymptotic Behaviour, Breathers, and Stability[END_REF] where V L (t, x) represents the usual external potentials, for instance it could represent the coupling to external electro-magnetic fields. It is thus represented by a self-adjoint operator linearily acting on the Hilbert space.

VNL represents a self focusing non-linearity. Contrary to V L it depends on Ψ. In order to distinguish short range and long range we shall consider in the rest of the paper the Yukawa like screened S-N potential:

V NL (Ψ) ≡ -K d 3 x ′ ( |Ψ(t, x ′ )| 2 |x -x ′ | )e -|x-x ′ | λ , (2)
where K is a positive coupling constant and λ is a characteristic length to be defined soon. The Schrödinger-Newton (S-N) potential is in turn defined as follows:

V NL SN (Ψ)((t, x) ≡ -Gm 2 d 3 x ′ ( |Ψ(t,x ′ )| 2 |x-x ′ | );
(1) has been abundantly studied in the literature in presence of the S-N potential and in absence of external potential (V L = 0). In particular, when V L = 0, (1) possesses a "ground-state" solution of the form ψ(x, t) = e -iEg t φNLg(x); φNLg is thus a solution of

-2 2m ∆φNLg(x) + Gm 2 d 3 y φNLg(y) 2 |x -y| φNLg(x) = EgφNLg(x) , (3)
which was studied in astrophysics and is known under the name of the Choquard equation [START_REF] Lieb | Existence and Uniqueness of the Minimizing Solution of Choquard's Nonlinear Equation[END_REF][START_REF] Colin | Can quantum systems succumb to their own (gravitational) attraction?[END_REF]. In [START_REF] Lieb | Existence and Uniqueness of the Minimizing Solution of Choquard's Nonlinear Equation[END_REF], Lieb showed that the energy functional

E(φ) = 2 2m d 3 x ∇φ(x) 2 (4) - Gm 2 2 d 3 x d 3 y φ(y) 2 |x -y| φ(x) 2 ,
is minimized by a unique solution φNLg(x) of the Choquard equation (3) for a given L2 norm N (φ).

As is well-known, the Choquard equation possesses well-defined scaling properties [START_REF] Colin | Can quantum systems succumb to their own (gravitational) attraction?[END_REF][START_REF] Van Meter | Schrödinger-Newton "collapse" of the wave-function[END_REF]; in particular, we may scale its solution in such a way that in the limit where the L2 norm goes to plus infinity, the extent goes to zero, and the energy to minus infinity. Numerical studies also established that φNLg has a "hump", quasi-gaussian shape [START_REF] Colin | Can quantum systems succumb to their own (gravitational) attraction?[END_REF][START_REF] Van Meter | Schrödinger-Newton "collapse" of the wave-function[END_REF]. In the case of quantum particles the non-linear potential V NL aims represents in our eyes a short-range self-focusing interaction of gravitational nature which localizes the wave function Ψ, analogous to the Poincaré pressure [START_REF]Poincaré Sur la dynamique[END_REF] aimed at ensuring the cohesion of electrons in presence of Coulombian self-repulsion. In the rest of the paper we shall identify the quantum particles with these self-collapsed wave packets (solitons). Our aim is to show that when several particles are present there appears a long range effective gravitational interaction between them. We explicitly established a distinction between gravitation at short and long spatial scale in our model, with the aim of gaining information about the short scale behaviour by fitting the long range effective gravitational potential with Newton gravitation. In the case of bouncing droplets, the non-linearity mimicks the complicate mechanism which ensures their stability. That we consider droplets or quantum systems, λ is intentionally chosen to be larger than the size of the object under interest (particle or droplet), in such a way that the solitonic ground state of (1) when V L = 0 is essentially the solution φNLg(x) of (3). If we consider quantum particles like the electron or the proton, we choose K to be Gm 2 ; in the case of droplets K ought to be calibrated in function of the experimental set-up.

The first real novelty of our paper is that we assume that the solution of (1) obeys the factorisation ansatz:

Ψ = ( 1 AL(t, x0(t)) )ΨL(t, x) • φNLg(x -x0(t))e -iEgt/ , (5)
where we introduce the pilot wave ΨL, of amplitude AL and phase ϕL: ΨL(t, x)) ≡ AL(t, x)e iϕ(t,x) and x0 the position of the barycentre of the soliton φNLg. We also suppose to begin with that x0 follows a de Broglie-Bohm trajectory:

x0(t) = x0(t = 0) + t 0 dtv dB-B , (6)
where v dB-B represents the dB-B velocity derived from the pilot wave ΨL evaluated at the position of the barycentre of Ψ:

v dB-B = m ▽ϕL(x0(t), t). (7)
Our goal is to study the feedback of the soliton on the pilot wave. We shall thus study in the rest of the paper solutions of (1,2), under the constraints [START_REF] Colin | Can quantum systems succumb to their own (gravitational) attraction?[END_REF][START_REF] Colin | Crucial tests of macrorealist and semi-classical gravity models with freely falling mesoscopic nanospheres[END_REF][START_REF] Couder | Dynamical phenomena: walking and orbiting droplets[END_REF].

The second novelty of our paper is that contrary to the majority of the papers that can be found in the literature concerning the S-N equation (1), we assume, for reasons that we shall clarify in the core of the paper, that whenever we consider elementary particles the size of the solution of (1,5) is very small, actually of the order of Gm/c 2 . In the case of an electron for instance this size is of the order of 10 -55 meter. This means [START_REF] Colin | Can quantum systems succumb to their own (gravitational) attraction?[END_REF] that the energy (4) of the self-collapsed ground state is of the order of -mc 2 . In our approach, the external potentials are thus treated as a perturbation, contrary to the standard approach, where the non-linearity is treated as a weak perturbation [START_REF] Smolin | Quantum fluctuations and inertia[END_REF][START_REF] Colin | Crucial tests of macrorealist and semi-classical gravity models with freely falling mesoscopic nanospheres[END_REF]. The non-linearity is so strong in our case that it forces the state of the system to behave as a solitary wave, a soliton of extremely small size, solution of the so-called Choquard equation [START_REF] Bohm | A Suggested Interpretation of the Quantum Theory in Terms of "Hidden" Variables. I and II[END_REF] for which the spread gets compensated by the non-linearity. The wave function of the system is thus supposedly self-collapsed to begin with, since arbitrary long times. This marks a difference with previous studies which rather focused on the collapse process itself [START_REF] Diósi | Gravitation and quantum-mechanical localization of macroobjects[END_REF][START_REF] Penrose | On Gravity's Role in Quantum State Reduction[END_REF][START_REF] Van Meter | Schrödinger-Newton "collapse" of the wave-function[END_REF][START_REF] Colin | Can quantum systems succumb to their own (gravitational) attraction?[END_REF][START_REF] Colin | Crucial tests of macrorealist and semi-classical gravity models with freely falling mesoscopic nanospheres[END_REF]. We consider situations where AL and ϕL smoothly vary in space and time compared to φNLg so that in good approximation (5) reads

Ψ = e iϕ L • φNLg(x -x0(t))e -iEgt/ , (8)
which explicitly shows that Ψ is a constant L2 norm function, in accordance with the norm-preserving character of the evolution equation [START_REF] Arriola | A Variational Approach to the Schrödinger-Poisson System: Asymptotic Behaviour, Breathers, and Stability[END_REF].

In this paper, we shall apply these ideas to a system consisting of two particles in order to derive an effective long range gravitational attraction between the particles. We also compare our predictions to droplets phenomenology and make in this case new predictions that are likely to be tested in the lab.

Effective gravitation

To simplify the treatment we shall first consider distinguishable particles A and B and suppose that the wave function of the full system reads

Ψ(x, t) = ΨL(x, t) • ( φ A N Lg (x,t) A L (x A 0 ,t) + φ B N Lg (x,t) A L (x B 0 ,t) )
where we introduced the short notation φ

A(B) NLg (x, t) ≡ φNLg(x -x A(B) 0 (t))e -iEgt/
, with x A 0 and x B 0 the positions of the barycentres of the solitons assigned to the two particles. In virtue of ( 8), at the locations x

A(B) 0 , V NL (Ψ) = V NL (φNLg), so that φ A(B) NLg (x, t) satisfies the constraint i • ∂φ A(B) NLg ∂t = - 2 2m • ∆φ A(B) NLg + V NL (Ψ)φ A(B) NLg - 2 m • i▽ϕL(t, x A(B) 0 ) • ▽φ A(B) NLg (9)
Multiplying ( 9) by ΨL(x, t), and substracting the result from (1) we find, in the low-dBB-velocity regime where the temporal derivative of AL(x

A(B) 0 , t) is small compared to other contributions ( φ A NLg (x, t) AL(x A 0 , t) + φ B NLg (x, t) AL(x B 0 , t) )(i • ∂ΨL(t, x) ∂t + 2 2m ∆ΨL(t, x) -V L (t, x)ΨL(t, x)) = - 2 m (▽ΨL(t, x) + ΨL(t, x) • i▽ϕL(t, x0)) • ▽( φ A NLg (x, t) AL(x A 0 , t) + φ B NLg (x, t) AL(x B 0 , t) ). ( 10
)
We shall only consider situations where the positions x A 0 and x B 0 are not too close to each other e.g. larger than λ; then we may neglect the overlap between the two solitons, so that, dividing (10) by (

φ A N Lg (x,t) A L (x A 0 ,t) + φ B N Lg (x,t) A L (x B 0 ,t) ) we find i • ∂ΨL(t, x) ∂t + 2 2m ∆ΨL(t, x) -V L (t, x)ΨL(t, x) = (- 2 m (▽ΨL(t, x) + ΨL(t, x) • i▽ϕL(t, x0)) • ( ▽φ A NLg (x, t) φ A NLg (x, t) + ▽φ B NLg (x, t) φ B NLg (x, t) ), (11)
which looks like the linear Schrödinger equation with source terms. At some distance from the soliton φNLg decreases exponentially, because φNLg is a negative energy state with radial symmetry. Moreover

▽ x,y,z φ N Lg (x,t) φ N Lg (x,t)
is odd in x, y, z around x0, y0, z0. It behaves thus along the x, y, z axis passing through (x0, y0, z0) as a kink with a s-like shape ---/ ---. In the plane orthogonal to this axis its tail decreases like (x-x0)/ (x -x0)2 + (y -y0) 2 + (z -z0) 2 , but we should not worry about the tails because when several particles are isotropically distributed, the tails cancel each other and the shape of the kink is rather ---/ ---. The integration over space of the source term proportional to ΨL is equal to zero. Integrating the source term proportional to ▽ΨL by part we find that everything happens as if the source terms in equation [START_REF] De Broglie | Une tentative d'interprétation causale et non linéaire de la mécanique ondulatoire: la théorie de la double solution[END_REF] were proportional to Dirac 3-deltas, and we may write [START_REF] De Broglie | Une tentative d'interprétation causale et non linéaire de la mécanique ondulatoire: la théorie de la double solution[END_REF]

in the form i • ∂ΨL(t, x) ∂t + 2 2m ∆ΨL(t, x) -V L (t, x)ΨL(t, x) = -4π 2 2m ΨL(t, x) • (12) (LAδ Dirac (x -x A 0 ) + LBδ Dirac (x -x B 0 )),
where L is a length of the order of the size (extent) of the particle. We incorporated in L A(B) factors of the order of unity, in order to simplify the computations. In a perturbative or bootstrap approach, we shall now treat (12) as a generalised Poisson equation with a source term proportional to a solution of the homogeneous (linear Schrödinger) equation without sources; moreover we impose a factorisable solution in the form

Ψ inhom L (t, x) = Ψ hom L (t, x)(-φ G (t, x)/c 2 ), then (12) reads
(-φ G (t, x)/c 2 )(i • ∂Ψ hom L (t, x) ∂t + 2 2m ∆Ψ hom L (t, x) -V L (t, x)) + 2 m ▽Ψ hom L (t, x) • ▽(-φ G (t, x)/c 2 ) +(Ψ hom L (t, x))(i • ∂(-φ G (t, x)/c 2 ) ∂t + 2 2m ∆(-φ G (t, x)/c 2 )) = -4π 2 2m • Ψ hom L (t, x) • (LAδ Dirac (x -x A 0 ) + LBδ Dirac (x -x B 0 )). ( 13
)
The three first terms of ( 13) are equal to zero, because Ψ hom L is solution of the linear Schrödinger equation without sources. It is consistent, in the low-dBB-velocity regime, to neglect

▽Ψ hom L (t, x) • ▽(-φ G (t, x)/c 2 ) as well as ∂(-φ G (t,x)/c 2 )
∂t as we shall explain soon. Then φ G obeys the Poisson equation

∆(φ G (t, x)/c 2 ) = 4π • (LAδ Dirac (x -x A 0 ) + LBδ Dirac (x -x B 0 )) (14)
Making use of the well-known properties of the Green functions associated to the Laplace equation, it is easy to check that the solution of ( 14) is

φ G (t, x)/c 2 = - LA |x -x A 0 | + LB |x -x B 0 | . ( 15
)
φ G (t, x)/c 2 looks thus like an effective (here repulsive) gravitational potential 2 . We check a posteriori that we were in right to neglect certain corrections proportional to the dB-B velocities.

In order to fit φ G with a Newtonian potential in the long range domain, let us consider HL the linear Hamiltonian of the system:

HL = H A L + H B L + mAc 2 + mBc 2 + V AB L
, including a possible coupling between the A and B systems. In the non-relativistic regime, H

A(B) L << m A(B) c 2 , H AB L << m A(B) c 2 , |i • ∂Ψ ∂t | << m A(B) c 2 |ΨL|. Note that ΨL(t, x), the solution of (12) obeys ΨL =Ψ hom L + Ψ inhom = (1 -φ G (t, x)/c 2 )Ψ hom L
. Let us from now on neglect self-interactions which were already taken account in

V NL . Requiring that Ψ hom L = ΨL/(1 - φ G /c 2 ) satisfies the homogeneous equation HLΨ hom L = i • ∂Ψ hom L ∂t
results, provided we only consider the dominating contribution, in the replacement in

H A(B) of m A(B) c 2 by m A(B) c 2 (m A(B) c 2 )φ G A(B) (t, x)/c 2 .
At this level, an effective gravitational interaction between A and B emerges which

satisfies φ G A(B) (t, x)/c 2 = -( L B(A) |x B(A) 0 -x A(B) 0 | ).
Requiring the equivalence of this effective potential with the Newtonian gravitational potential φ Newton = -

Gm A m B |x B(A) 0 -x A(B) 0 | imposes the con- straint: L A(B) = G • m A(B) 2c 2 , ( 16
)
as announced in the introduction. Disregarding the self-interactions, the netto contribution of the perturbation is thus, when ( 16) is satisfied, to add -GmAmB(

1 |x A 0 -x B 0 |
) to the total energy.

If A and B represent identical particles, we impose that the fermionic or bosonic character of the full wave Ψ is expressed at the level of the linear component only. The non-linear components behave thus like bosons and we get

Ψ(1, 2) = ΨL(t, x1, x2) • ( 1 AL ) • S • φ A NLg (t, x1)φ B NLg (t, x2)) ≈ e iϕ L (t,x 1 ,x 2 ) • S • φ A NLg (t, x1)φ B NLg (t, x2)),
where φ

A(B) NLg (t, x i ) = φNLg(x i -x A(B) 0 (t))e -iEgt/ while S is a bosonic symmetrization operator: 2S • φ A NLg (t, x1)φ B NLg (t, x2))= φ A NLg (t, x1)φ B NLg (t, x2)+φ A NLg (t, x2)φ B NLg (t, x1). The barycentres x A(B) 0
of the particles move according to the two particles dB-B guidance equation

v idrif t = m ▽ i ϕL(x A(B) 0 (t), x B(A) 0 (t), t), (i = 1, 2) (17)
In the present case, (1) and ( 17) are dynamical equations in the 3N =6 dimensional configuration space (here there are N = 2 particles). Therefore ΨL(1, 2) = ALe iϕ L , where AL and ϕL depend on x 1 and x 2 instantaneously. The system is therefore likely to exhibit a non-local [START_REF] Einstein | Can Quantum-Mechanical Description of Physical Reality be Considered Complete?[END_REF] behaviour in presence of entanglement [START_REF] Bohm | A Suggested Interpretation of the Quantum Theory in Terms of "Hidden" Variables. I and II[END_REF].

We shall only consider situations where x A 0 and x B 0 do not overlap. By computations very similar to those already performed in the case of indistingusihable particles, we find that an effective gravitational interaction appears, symmetrized in x1 and x2.

φ G (t, x)/c 2 = -LΣi=1,2( 1 |x i -x A 0 | + 1 |x i -x B 0 | ) ( 18
)
Fitting this expression with the Newton interaction provides as before the constraint L = G•m 2c 2 that we may also rewrite in the form

mc 2 = G•m 2 2L
in accordance with the results announced in the introduction and in particular with the value of the energy functional (4) which is of the order of -mc 2 in this case. Relying on previous stability analyses of the S-N equation [START_REF] Arriola | A Variational Approach to the Schrödinger-Poisson System: Asymptotic Behaviour, Breathers, and Stability[END_REF][START_REF] Van Meter | Schrödinger-Newton "collapse" of the wave-function[END_REF][START_REF] Colin | Can quantum systems succumb to their own (gravitational) attraction?[END_REF], it is worth noting that to destabilize the soliton would require a positive energy of the order of mc 2 which confirms our interpretation in which the soliton and the particle are the same object.

2 Droplets, dB-B trajectories, and gravitation dB-B trajectories [START_REF] De Broglie | Une tentative d'interprétation causale et non linéaire de la mécanique ondulatoire: la théorie de la double solution[END_REF][START_REF] Bohm | A Suggested Interpretation of the Quantum Theory in Terms of "Hidden" Variables. I and II[END_REF][START_REF] Holland | The Quantum Theory of Motion[END_REF] have been studied in relation with the measurement problem, but they are often considered as conceptual tools rather than empirical realities, among other reasons because the dB-B dynamics is often considered to be an ad hoc reinterpretation of the standard quantum theory. In the last decade, however, they were realized in the lab. with artificial macroscopic systems, the bouncing oil droplets or walkers [START_REF] Busch | Pilot-Wave Hydrodynamics[END_REF][START_REF] Couder | Walking droplets, a form of wave-particle duality at macroscopic scale[END_REF], which were shown to follow dB-B like quantum trajectories.

Our model seemingly catches some fundamental properties of droplets in the sense that it explains the appearance of an effective gravitational interaction in presence of dB-B trajectories, as they were observed directly in droplets phenomenology (and only there).

Of course, droplets are complicated, hydrodynamical, macroscopic systems, but in order to simplify the treatment we shall from now on identify the droplets with the self focused solitons of our model φNL and the liquid on which they are floating with the pilot wave ΨL, which implies that the state of the system is represented by Ψ(x, t) = ΨL(x, t) • (

φ 0(A) N L (x,t) A L (x A 0 ,t) + φ 0(B) N L (x,t) A L (x B 0 ,t) )
, where A and B refer to the presence of two droplets. It is then easy to repeat the same treatment as before, provided the two solitons stay away from each other. As has been reported in [START_REF] Couder | Single-Particle Diffraction and Interference at a Macroscopic Scale[END_REF], stationary waves are present, resulting from the forcing frequency imposed to the container at frequency f0. The stationary waves are characterized by Faraday wave lengths λF in good agreement with the values computed from the dispersion relation, at the frequency fF , where the Faraday frequency fF is equal to half the forcing frequency f0.

In order to simulate the propagation of vibrations in the container, let us modelize, in a first step, the "Schrödinger" linear equation describing wave propagation in the container by the d' Alembert equation

( 1 v 2 ∂ 2 ∂t 2 -∆)ΨL = 0, (19)
with v = λF • fF . Of course d' Alembert equation is not dispersive, whereas the liquid of the container is a dispersive medium, but we shall assume in first approximation that the velocity of propagation smoothly depends on the frequency, in the spectral domain under interest. This remark matters, because, as noted in [START_REF] Couder | Single-Particle Diffraction and Interference at a Macroscopic Scale[END_REF] two frequencies play a role here, f0 and fF = f0/2. When two droplets are present we must solve an inhomogeneous d' Alembert equation with a source term 4π(LA

• δ(x -x A 0 ) + LB • δ(x - x B 0 )).
Repeating the same process as for the inhomogeneous Schrödinger equation, we predict the appearance of a pseudo-gravitational interaction φ P G which obeys

( 1 v 2 ∂ 2 ∂t 2 -∆)φ P G = -4π(LA • δ(x -x A 0 ) + LB • δ(x -x B 0 )).
Due to the forcing, we shall replace d' Alembert equation by Helmholtz equation

( (2π) 2 f 2 0 v 2 + ∆)φ P G = (k 2 0 + ∆)φ P G = (20) 4π(LA • δ(x -x A 0 ) + LB • δ(x -x B 0 )),
where k0 ≡ 2π/λ0. [START_REF]Poincaré Sur la dynamique[END_REF] has been studied by us in another context [START_REF] Durt | Estimate of the weight of empty space based on astronomical observations quant/ph[END_REF], and, in the case of a punctual source, its Green function is not 1/r but cos(kr)/r which leads as shown in [START_REF] Durt | Estimate of the weight of empty space based on astronomical observations quant/ph[END_REF] to the appearance of attractive and repulsive gravitational zones periodically distributed among the punctual sources.

Henceforth we predict the appearance of a pseudo-gravitational field

φ P G = -v 2 (LA(cos(k0|x-x A 0 |)/|x-x A 0 |)+LB (cos(k0|x-x B 0 |)/|x-x B 0 |)).
Disregarding self-interactions, the sum of the potential energy undergone by A (due to B) with the potential energy undergone by B (due to

A) is thus equal to -v 2 (cos(k0|x B -x A 0 |)/|x B -x A 0 |)(MBLA + MALB).
Our model explains in this way the appearance of repulsive and attractive gravitation in droplets phenomenology, in connection with the presence of dB-B trajectories.

In the same vein, we explain the appearance of a pseudo-quantisation rule, self-adapting to the forcing frequency, and similar to the one observed in [START_REF] Couder | Dynamical phenomena: walking and orbiting droplets[END_REF] according to which orbital radii obey d orb n = (n/2 -ǫ)λF , with n a positive integer, where we made use of the fact that the Faraday frequency is one halve of the forcing frequency f0. In our eyes this effect is not specifically quantum, it is rather related to the very unfamiliar topology of the attractive and repulsive (!) gravitational basins (in case of circular orbits we conjecture that the aforementioned quantisation rule imposes that after one closed circular orbit each soliton keeps the Faraday phase that it possessed before the revolution). Let us now propose a toy model for quantum gravity, inspired by droplet phenomenology.

Minimal coupling to gravity

i • ∂ ∂t ( ΨL(t, x) (1 -φ G /c 2 ) ) = - 2 2m ∆( ΨL(t, x) (1 -φ G /c 2 ) ) (21) +V L (t, x)( ΨL(t, x) (1 -φ G /c 2 ) ) + mc 2 ( ΨL(t, x) (1 -φ G /c 2 ) ),
to be interpreted according to us in a perturbative approach, in terms of the small parameter φ G /c 2 , replacing 1/(1 -φ G /c 2 ) by 1 + φ G /c 2 + (φ G /c 2 ) 2 + .... There appears thus post-Newtonian corrections proportional to ▽ΨL(t, x) • ▽(-φ G (t, x)/c 2 ) as well as ∂(-φ G (t,x)/c 2 ) ∂t and φ G /c 2 . It is not in the scope of our paper to study these corrections 3 .

We shall emit the hypothesis that the minimal coupling condition that consists of replacing ΨL by ΨL/(1 -φ G /c 2 ) in the linear Schrödinger equation is general, and that φ G is a field in "real", 3-dimensional space, equal to the product of the gravitational fields generated by all species of indistinguishable elementary particles. In a regime where all these contributions φ k G are small compared to c 2 , we find that

π k (1 -φ k G /c 2 ) ≈ (1 -k φ k G /c 2 )
, which expresses the universal character of gravitation. If we had chosen to begin with to describe the system with the relativistic Klein-Gordon equation (that we write in the free case here for simplicity but the result is still valid in the presence of external potentials e.g. electro-magnetic potentials)

(c 2 ( 1 c 2 ∂ 2 ∂t 2 -∆) - m 2 c 2 2 )ΨL = 0 (22)
then, by a treatment similar to the one performed in the previous sections we would have found finally that the gravitational potential obeys the inhomogeneous d' Alembert equation:

-c 2 ( 1 c 2 ∂ 2 ∂t 2 -∆)φG = 4πGρ. (23)
We find so that all gravitational waves move at the (same) speed of light in vacuum.

Beginning with the Dirac equation βi ∂tΨ(t, x) -βαc i ▽Ψ(t, x) = mc 2 Ψ(t, x) + VNLΨ(t, x),

where α and β represent Dirac matrices and imposing the ansatz Ψ = ΨL(t, x) • φNL(t, x) where ΨL(t, x) a Dirac 4-spinor and φNL(t, x) is a Lorentz scalar moving at the velocity v DiracdB-B = ΨL(t, x) † αΨL(t, x)/ΨL(t, x) † ΨL(t, x), in accordance with the dB-B guidance equation [START_REF] Takabayasi | Relativistic hydrodynamics of the Dirac matter[END_REF][START_REF] Holland | The Quantum Theory of Motion[END_REF], we find again by similar methods as those of previous sections the inhomogeneous Dirac equation

i ∂tΨL(t, x) -αc i ▽ΨL(t, x) -mc 2 βΨL(t, x) = -i αc(ΨL(t, x) -ΨL(t, x0)) ▽φNLg(t, x) φNLg(t, x) (24)
Multiplying ( 24) by (i ∂t

+ αc i ▽ + mc 2 β) we get -2 c 2 ( 1 c 2 ( ∂ 2 ∂t 2 -∆) + m 2 c 2 2 )ΨL(t, x) = (i ∂t+αc i ▽+mβ) (-) i αc(ΨL(t, x)-ΨL(t, x0)) ▽φ N Lg (t,x)
φ N Lg (t,x) . Applying the same reasonings as in the previous section, making use of ( 16), and α 2 k = 1, still in the limit of slowly moving bodies, we find [START_REF] Takabayasi | Relativistic hydrodynamics of the Dirac matter[END_REF]. Together with i ∂t

Ψ L (t,x) (1-φ G /c 2 ) -αc i ▽ Ψ L (t,x) (1-φ G /c 2 ) -mc 2 β Ψ L (t,x) (1-φ G /c 2 )
= 0, and the Dirac-dB-B guidance relation v DiracdB-B = ΨL(t, x) † αΨL(t, x)/ΨL(t, x) † ΨL(t, x) our model is self-consistent. 3 These two corrections are reminiscent of the standard coupling in electro-magnetism in which we replace i ∂ ∂µ by i ∂ ∂µ -eAµ. Here we replace i ∂ ∂µ by i ∂ ∂µ + i c 2 ∂φ G ∂µ . Formally, the gravitational potential looks like a purely imaginary gauge field. This is not so amazing having in mind the role played by rescalings in our approach.

Conclusions

Treating particles/droplets as incompressible solitons which obey dB-B dynamics 4 , the spread of which is compensated by a self focusing nonlinear interaction, we predicted the appearance of an effective gravitation. In the case of elementary particles, our model makes it possible, fitting the effective gravitation with Newtonian gravitation to estimate the extent of the particle [START_REF] Einstein | Can Quantum-Mechanical Description of Physical Reality be Considered Complete?[END_REF]. In the case of droplets, it delivers precise predictions about the pseudo-gravitational interaction. Our model is quite unorthodox. We found our main inspiration in old fashioned concepts such as the Poincaré pressure [START_REF]Poincaré Sur la dynamique[END_REF] or de Broglie's double solution program [START_REF] De Broglie | Une tentative d'interprétation causale et non linéaire de la mécanique ondulatoire: la théorie de la double solution[END_REF], and we did not make any kind of reference to curved space-time. This is maybe an open door for quantum gravity, maybe not. At this level, we simply do not know. In order to falsify our model it suffices in principle to test its post-Newtonian predictions, which is beyond the scope of our paper. According to us, alternative approaches to gravity could maybe help to understand apparent modifications of Newton's equation in the solar system [START_REF] Reynaud | Gravity tests in the solar system and the pioneer anomaly[END_REF] and in galactic rotation curves as well [START_REF] Durt | Estimate of the weight of empty space based on astronomical observations quant/ph[END_REF] but this is another story. In the meanwhile, our study suggests that dB-B trajectories and effective gravitation could be observed with collective self-collapsed assemblies of cold atoms [START_REF] Strecker | Formation and propagation of matter-wave soliton trains[END_REF], which has never been done so far. In any case, a virtue of our model is that it has some retrodictive power in the sense that it explains the appearance, in presence of dB-B trajectories, of a pseudo-gravitational interaction in droplets phenomenology, attractive and repulsive as well. Moreover we predict that the interaction scales like v 2 (LAMB + LBMA)cos(k0rAB)/rAB, which can possibly be tested in the lab.. There are two unspecified parameters in our model, at this level, which are the exact ratios between L A(B) and the sizes of the droplets. We expect those to be of the order of unity however, and they can easily be evaluated experimentally.

  Coming back to the single particle case, replacing Ψ hom L by Ψ hom L /(1φ G /c 2 ) in the Schrödinger equation delivers the modified Schrödinger equation

Note that the singularities of this expression in x A 0 and x B 0 are artificial, they result from our discretisation procedure.

In[START_REF] Durt | Generalized guidance equation for peaked quantum solitons: the single particle case[END_REF] we explain how we were brought to impose[START_REF] Colin | Can quantum systems succumb to their own (gravitational) attraction?[END_REF][START_REF] Colin | Crucial tests of macrorealist and semi-classical gravity models with freely falling mesoscopic nanospheres[END_REF][START_REF] Couder | Dynamical phenomena: walking and orbiting droplets[END_REF] that in the present paper we treat as a postulate. Actually in[START_REF] Durt | Generalized guidance equation for peaked quantum solitons: the single particle case[END_REF] we studied the feedback of the pilot wave Ψ L on the soliton or particle φ NL , postulating to begin with that (1,2) is satisfied and also that Ψ = Ψ L • φ NL , while Ψ L is a solution of the homogeneous Schrödinger equation; we argued that this feedback results in conditions[START_REF] Colin | Can quantum systems succumb to their own (gravitational) attraction?[END_REF][START_REF] Colin | Crucial tests of macrorealist and semi-classical gravity models with freely falling mesoscopic nanospheres[END_REF][START_REF] Couder | Dynamical phenomena: walking and orbiting droplets[END_REF] in the appropriate regime.[START_REF] Durt | Generalized guidance equation for peaked quantum solitons: the single particle case[END_REF] is complementary to the present paper in the sense that here we study the feedback of the solitons on the pilot wave.

Acknowledgments

This work benefitted from the support of grants 21326 and 60230 from the John Templeton Foundation and the FQXI project FQXi-RFP-1506. Thanks to C. Champenois and R. Willox for kind comments.


Stéphane Delbruel

Davide Frey
email: davide.frey@inria.fr

François Taïani
email: francois.taiani@irisa.fr

Mignon: a Fast Decentralized Content Consumption Estimation in Large-Scale Distributed Systems

Keywords: Decentralized systems, Content consumption, Estimation

Although many fully decentralized content distribution systems have been proposed, they often lack key capabilities that make them difficult to deploy and use in practice. In this paper, we look at the particular problem of content consumption prediction, a crucial mechanism in many such systems. We propose a novel, fully decentralized protocol that uses the tags attached by users to on-line content, and exploits the properties of self-organizing kNN overlays to rapidly estimate the potential of a particular content without explicit aggregation.

Introduction

User-generated content (UGC) services have grown extremely fast over the last few years [START_REF]Global internet phenomena report: 2h 2013[END_REF][START_REF]LCC. Statistics, viewership[END_REF]. In order to support this growth, current services typically exploit private data centers owned by large companies such as Google, Sony and Amazon. These data centers are further augmented with Content Distribution Networks (CDNs) and caching servers positioned at points-of-presence (PoP) within the infrastructure of Internet Service Providers (ISPs) [START_REF]Google peering and content delivery[END_REF].

This approach tends to favor big players, and to concentrate the industry in the hands of a few powerful actors. For several years now, both academia and practitioners have therefore sought to explore alternative designs to implement social online services in general, and UGC video services in particular. One strategy espouses a fully decentralized organization [START_REF] Androutsellis-Theotokis | A survey of peer-to-peer content distribution technologies[END_REF][START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Huguenin | Content and geographical locality in user-generated content sharing systems[END_REF][START_REF] Kubiatowicz | Oceanstore: An architecture for global-scale persistent storage[END_REF][START_REF] Pujol | The little engine(s) that could: scaling online social networks[END_REF], in which each individual user (through her computer or set-top box) provides resources to implement the system's overall services, including storage [START_REF] Kubiatowicz | Oceanstore: An architecture for global-scale persistent storage[END_REF][START_REF] Ratnasamy | A scalable contentaddressable network[END_REF][START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF], indexing [START_REF] Crespo | Routing indices for peer-to-peer systems[END_REF], queries [START_REF] Bai | Gossiping personalized queries[END_REF][START_REF] Idreos | P2P-diet: An extensible P2P service that unifies ad-hoc and continuous querying in super-peer networks[END_REF], recommendation [START_REF] Baraglia | A peer-to-peer recommender system for self-emerging user communities based on gossip overlays[END_REF][START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Boutet | WhatsUp Decentralized Instant News Recommender[END_REF], caching [START_REF] Frey | Behave: Behavioral Cache for Web Content[END_REF], and streaming [START_REF] Cha | I tube, you tube, everybody tubes: Analyzing the world's largest user generated content video system[END_REF][START_REF] Frey | Heterogeneous gossip[END_REF].

To ensure their scalability, most of these services primarily rely on limited interactions (e.g. with a small set of neighboring nodes) and local information (e.g. users profiles, bandwidth, latency, tags). The use of local information is one of the key reasons why these services scale. Too strong a focus on locality, however, constrains the range of decisions that can be taken by individual nodes, and their ability to adapt to phenomena occurring at a global scale.

In an attempt to address this limitation, we focus, in this paper, on the particular problem of global predictions in large-scale decentralized systems, with an application to the placement of videos in a decentralized UGC video service. Being able to predict where a new video is likely to be consumed is a crucial ability for decentralized services that often lack the tightly integrated global infrastructure of large players. It can help inform storage and caching decisions in order to best exploit the resources these services can rely on [START_REF] Scellato | Track globally, deliver locally: Improving content delivery networks by tracking geographic social cascades[END_REF][START_REF] Sastry | Buzztraq: Predicting geographical access patterns of social cascades using social networks[END_REF].

More precisely, we consider the problem of a newly uploaded videos that must be stored and replicated within a peer-to-peer system in the countries where it is more likely to be viewed. We have shown in a previous work that the tags attached to videos are a good predictor of a video's view distribution [START_REF] Delbruel | Exploring the use of tags for georeplicated content placement[END_REF]. Unfortunately, individual peers do not by default have access to the past videos and tags consumed within individual countries, and this information can be costly to aggregate explicitly. In this paper, we therefore propose Mignon, a novel decentralized content consumption estimation mechanism that is fast and scalable and eschews the need for any global aggregation. Mignon exploits the properties of self-organizing similarity overlays [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF][START_REF] Voulgaris | Epidemic-style management of semantic overlays for content-based searching[END_REF] and delivers estimations that are on average within 0.6% (respectively 13%) of an exhaustive view aggregation on a MovieLens (respectively YouTube) dataset.

Problem Statement and Related Work

We consider a global decentralized P2P UGC service, in which each user contributes her resources to the system. As we focus on video placement and view prediction, we assume our service can store and retrieve videos from users' machines [START_REF] Saroiu | Measuring and analyzing the characteristics of napster and gnutella hosts[END_REF][START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF][START_REF] Ratnasamy | A scalable contentaddressable network[END_REF]. As is now common in many on-line services, we also assume that the past activity of users can be used to predict their affinity with new content (Fig. 1). More precisely, the individual devices of users (Alice and Bob, label 1) store the list of videos they have consumed (their video profile, label 2). Each video is associated with a set of descriptive tags provided by its uploading user [START_REF] Greenaway | Tagging youtube -a classification of tagging practice on youtube[END_REF][START_REF] Geisler | Tagging video: conventions and strategies of the youtube community[END_REF] (label 3). Here for instance, Alice has viewed a BBC video with the tag 'news' ( ), and a video on environmental protection with the tags 'news', and 'animals' (

). The tags of the videos viewed by a user form her tag profiles (label 4): [ :2, :1] for Alice and [ :1] for Bob.

We rely on a tag-based affinity function f that measures a user's affinity with new videos (5) [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Delbruel | Exploring the use of tags for georeplicated content placement[END_REF]. The only assumptions we make about f is that its result is correlated with the probability that this user will watch the video (6).

Placing new videos: the prediction problem

When uploading a new video, copies of this video should ideally be placed in storage locations close to where it might be most consumed. This is because the viewing patterns of many videos in UGC services present clear geographic trends [START_REF] Brodersen | YouTube around the world: Geographic popularity of videos[END_REF], which are strongly correlated with a video's tags [START_REF] Delbruel | Exploring the use of tags for georeplicated content placement[END_REF]. for instance how the tags "bollywood " and "favela" follow clearly distinctive geographic distributions in a Youtube dataset analyzed in an earlier work [START_REF] Delbruel | Exploring the use of tags for georeplicated content placement[END_REF]. Correctly predicting the geographic distribution of a video's views is particularly important in decentralized systems that often lack the caching infrastructure of large integrated services. In Fig. 2 for instance, Dave must decide whether to store his new video in the USA or in France. This decision should be driven by the video's likely future popularity in both countries, which can be estimated as the sum of all user affinities in each country.

Obtaining this aggregated sum efficiently is unfortunately challenging in a large P2P system. Dave could trigger a P2P aggregation in the USA and France [START_REF] Montresor | Robust aggregation protocols for large-scale overlay networks[END_REF], but such an approach would require computing the similarity between the new video and every user in each country, a slow and costly operation.

In this paper, we therefore investigate how such a sum can be efficiently, rapidly, and accurately estimated in a fully decentralized system while involving only a small subset of the users in a given country.

Related work

A number of works have been proposed to perform aggregation operations in decentralized peer-to-peer systems [START_REF] Jelasity | Epidemic-style proactive aggregation in large overlay networks[END_REF][START_REF] Montresor | Robust aggregation protocols for large-scale overlay networks[END_REF]. These works typically use an epidemic procedure in which nodes repeatedly interact with other random peers in a pair-wise fashion. They often further rely on a peer-sampling protocol [START_REF] Jelasity | Gossip-based peer sampling[END_REF][START_REF] Voulgaris | Cyclon: Inexpensive membership management for unstructured p2p overlays[END_REF] to maximize the diversity of interactions between peers. Following this strategy, averaging can for instance be implemented in the following manner: all peers p i start with an initial value v 0 i . A given peer p i then periodically selects another random peer p j returned from the peer sampling service, and both peer update they respective value to (vi+vj ) 2

. This procedure guarantees that all nodes progressively converge to a value that is increasingly close to the average of all initial values 1 N N i=1 v i . The number of rounds required to attain a given aggregate accuracy primarily depends on the distribution of the original data [START_REF] Jelasity | Epidemic-style proactive aggregation in large overlay networks[END_REF].

This aggregation procedure can be used to estimate the size of a network, with all nodes but one starting with a value of 0, and one node (the initiator) a value of 1: all nodes will converge to a value of 1 N [START_REF] Montresor | Robust aggregation protocols for large-scale overlay networks[END_REF]. Combined with the above averaging protocol, such a size estimation can provide an estimate of the sum of the original peer values N i=1 v i . Unfortunately, this approach is ill-suited to our case, as it would require the tags of every new video to be propagated to the entire network before any estimation may take place, incurring both additional latency and high network costs for every new load.

Fast Decentralized Sum Estimation

Instead of launching an expensive aggregation every time a new video is uploaded, we propose a cheaper mechanism to estimate the aggregated affinity of a video. Our approach exploits a similarity-driven overlay [START_REF] Bertier | The gossple anonymous social network[END_REF] that interconnects all the users in a country. In the following we first briefly describe similarity-driven overlays, and then present the details of our approach.

Self-organizing overlays

Similarity-driven overlay networks organize peers according to their similarity [START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF], with a wide range of applications [START_REF] Bertier | The gossple anonymous social network[END_REF][START_REF] Bai | Gossiping personalized queries[END_REF][START_REF] Boutet | WhatsUp Decentralized Instant News Recommender[END_REF][START_REF] Frey | Behave: Behavioral Cache for Web Content[END_REF][START_REF] Dick | Flower-cdn: a hybrid p2p overlay for efficient query processing in cdn[END_REF]. In this work, we consider gossip-based similarity driven overlays, whose working is depicted in Figures 345. The machine of each user holds the user's profile: in our case the list of viewed videos and their attached tags (Fig. 3). Starting from random neighborhoods This construction uses two greedy mechanisms (Figures 4 and5). With the first mechanism, a peer (e.g. Alice) regularly polls an underlying and constantly evolving Random Peer Sampling (RPS) overlay [START_REF] Jelasity | Gossip-based peer sampling[END_REF] to obtain a set of random peers from the rest of the system. In Fig. 4 for instance, Alice might discover Dave through the RPS layer. If Dave turns out to be a better neighbor for Alice than Bob (upper self-organizing layer), Alice will replace Bob by Dave in her neighborhood. This stochastic process ensures that the system eventually converges to an optimal state. The convergence might however be very slow.

To speed up convergence, peers use a second 'neighbor-of-neighbor ' mechanism (Fig. 5). The intuition is that if Alice is similar to Bob, and Bob to Carl, then Carl might be similar to Alice. Peers therefore periodically exchange their current neighbors lists (Step 1 in Fig. 5), and use the new peers they discover to optimize their neighborhoods (Step 2). This mechanism greatly accelerates convergence (usually in log(N ) rounds [START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF]), but might get stuck in a local minimum, and is therefore complementary to the stochastic mechanism of Fig. 4.

Mignon: Fast Decentralized Estimation

In this paper we propose Mignon, a protocol that employs the similarity-driven overlay we have just described to estimate the aggregated affinity of a new video with all the users in a country. To this end, all the users in a country participate in a similarity-driven overlay whose similarity function is the affinity function f of Fig. 1. When one of these users uploads a new video, v, she additionally creates a new virtual peer P v , whose profile contains the tags associated with v.

Our estimation problem simply consists in computing the sum of the similarities between P v and every other user in the country. To compute this sum exhaustively, either at peer P v or using a standard aggregation protocol, we would either have to collect the profiles of all other nodes at P v , or disseminate the profile of P v to every other node. In both cases, the delay and the resulting network cost would be prohibitive for very large networks.

Instead, in Mignon, the uploading user simply impersonates the virtual peer by having it join the similarity-based overlay. In a very short time (generally logarithmic in the size of the network [START_REF] Jelasity | T-man: Gossip-based fast overlay topology construction[END_REF]), P v obtains its k-nearest neighbors. Once this happens, the uploading user exploits the content of the KNN and RPS neighborhoods of P v to estimate the video's aggregated affinity without any further network exchanges.

The key to the approach consists in considering the affinity values of users found in the KNN and RPS views of P v as samples taken from a monotonically decreasing function. Fig. 6 shows this pictorially in two examples. The black vertical lines represent the affinity values of the users found in the KNN and RPS views of P v . Mignon uses these values to interpolate the function's shape, from which we derive an aggregated affinity by integration. The values obtained from the KNN neighbors constitute the first k consecutive samples, while those in the RPS represent randomly chosen samples distributed along the rest of the x-axis. To associate each of them with an x-coordinate (which the RPS does not indicate), we rely on a network-size estimation protocol [START_REF] Merrer | Peer to peer size estimation in large and dynamic networks: A comparative study[END_REF] that provides us with the length of the x-axis, and assume that the RPS samples are equally spaced along this axis.

It should be noted that the inherent cost of size-estimation does not offset the benefits provided by our approach in terms of delay and network cost. First, the size estimation protocol does not need to be run for every video upload. Rather, in a setup consisting of set-top boxes that are almost always on, the protocol can run every few days. Second, protocols like Sample & Collide [START_REF] Merrer | Peer to peer size estimation in large and dynamic networks: A comparative study[END_REF] can estimate the size of the network within a reasonable error margin at a minimal cost. We evaluate the impact of protocols like Sample & Collide in Section 4.3. In the following we describe the two interpolation techniques we use in Mignon.

Trapezoidal rule. The first technique we consider is the trapezoidal rule, a wellknown method for approximating the integral of a function. The rule replaces the function to be integrated with a sequence of linear segments and computes the integral as the sum of the areas of the corresponding trapezoids.

Polynomial Interpolation. As a second estimation mechanism, we consider a polynomial interpolation. Specifically, we compute the polynomial of degree n-1 that goes through all of the n samples in the KNN and RPS. We then use this polynomial to compute the values associated with the users that are not among the samples.

We evaluate Mignon on two distinct datasets. The first consists of an adaptation of the YouTube dataset we introduced in our previous work [START_REF] Delbruel | Exploring the Geography of Tags in Youtube Views[END_REF][START_REF] Huguenin | Content and geographical locality in user-generated content sharing systems[END_REF]. It contains 590, 897 videos, each associated with a set of tags -11.18 per video on average, with a total of 705, 415 distinct tags-and with a popularity vector that provides an estimated number of views per country. We extracted videos and tags directly from YouTube, while we computed the number of views for videos and tags by crossing YouTube data with information from Alexa Internet Inc. 3 as described in [START_REF] Delbruel | Exploring the Geography of Tags in Youtube Views[END_REF], with the following equation.

views(v)[c] pyt [c] × pop(v)[c] γ∈World pyt [γ] × pop(v)[γ] × tot_views(v) (1)
Where views(v)[c] is the number of views of video v in country c, p yt [c] is the proportion of Youtube views in country c at the time our data set was collected, and pop(v)[c] is a popularity vector issued from our ground hypothesis in [START_REF] Delbruel | Exploring the Geography of Tags in Youtube Views[END_REF], i.e. a number proportional to the share of video v's views in country c. To evaluate Mignon, we "reinterpreted" this dataset by considering each country as if it was a single user. Our modified dataset therefore consists of 257 users in a single country.

Our second dataset, MovieLens, consists of a trace from a movie recommendation system4 . It contains a set of movies, each associated with a vector of ratings (1 to 5 integers) by a subset of the users, and a set of n pairs, each consisting of a tag and a real-valued relevance score. The rating R u (m) expresses the interest of a user u in movie m, while the relevance r m (t) score expresses the importance of a tag t for a given movie m. Based on this information, we compute the interest score u t of a user u for a tag t as follows.

u t = 1 n n m=1 (r m (t) * R u (m)) (2)
Since we want to evaluate Mignon's ability to estimate the aggregation of a score value, we consider a synthetic set of new "videos", whose profile only comprises a single tag taken from the dataset. For each such video v, we first select the set of users in its KNN and RPS views, and then compute its affinity with these users. We use this sample of affinity values to produce an estimate (noted âv ) of the video's aggregated affinity with all the users in the system (which we note a v ). To assess the performance of different estimation techniques, we define an estimation ratio: ER v = âv av . We evaluate ER v in a variety of configurations on each of our datasets. Let n be the number of tags in a dataset (and hence of synthetic videos), we present the distribution of ER v , its mean ER = 1 Figure 6 exemplifies the affinity score distribution of particular tags (interpreted as videos) in each of the two dataset. The curve depicts the affinity score of each user for the tag in decreasing order, while the vertical bars represent the data available in the KNN and RPS views.

Accuracy Comparison

We start our evaluation by comparing the results obtained by Mignon with those obtained by three baseline approaches that exploit either the KNN or the RPS views but not both. For Mignon, we consider the two estimation techniques presented in Section 3.2 (the Trapezoidal and Polynomial interpolations). For the baselines, we tested both these techniques as well as linear and quadratic regression and selected the three that obtained the best performance. Specifically, KNN-Trapezoid applies the trapezoid rule on a KNN view without using the RPS, RPS-Trapezoid also applies the trapezoid rule but on an RPS view with no KNN, while RPS-Mean simply computes the average similarity of the nodes in the RPS view and multiplies it by the size of the network. We configured our techniques to use a KNN view size of 15 and an RPS size of 10, while all the baselines use a single view (RPS or KNN) of size 25.

Figure 7 shows the results on both of our datasets. Figure 7a depicts the the error on the mean estimation ratio, that is |ER -1|, and shows that combining the KNN and the RPS views allows Mignon to adapt to multiple data sets. Specifically, both the Trapezoidal rule and Polynomial interpolation obtain very good estimates on both datasets with an error on the mean ratio respectively of 0.06 (6%) and 0.01 (1%) on MovieLens and of 0.143 (14.3%) and 0.114 (11.4%) on YouTube. The baselines, on the other hand, can achieve good performance on one of the datasets but not on both. KNN-Trapezoid achieves a very low error of 0.09 (9%) on YouTube, but a very high error of 0.7 (70%) on MovieLens. RPS-Mean achieves a very low error of 0.02 (2%) on MovieLens but a high error Figure 7b completes the picture by showing the standard deviation of the estimation ratio. Again, Mignon obtains low standard deviations on both data sets, contrary to RPS-Trapezoid and RPS-Mean. KNN-Trapezoid also achieves good standard deviations on both dataset, but with a very high mean error on MovieLens (Figure 7a).

Sensitivity Analysis

Now that we have shown the effectiveness of Mignon's estimation approach on multiple datasets, we analyze how the KNN and RPS views impact its performance. We present our results in the form of whisker plots in Figures 8 and9. Each box in the plot covers the values between the lower and the upper quartiles; the point in the box represents the mean, while the line the median. The endpoints of the whiskers represent the lowest datum still within 1.5 * InterQuartile Range (IQR) of the lower quartile, and the highest datum still within 1.5 * IQR of the upper quartile, while the points outside the whiskers represent outliers. views slightly tend to overestimate the total affinity, while large RPS views slightly tend to underestimate it, with the best performance being achieved with a KNN view of 15 and an RPS view of 10. Additional tests (results not shown for space reason) showed that this results primarily from the size of the RPS view. Varying the KNN size with a constant RPS size has almost no impact, while varying the RPS size with a constant KNN size results in overestimation with few RPS nodes and in underestimation with too many RPS nodes.

Trapezoidal rule.

Figure 8b complements the above results with the performance of the Trapezoid rule on the YouTube dataset. Again, we obtain the best performance with a KNN-to-RPS ratio of 3/2. With a KNN view of 15 and an RPS view of 10, the mean estimation ratio settles at 1.14. Moreover, slightly smaller or slightly larger KNN-to-RPS ratios impact this result only to a limited extent. In our tests, we observed that this results from the fact that when one view remains constant, performance consistently improves when increasing the size of the other.

Polynomial interpolation. Next, we evaluate the effectiveness of Mignon using polynomial interpolation. To this end, we used the Gregory-Newton interpolation algorithm as implemented in SciPy. Figure 9 shows the results. Both datasets exhibit similar behaviors. For low RPS sizes, results resemble those obtained with the trapezoid rule, with the best performance being achieved with an RPS of 10 and a KNN of 15. However, results start diverging as soon as the RPS size goes beyond 15. We experimentally verified that this also occurs when increasing the RPS size with a constant KNN size, but not when increasing the KNN size with a constant RPS size.

To understand the high variability associated with high RPS sizes, we examine two runs of the Gregory-Newton interpolation algorithm in Figure 10. Figure 10a shows a run with 10 RPS nodes, while Figure 10b shows one with 30. In both figures, the diamonds represent the real abscissas of the samples on the curve, while the crosses represent those taken into account by our protocol (see Section 3.2). For KNN samples, the two coincide (points at the extreme left of the curve), but for the RPS the difference can be very large. This, together with the numerical instability of the Gregory-Newton's method causes oscillations at the right end of the curve. Some oscillations are visible even with an RPS of 10. But with an RPS of 30, they completely disrupt the estimation.

Influence of Sample & Collide

We now assess the impact of errors on the network-size estimation. As previously stated, nodes do not need to recompute the size of the network for every new upload as we assume the network to be relatively stable. Nonetheless, it is possible to limit the cost of size estimation by means of protocols like Sample & Collide [START_REF] Massoulié | Peer counting and sampling in overlay networks: Random walk methods[END_REF]. Such a protocol yields an estimate with a 10% error at a very limited network cost. We estimate the impact of this error in Table 2 where we shows the absolute value of the error on the mean estimation ratio for both Mignon's approaches in the presence of a positive or negative error on the estimation size. The data shows that the error on the network size has almost no impact on YouTube, and a relatively low one on MovieLens.

Convergence speed

We conclude by evaluating the time required to compute the estimate using Mignon. First, let us consider a baseline system that would simply compute the In this paper, we have proposed Mignon, a new protocol to rapidly estimate the aggregate affinity of a newly uploaded video in a community of users in a fully decentralized manner. Our proposal avoids an explicit and costly aggregation by relying on the properties of similarity-based self-organizing overlay networks, and can be used to decide where to place videos in a decentralized UGC system. By eschewing the need for a central support infrastructure, our approach hints at the possibility of fast reactive aggregate analytics in decentralized systems. This may be useful both to promote alternatives to the cloud-centered model of current UGC video services, but also to improve hybrid P2P/cloud architectures [START_REF] Kreitz | Spotify -large scale, low latency, P2P music-on-demand streaming[END_REF][START_REF] Zhao | Peer-assisted content distribution in Akamai NetSession[END_REF] by offloading complex adaptive tasks to the P2P part of a hybrid system.

Fig. 1 :

 1 Fig. 1: Using tags to predict users' affinity with a new video

Fig. 2 :

 2 Fig. 2: Placing new videos based on aggregated affinity

Fig. 3 :Fig. 5 :

 35 Fig. 3: A self-organizing overlay

Fig. 6 :

 6 Fig. 6: Interest curve for MovieLens(a) and YouTube(b) datasets. Black vertical lines represent KNN and RPS samples.

MFig. 7 :

 7 Fig. 7: Evaluation of the error and the standard deviation for both datasets MovieLens and YouTube

Figure 8 Fig. 8 :

 88 Fig. 8: Fast Decentralized Area Estimation using the trapezoid rule in the Movielens dataset(a) and YouTube dataset(b).

2/23 5 /Fig. 9 :

 59 Fig. 9: Fast Decentralized Area Estimation using Polynomial interpolation in the Movielens dataset(a) and YouTube dataset(b).

Table 1 shows

 1

	Users	Video Profiles	Tags	Tag Profiles
	Alice
	Bob

Table 1 :

 1 Top 3 countries for bollywood (left) and favela (right)

	country	#views %age	country	#views %age
	India	200,956,055 39.8%	Brazil	19,834,633 47.9%
	United-States	124,461,447 24.7%	United-States	14,468,608 34.9%
	United-Kingdom 29,506,586 5.8%	United-Kingdom 1,701,496 4.1%

http://www.alexa.com/siteinfo/youtube.com

www.movielens.org

sum of the affinities of the uploaded video with all the other nodes in the country. Such a system would either require the uploading node to contact each other node in the country to compute its affinity, or it would have to disseminate the video's profile so that other nodes could evaluate the video's affinity with them. Both of these approaches would clearly be difficult to scale to large numbers of nodes and their convergence time would be comparable, if not worse, than that required by a KNN protocol to converge from a completely random configuration.

Mignon, on the other hand, takes advantage of the presence of an already converged KNN protocol. This overlay allows the uploading node to quickly reach its closest neighbors. To evaluate this difference, we counted the number of gossip cycles required by a KNN protocol to reach convergence from scratch with 6000 nodes. In each cycle, a node contacts one other node, and is, on average, contacted by another one. We then added one random node, and counted the cycles it took to reach convergence again. Convergence from scratch took between 150 and 190 gossip cycles, while convergence after adding a node to an already converged network took an order of magnitude less (10 -20).