Konstantin Avrachenkov

Nelly Litvak

Vasily Medyanikov

Marina Sokol

Alpha current flow betweenness centrality

Introduction

A class of centrality measures called betweenness centralities reflects degree of participation of edges or nodes in communication between different parts of the network. The first notion of betweenness centrality was introduced by Freeman [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF]. Let s, t ∈ V be a pair of nodes in an undirected graph G = (V, E). (In the present work we restrict our consideration to undirected graphs.) We denote |V | = n, |E| = m, and let d v be the degree of node v. Let σ s,t be the number of shortest paths connecting nodes s and t and denote by σ s,t (e) the number of shortest paths connecting nodes s and t passing through edge e. Then betweenness centrality of edge e is calculated as follows:

C B (e) = 1 n(n -1) s,t∈V σ s,t (e) σ s,t . (1)
Computational complexity of the best known algorithm for computing the betweenness in [START_REF] Aldous | Reversible Markov chains and random walks on graphs[END_REF] is O(mn) [START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF]. This limits its applicability for large graphs.

One of shortcomings of the betweenness centrality in [START_REF] Aldous | Reversible Markov chains and random walks on graphs[END_REF] is that it takes into accounts only the shortest paths, ignoring the paths that might be one or two steps longer, while the edges on such paths can be important for communication processes in the network. In order to take such paths into account, Newman [START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF] and Brandes and Fleischer [START_REF] Brandes | Centrality measures based on current flow[END_REF] introduced the current flow betweenness centrality (CF-betweenness). In [START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF][START_REF] Brandes | Centrality measures based on current flow[END_REF] the graph is regarded as an electrical network with edges being unit resistances. The CF-betweenness of an edge is the amount of current that flows through it, averaged over all source-destination pairs, when one unit of current is induced at the source, and the destination (sink) is connected to the ground. This exploits the well known relation between electrical networks and reversible Markov chains, see e.g., [START_REF] Aldous | Reversible Markov chains and random walks on graphs[END_REF][START_REF] Doyle | Random walks and electric networks[END_REF].

The computational difficulty of Betweenness and the CF-betweenness is that the computations must be done over the set of all source-destination pairs. The best previously known computational complexity for the CF-betweenness is O(I(n -1) + mn log n) where I(n -1) is the complexity of the inversion of matrix of dimension n -1.

In the present work we introduce new betweenness centrality measures: αcurrent flow betweenness (α-CF betweenness) and its truncated version. The main purpose of these new measures is to bring down the high cost of the CFbetweenness computation. Our proposed measures are very close in performance to the CF-betweenness, but they are comparable to the PageRank algorithm [START_REF] Brin | The anatomy of a large-scale hypertextual Web search engine[END_REF] in their modest computational complexity. Our goal is to provide and analyze efficient algorithms for computing α-CF betweenness and truncated α-CF betweenness, and to compare the α-CF betweenness to other centrality measures.

Alpha current flow betweenness

We view the graph G as an electrical network where each edge has resistance α -1 , and each node v is connected to ground node n + 1 by an edge with resistance

(1 -α) -1 d -1
v . This is in the spirit of PageRank. Indeed, the current (probability flow) is inversely proportional to the resistance. Thus, the fraction α of the current from node v flows to the network, while fraction (1 -α) of the current is directed to the sink. Since the graph is undirected, we use a convention that (v, w) and (w, v) represent the same arc in E, but depending on the chosen direction the current along this arc is considered to be positive or negative.

Assume that a unit of current is supplied to a source node s ∈ V , and there is a destination node t ∈ V connected to the ground. Let ϕ (s,t) v denote the absolute potential of node v ∈ V , if s is the source and t is the destination. Assume without loss of generality that s = 1 and t = n (ϕ

(1,n) n = ϕ (1,n) n+1 = 0, i.e.
, we set the ground potential to zero). The vector of absolute potentials of the other nodes ϕ (1,n)

= [ϕ (1,n) 1 , ..., ϕ (1,n) n-1 ]
T is a solution of the following system of equations (Kirchhoff's current law):

[ D -α Ã]ϕ (1,n) = b, (2)
where D and à are the degree and adjacency matrices of the graph without node n and b = [1, 0, ..., 0] T , see e.g., [START_REF] Brandes | Centrality measures based on current flow[END_REF].

In the following theorem we demonstrate that we do not need to solve a separate linear system for each source-destination pair, it suffies to invert the coefficient matrix [D -αA].

Theorem 1 The voltage drop along the edge (v, w) is given by

ϕ (s,t) v -ϕ (s,t) w = (c s,v -c s,w ) + c s,t c t,t (c t,w -c t,v ), (3)
where (c v,w ) v,w∈V , are the elements of the matrix C = [D -αA] -1 .

Proof: Assume again without loss of generality that s = 1 and t = n. The matrix [D -αA] can be written in the following block structure

D -αA = D -α Ã -αã -αã T d n , with ã = [a 1,n , a 2,n , . . . , a n-1,n ] T .
Then, divide accordingly the elements of the inverse matrix

C = [D -αA] -1 = C c cT c n,n .
Writing the relation [D -αA]C = I in the block form yields

[ D -α Ã] C -αãc T = I, (4)
[ D -α Ã]c -αãc n,n = 0. ( 5
)
Premultiplying equation ( 4) by [ D -α Ã] -1 , we obtain

[ D -α Ã] -1 = C -α[ D -α Ã] -1 ãc T . (6)
And premultiplying ( 5) by [ D -α Ã] -1 , we obtain

α[ D -α Ã] -1 ã = 1 c n,n c. ( 7
)
Combining both equations ( 6) and [START_REF] Doyle | Random walks and electric networks[END_REF] gives

[ D -α Ã] -1 = C - 1 c n,n cc T , and hence ϕ (1,n) = [ D -α Ã] -1b = C•,1 - c1,n
cn,n c. Thus, we can write

ϕ (1,n) v -ϕ (1,n) w = (c v,1 -c w,1 ) + c 1,n c n,n (c w,n -c v,n )
The above expression is symmetric and can be rewritten for any source-target pair (s, t). That is,

ϕ (s,t) v -ϕ (s,t) w = (c v,s -c w,s ) + c s,t c t,t (c w,t -c v,t ).
Furthermore, since matrix C is symmetric for undirected graphs, we can rewrite the above equation as

ϕ (s,t) v -ϕ (s,t) w = (c s,v -c s,w ) + c s,t c t,t (c t,w -c t,v ),
which completes the proof.

The potentials ϕ (s,t) v , v, s, t ∈ V , have a clear probabilistic interpretation. Take again s = 1 and t = n. Then from (2) we readily obtain

ϕ (1,n) v = e T v [ D -α Ã] -1 b = e T v [I -α P ] -1 D-1 b, (8)
where e v is a v-th standard basis column vector, and P is the transition probability matrix for a simple random walk on G with absorption in n. Compare this to the well-known expression for the Personalized PageRank vector π(v) = (π 1 (v), . . . , π n (v)) with teleportation preference concentrated in v and damping factor α:

π(v) = (1 -α)e T v [I -αP ] -1 . Note that the vector π(v) = (1 -α)e T v [I -α P ] -1 is very similar to π(v), except it nullifies the con- tribution of node n. Now, recall that b = (1, 0, . . . , 0) T to obtain ϕ (1,n) v = (1 -α) -1 π1 (v)d -1
1 . Furthermore, let 1 be a column vector of ones. Recall that the PageRank vector with uniform teleportation can be written as π = 1-α n 1 T [I -αP ] -1 , and define a similar vector π =

1-α n 1 T [I -α P ] -1 . Then v∈V ϕ (1,n) v = n(1 -α) -1 π1 d -1 1 .
It is well-known (see e.g., [START_REF] Grolmusz | A note on the pagerank of undirected graphs[END_REF] and references therein) and is also confirmed by our experiments that the PageRank of a node in an undirected graph is strongly correlated to the degree of the node. Thus, with any choice of the source, the sum of the potentials is of similar magnitude, except for the cases when the destination node has a large contribution into the PageRank mass of the source. Finally, we note that the source node has the highest potential, and from [1, Chapter 3, Section 3] we find

ϕ (1,n) 1
= [P (random walk returns to node 1 before absorption)] -1 = E(# returns to node 1 before absorption). Now we are ready to define α-CF betweenness. The current

I (s,t) e through edge e = (v, w) is equal to α(ϕ (s,t) v -ϕ (s,t) w ). Let x (s,t) e = |ϕ (s,t) v -ϕ (s,t) w |, (v, w) ∈ E,
be the difference of potentials, that determines the absolute value of the current on the edge. The α-CF betweenness of edge e is defined by

x α e = 1 n(n -1) s,t∈V,s =t x (s,t) e , e ∈ E. (9)
Further, for each node v ∈ V its α-CF betweenness is defined as the sum of the α-CF betweenness scores of its adjacent edges:

α-CF betweenness(v) = (v,w)∈E x α (v,w) , v ∈ V. ( 10
)
With this definition, the node is central if a relatively large amount of current flows from this node to the network. This is in accordance to the original CFbetweenness of [START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF][START_REF] Brandes | Centrality measures based on current flow[END_REF], except we introduced the additional sink ground node n + 1. This mitigates the computational issues because the original CF-betweenness requires the inversion of the ill-conditioned matrix [ D -Ã], while for computing α-CF betweenness we need to invert the matrix [D -αA], which is a well posed problem, and has many efficient solutions (e.g., power iteration and Monte Carlo methods). In fact, as we shall show below, we need to obtain just a few rows of the inverse matrix [D -αA] -1 . In the rest of the paper we will discuss the computation and the properties of the α-CF betweenness.

Computation of α-CF betweenness

Due to the presence of the auxiliary node n + 1, the value of x (s,t) e on the righthand side of ( 9) can be computed efficiently with high precision for any sourcedestination pair. However, the summation over all n(n -1) pairs is a problem of prohibitive computational complexity even for graphs of modest size. The solution is to perform the computations for sufficiently many source-destination pairs. Since all source-destination pairs contribute equally in [START_REF] Grolmusz | A note on the pagerank of undirected graphs[END_REF] we choose to sample them uniformly at random. This results in the next algorithm for computing the α-CF betweenness.

Algorithm 1.

1. Select a set of pairs of nodes (s i , t i ), i = 1, ..., N , uniformly at random; 2. For each s i and t i , i = 1, ..., N compute the rows c si,• , c ti,• (this can be done either by power iteration or by Monte Carlo algorithm); 3. For each edge e = (v, w) and each pair (s i , t i ), use (3) to compute x (si,ti) e .

x (si,ti) e = |ϕ (si,ti) v -ϕ (si,ti) w |.
Since we chose the pairs (s i , t i ) uniformly at random then for every edge e, xα e is just a sample average where all values are between zero and one. Then using the standard approach for the analysis of the series of independent random variables we have the following result.

Theorem 2 Algorithm 1 approximates the alpha current flow betweenness in O(m log(n)ε -2 log(ε)/ log(α)) time to within an absolute error of ε with arbitrarily high fixed probability.

Proof: In addition to the proof of Theorem 3 in [START_REF] Brandes | Centrality measures based on current flow[END_REF] we just need to note that we can compute Personalized PageRank with precision ε in O(log(ε)/ log(α)) power iterations.

Truncated α-CF betweenness

In the experiments we noticed that the values x (s,t) e have a high variance, which results in poor precision when evaluating x α e . A closer analysis revealed that the edges adjacent to the source s receive large values of x (s,t) e , especially when e = (v, s), where v has degree 1, so (v, s) is its only edge, and s has a large degree. This can be explained using the random walk interpretation. Consider a PageRank-type random walk on G. At each node, with probability α, the random walk traverses a randomly chosen edge of this node, and with probability 1-α it jumps to the sink, node n + 1. Denote by T B the number of steps of the random walk needed to hit set B. It follows from Proposition 10 of [1, Chapter 3] that ϕ (s,t) v /ϕ (s,t) s = P v (T {s} < T {t,n+1} ), where P v (•) is a conditional probability given that the random walk starts at v. Hence, if s is the only neighbor of v then ϕ (s,t) v /ϕ (s,t) s = α, the probability of no absorption before reaching s. Thus, |ϕ

(s,t) s -ϕ (s,t) v | = (1 -α)ϕ (s,t) s
, which can be large if e.g. α = 0.8 because ϕ (s,t) s is the largest potential in the network. In contrast, the original CF-betweenness corresponds to α = 1, implying that the current in (v, s) is zero.

This prompts us to introduce the truncated version of α-CF betweenness where for each edge (v, w) we only take into account the scores x (s,t) (v,w) if v, w = s. In Fig. 1 we present log-linear plots of the empirical complementary distribution function of x (s,t) (v,w) over all pairs (s, t) (solid line), and its truncated version (dashed line). The plots are given for two edges in the Dolphin social network described in Section 5 below. Nodes 1 and 36 are central in the network, so the high α-CF betweenness of (1,36) is expected. Node 60 has degree 1, so edge (32,60) gains an unwanted high betweenness in the non-truncated version.

Since the truncated α-CF betweenness gives lower scores to the edges connected to nodes of degree 1, one can expect that it has a higher correlation with CF-betweenness, especially for middle-range values of α. This is confirmed below in Fig. 2. Moreover, the truncated version removes outliers, and does not have large spread in values, thus standard statistical procedures, based on the Central Limit Theorem can be applied. Also, because of the smaller variance, Algorithm 1 achieves a desired precision with a smaller sample of source-destination pairs.

Datasets

We consider the four graphs described below. Dolphin social network. This small graph represents a social network of frequent associations between 62 dolphins in a community living off Doubtful Sound, New Zealand [START_REF] Lusseau | The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations[END_REF].

Graph of VKontakte social network. We have collected data from a popular Russian social network VKontakte. We were considering subgraph representing one of the connected components of people who stated that they were studying at Applied Mathematics -Control Processes Faculty at the St. Petersburg State University in different years. We ran the breadth-first search (BFS) algorithm starting at one specific node of the network and then anonymized the obtained users' data leaving only information about connections between people. Collected network consists of 2092 individuals out of total 8859 denoted the specified faculty in the Education field.

Watts-Strogatz model. As an artificial example, we used a random graph generated by the Watts-Strogatz model. We have chosen this model as it combines high clustering and short average path length, thus different centrality measures give very different results on this graph. For other random models considered (Erdös-Rényi and Barabási-Albert) all measures are highly correlated and behave very similarly to each other.

Enron graph. Enron email communication network is a well known test dataset. It covers all the email communication within a dataset of around half million emails between Enron's employees. The node are e-mail addresses, and an edge appears if an e-mail message was sent from one e-mail to another. Although this graph is small compared to, say, web or Twitter samples, it is already prohibitively large for computing the CF-betweenness in its original form.

Numerical results for α-CF betweenness

To begin with, we compare the two versions of α-CF betweenness (truncated and without truncation) to the CF-betweenness scores defined as in [START_REF] Newman | A measure of betweenness centrality based on random walks[END_REF][START_REF] Brandes | Centrality measures based on current flow[END_REF]. Fig. 2 presents the results for the three smaller graphs, in which the latter measure 1. Datasets characteristics could be computed. As a correlation measure we use the Kendall tau rank correlation. We observe that the truncated version is better correlated with the CF-betweenness when α is not very close to one. As explained above, this is because the high probability of absorption in the auxiliary node n + 1 results in a relatively high current in the edges connected to the source, which is not necessarily the case if absorption is only possible in the destination node.

Next, we demonstrate that we can compute α-CF betweenness in the Enron graph, where the computation of CF-betweenness is infeasible (at least, with our means). We have evaluated α-CF betweenness, non-truncated and truncated, with α = 0.98. We have run Algorithm 1 using N = 20 • 10 6 source-destination pairs. In Fig. 3 we plot the complementary distribution function in log-linear scale, of the score x 0.98 e across the edges. Note that distribution over edges (the left plot in Fig. 3) does not have a large spread of values, except one outlier edge that connects two most important hubs. Since the weights of the edges are comparable, it is to be expected that in this graph the nodes of large degrees are also the ones with highest betweenness. Indeed, the Kendall's tau correlation between α-CF betweenness and degree of the nodes turns out to be 0.808, which is higher than in the three smaller graphs. The reason can be either the graph size or its structure. In future research we will investigate how the CF-betweenness score, e.g. its maximum value across the edges, scales with the graph size in graphs with power law degrees.

We further present correlations between our proposed measures and other measures of betweenness. These are computed on smaller graphs where we could obtain exact values of all presented measures, see Tables 234. For completeness, we have also included PageRank (PR) computed with α = 0.85 and a distancebase centrality measure -Closeness centrality:

C C (v) = n -1 w∈V,w =v d(v, w)
, where d(v, w) is the graph distance between v and w. Betweenness (Between.) is computed as in [START_REF] Aldous | Reversible Markov chains and random walks on graphs[END_REF]. PageRank and the degrees have a higher correlations with the CF-betweenness in real graphs. Recent paper [START_REF] Boldi | Axioms for centrality[END_REF] suggests more measures based on distance, and efficient computation methods for such measures is presented in [START_REF] Boldi | In-core computation of geometric centralities with hyperball: A hundred billion nodes and beyond[END_REF]. In future it will be interesting to compare these new measures to α-CF betweenness.

Centrality measures and network vulnerability

We now consider how well the CF-betweenness and α-CF betweenness can indicate the nodes responsible for maintaining connectivity of a network. We follow the methodology of [START_REF] Holme | Attack vulnerability of complex networks[END_REF]. As measures of connectivity we choose the average inverse distance

< d -1 >= 1 n(n -1) u,v∈V,u =v 1 d(u, v)
and the size of the largest connected component. In the experiment, we remove the top nodes one by one, according to different betweenness measures, and observe how the connectivity of the network changes. In Fig. 4 the results are presented for the inversed average distance.

The results for the social graph VKontakte are especially interesting, because this network turns out to be less vulnerable to the removal of nodes with large degree than nodes with large betweenness and its modifications (CF-betweenness, α-CF betweenness, and truncated α-CF betweenness). On the small Dolphin social network there is no much difference in vulnerability with respect to different centrality measures. Finally, on the artificial Watts-Strogatz graph the CF-betweenness and our proposed two versions of α-CF betweenness find the nodes that are most essential for the network connectivity.

In Fig. 5 we plot the size of the largest connected components against the fraction of removed top-nodes. We do not present the plot for the Watts-Strogatz graph because it remains entirely connected, so the size of its largest connected component equals to the number of remaining nodes irrespectively of which nodes are removed first. For the two real graphs, the CF-betweenness is most efficient in reducing the size of the giant component. On the Dolphin graph, α-CF betweenness performs closely to CF-betweenness, except the interval when 13-18% of nodes are removed. On the graph VKontakte, α-CF betweenness and its truncated version perform comparably to the CF-betweenness. Again, on this graph, degree and Closeness centrality fail to reveal the nodes responsible for good network connectivity. The α-CF betweenness with α = 0.98 appears to be a better indicator for vulnerability than the truncated α-CF betweenness with α = 0.8. The latter however also gives good results, and can be computed easier on large graphs due to the faster convergence of the power iteration algorithm.

We conclude that both α-CF betweenness and truncated α-CF betweenness provide an adequate measure for the role of a node in network's connectivity. Furthermore, their computational costs are lower than for known measures of betweenness, and the computations can be done in parallel easily. Thus, α-CF betweenness can be applied in large graphs, for which computation of other measures of betweenness is merely infeasible.

Fig. 1 .

 1 Fig. 1. The number of pairs s, t with x (s,t) (v,w) > x over all pairs (s, t) (solid line) and only pairs with v, w = s (dashed line).

Fig. 2 .

 2 Fig. 2. Correlations between α-CF betweenness and truncated α-CF betweenness with CF-betweenness as a function of α.

Fig. 3 .

 3 Fig. 3. Distribution of α-CF betweenness scores in the Enron graph, truncated (dashed line) and not truncated (solid line). Left: 10 4 • x 0.98 e for edges e ∈ E. Right: α-CF betweenness (v) for v ∈ V . On the x-axis are the values of α-CF betweenness, on the y-axis the number of edges/nodes with the score larger than x.

Fig. 4 .

 4 Fig. 4. Inverse average distance as a function of the fraction of removed top-nodes according to different betweenness centrality measures.

Fig. 5 .

 5 Fig. 5. The size of the largest connected component as a function of the fraction of removed top-nodes according to different betweenness centrality measures. (same legend as in Fig. 4)

Table 2 .

 2 Kendall tau for centrality measures in Dolphin social network.Note that α-CF betweenness is strongly correlated with CF-betweenness. The Closeness Centrality does not agree well with the CF-betweenness, even the Degree PR Closeness Between. CF αCF(0.8) αCF-tr(0.8) αCF(0.98)

		Degree PR Closeness Between. CF αCF(0.8) αCF-tr(0.8) αCF(0.98)
	Degree	1.000 0.930 0.548	0.665 0.737 0.864	0.855	0.769
	PageRank 0.930 1.000 0.458	0.658 0.733 0.872	0.827	0.757
	Closeness	0.548 0.458 1.000	0.578 0.575 0.515	0.573	0.591
	Between.	0.665 0.658 0.578	1.000 0.829 0.749	0.759	0.828
	CF	0.737 0.733 0.575	0.829 1.000 0.798	0.820	0.939
	αCF(0.8)	0.864 0.872 0.515	0.749 0.798 1.000	0.925	0.838
	αCF-tr(0.8) 0.855 0.827 0.573	0.759 0.820 0.925	1.000	0.876
	αCF(0.98) 0.769 0.757 0.591	0.828 0.939 0.838	0.876	1.000

Table 3 .

 3 Kendall tau for centrality measures in the social graph VKontakte AMCP.

		Degree PR Closeness Between. CF αCF(0.8) αCF-tr(0.8) αCF(0.98)
	Degree	1.000 0.891 0.462	0.526 0.610 0.643	0.581	0.612
	PageRank 0.891 1.000 0.415	0.485 0.565 0.610	0.546	0.567
	Closeness	0.462 0.415 1.000	0.655 0.613 0.647	0.666	0.628
	Between.	0.526 0.485 0.655	1.000 0.853 0.819	0.852	0.857
	CF	0.610 0.565 0.613	0.853 1.000 0.910	0.914	0.979
	αCF(0.8)	0.643 0.610 0.647	0.819 0.910 1.000	0.935	0.923
	αCF-tr(0.8) 0.581 0.546 0.666	0.852 0.914 0.935	1.000	0.930
	αCF(0.98) 0.612 0.567 0.628	0.857 0.979 0.923	0.930	1.000

Table 4 .

 4 Kendall tau for centrality measures in the Watts-Strogatz graph (n=1000, k=12, p=0.150).

This research is partially funded by Inria Alcatel-Lucent Joint Lab, by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672, see www.congas-project.eu, and by the EU-FET Open grant NADINE (288956).


Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Yann Busnel
email: yann.busnel@univ-nantes.fr

Sébastien Gambs
email: sebastien.gambs@irisa.fr

On the Power of the Adversary to Solve the Node Sampling Problem

Keywords: Data Stream, Kullback-Leibler Divergence, Uniform sampling, Freshness, Byzantine adversary

We study the problem of achieving uniform and fresh peer sampling in large scale dynamic systems under adversarial behaviors. Briefly, uniform and fresh peer sampling guarantees that any node in the system is equally likely to appear as a sample at any non malicious node in the system and that infinitely often any node has a non-null probability to appear as a sample of honest nodes. This sample is built locally out of a stream of node identifiers received at each node. An important issue that seriously hampers the feasibility of node sampling in open and large scale systems is the unavoidable presence of malicious nodes. The objective of malicious nodes mainly consists in continuously and largely biasing the input data stream out of which samples are obtained, to prevent (honest) nodes from being selected as samples. First, we demonstrate that restricting the number of requests that malicious nodes can issue and providing a full knowledge of the composition of the system is a necessary and sufficient condition to guarantee uniform and fresh sampling. We also define and study two types of adversary models: (1) an omniscient adversary that has the capacity to eavesdrop on all the messages that are exchanged within the system, and (2) a blind adversary that can only observe messages that have been sent or received by nodes it controls. The former model allows us to derive lower bounds on the impact that the adversary has on the sampling functionality while the latter one corresponds to a more realistic setting. Given any sampling strategy, we quantify the minimum effort exerted by both types of adversary on any input stream to prevent this sampling strategy from outputting a uniform and fresh sample.

Introduction

We tackle the problem of achieving node sampling in large scale open systems in presence of adversarial (Byzantine) nodes. Uniform sampling is a fundamental primitive guaranteeing that any node in a population has the same probability to be selected as sample. This property is of utmost importance in systems in which both the population is continuously evolving and it is impossible to capture the full complexity of the network through global snapshots. By collecting random subsets of information over the network, one can infer at almost no cost global characteristics of the whole population such as its size, its topological organization or its resources. Providing at any time randomly chosen identifiers of nodes in the system is an essential building block to construct large scale distributed applications. Uniform sampling finds its root in many problems such as data collection, dissemination, load balancing, and data-caching. A typical example is load balancing in cluster-based applications, in which choosing a host at random among the available ones is often a choice that provides performance close to that offered by more complex selection criteria [START_REF] Lv | Search and Replication in Unstructured Peer-to-Peer Networks[END_REF]. Another example is epidemic-based applications, in which periodically selecting a few random nodes as neighbors, preserve the connectivity in large-scale environments despite the dynamical aspect of these systems [START_REF] Bertier | On Gossip and Populations[END_REF][START_REF] Bollobás | Random Graphs -2nd Edition[END_REF][START_REF] Demers | Epidemic algorithms for replicated database management[END_REF][START_REF] Massoulié | Peer Counting and Sampling in Overlay Networks: Random Walk Methods[END_REF][START_REF] Stutzbach | On Unbiased Sampling for Unstructured Peer-to-Peer Networks[END_REF].

Providing unbiased (i.e., uniform) sampling in these open systems is a challenging issue. First, this primitive must cope with the continuous change of the network structure caused by nodes departures and arrivals. Furthermore, an important issue that seriously hampers the feasibility of uniform sampling in open and large scale systems is the unavoidable presence of malicious nodes. Malicious (also called Byzantine) nodes typically try to manipulate the system by exhibiting undesirable behaviors [START_REF] Sit | Security Considerations for Peer-to-Peer Distributed Hash Tables[END_REF]. In our context, they try to subvert the system by launching targeting attacks against nodes in the aim of biasing uniformity by isolating honest nodes within the system. This can be quickly achieved by poisoning local views of honest nodes with malicious node ids (cf. Section 3.2). For instance in unstructured graphs, a number of push operations logarithmic in the size of local views is sufficient to fully eclipse honest nodes from the local view of a node [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF], while in structured graphs, a linear number of join operations is required [START_REF] Awerbuch | Group Spreading: A Protocol for Provably Secure Distributed Name Service[END_REF].

Recent works have been proposed to detect and exclude these adversarial behaviors [START_REF] Jesi | Secure Peer Sampling[END_REF][START_REF] Singh | Eclipse Attacks on Overlay Networks: Threats and Defenses[END_REF] by observing that malicious nodes try to get an in-degree much higher than honest nodes in order to isolate them. Extensive simulations [START_REF] Jesi | Secure Peer Sampling[END_REF] have shown that this approach is only highly effective for a very small number of malicious nodes (i.e., in O(log |S|) where |S| is the size of the network S). Otherwise detection mechanisms can display a high rate of false positives (i.e., detect honest nodes as faulty ones).

When the system is harmed by a large number of malicious nodes (e.g, a linear proportion of the nodes of the system), which is definitively a realistic assumption in peer-to-peer systems [START_REF] Sit | Security Considerations for Peer-to-Peer Distributed Hash Tables[END_REF][START_REF] Douceur | The Sybil Attack[END_REF], additional mechanisms are required to prevent targeted attacks from succeeding. Specifically, in structured peer-to-peer systems, analytical studies have shown that artificially inducing churn allows to defend the system against adversarial behaviors, either through competitive induced churn strategies [START_REF] Awerbuch | Towards a Scalable and Robust Overlay Network[END_REF], or through global induced churn [START_REF] Anceaume | Performance evaluation of large-scale dynamic systems[END_REF]. Briefly, the "induced churn" principle states that, by forcing nodes to periodically change their position in the graph, malicious nodes cannot predict the evolution of the state of the system after a given sequence of join and leave operations. By taking advantage of the properties of structured graphs, the authors of both papers have shown that, with high probability, any node is equally likely to appear in the local view of each other honest node after a number of rounds polynomial in the size of the system.

Unfortunately, in unstructured peer-to-peer systems, nodes cannot rely on the topological nature of structured graphs to reject new node ids that do not conform to the imposed distance function in contrast to structured networks [START_REF] Awerbuch | Towards a Scalable and Robust Overlay Network[END_REF][START_REF] Anceaume | Dependability Evaluation of Cluster-based Distributed Systems[END_REF]. To circumvent this issue, Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF] rely on the properties of min-wise independent permutations to eventually converge towards uniform sampling on the node ids. However by construction, this convergence is definitive in the sense that once a random sample has been locally observed it is kept forever as the local sample, thus making this solution static. Intuitively, this lack of adaptivity seems to be the only defense against adversarial behavior when considering bounded resources (i.e., memory and bandwidth).

In this paper we propose a solution that guarantees that each node id received infinitely often has a non-null probability to locally appear as a sample. We coin this property as the freshness sampling property, which we formally define later in the paper. We present a formal analysis of the conditions under which uniform and fresh sampling is feasible. More precisely, the first contribution of this paper is to show necessary and sufficient conditions under which uniform and fresh sampling is achievable in unstructured peer-to-peer systems potentially populated with a large proportion of Byzantine nodes. Let S represent the collection of nodes in the system, and k < 1 the proportion of malicious nodes in S. Let δ be the number of (not necessarily unique) malicious node ids gossiped by malicious nodes during a time interval T s , and Γ vi denotes the local memory of any honest node v i in S. We prove the following assertions.

-If the number δ of (non-unique) malicious ids received at node v i during a given period of time T s is strictly greater than T s -|S|(1k) then, neither uniform sampling nor fresh sampling can be achieved. -If δ ≤ T s -|S|(1k) and the size of the memory Γ vi is greater than or equal to |S| then, both uniform and fresh sampling can be achieved. -If δ ≤ T s -|S|(1k), and |Γ vi | < |S| then, both uniform and fresh sampling cannot be achieved.

Briefly, these conditions show that if the system cannot limit the number of messages an adversary can periodically send, then solving either uniform sampling or fresh sampling is impossible. On the other hand, if this assumption holds and if all honest nodes in the system have access to a very large memory (i.e., linear in the size of the network), then the sampling problem becomes trivially solvable. Unfortunately, we show that both conditions are necessary and sufficient to solve the uniform and fresh sampling problem. As a consequence, these strong conditions highlight the possible damages that adversarial behaviors can cause in large-scale unstructured systems.

We also propose a characterization of the adversarial power towards biasing uniform and fresh sampling. By adopting a statistical view of the input stream and by comparing distributions using metrics such as information divergence, we derive lower bounds on the work that the adversary has to exert to bias this input stream so that uniform and fresh sampling do not hold. We define and study two models of adversary: (1) the omniscient adversary, which has the capacity to eavesdrop on all the messages that are exchanged within the system, and (2) the blind adversary, which can only observe messages that have been sent or received by malicious nodes. To the best of our knowledge, we are not aware of any previous work that has characterized the minimum effort an adversary has to exert to prevent the uniform and fresh sampling to be achievable.

The outline of this paper is the following. First in Section 2, we give an overview of the existing related work on uniform sampling before describing in Section 3, the system model and the assumptions that we make. In Section 4, we present the functionalities of a sampling component and the properties that it should guarantee. Afterwards in Section 5, we identify the two conditions under which uniform and fresh sampling is achievable, while in Section 6 we review some background on information divergence of data streams. The omniscient and blind adversary models, as well as the characterization of the minimum effort the adversary has to exert to bias the sampling properties, are respectively studied in Sections 7 and 8. Finally, we conclude in Section 9 with some open issues.

Related Work

In absence of malicious behaviors, uniform sampling can be achieved through gossip-based algorithms [START_REF] Jelasity | Gossipbased Peer Sampling[END_REF][START_REF] Karp | Randomized Rumor Spreading[END_REF][START_REF] Voulgaris | CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays[END_REF] or through random walks [START_REF] Bollobás | Random Graphs -2nd Edition[END_REF][START_REF] Massoulié | Peer Counting and Sampling in Overlay Networks: Random Walk Methods[END_REF][START_REF] Stutzbach | On Unbiased Sampling for Unstructured Peer-to-Peer Networks[END_REF][START_REF] Zhong | Non-uniform Random Membership Management in Peer-to-Peer Networks[END_REF]. Gossipbased algorithms mainly consist, for each node v i in the system, in periodically selecting some other node v j in v i 's local view and exchanging information. Information can either be pushed to or pulled from other nodes. Over time, information spreads over the system in an epidemic fashion allowing each node to continuously update its local view with fresh node ids. On the other hand, a random walk on a network is a sequential process, starting from an initial node v i , which consists in visiting a node in v i 's neighborhood according to some randomized order. In its simpler form, the next visited node is chosen uniformly at random among the neighbors, while more sophisticated choices are implemented to cope with the bias introduced by topology, specifically towards high degree nodes (for instance, through the Metropolis-Hastings algorithm [START_REF] Awan | Distributed Uniform Sampling in Unstructured Peer-to-Peer Networks[END_REF]). In the literature, different approaches have been proposed to deal with malicious behaviors, each one focusing on a particular adversarial strategy. In this section, we provide a brief overview of these techniques.

In presence of malicious behaviors, different approaches have been proposed according to the considered attacks. Specifically, with respect to eclipse attacks a very common technique, called constrained routing table, relies on the uniqueness and impossibility of forging nodes identifiers. This technique selects as neighbors only the nodes whose identifiers are close to some particular points in the identifier space [START_REF] Castro | Secure Routing for Structured Peer-to-peer Overlay Networks[END_REF]. Such an approach has been successfully implemented into several overlays (e.g., CAN [START_REF] Ratnasamy | A scalable content-addressable network[END_REF], Chord [START_REF] Stoica | Chord: a Scalable Peer-to-Peer Lookup Protocol for Internet Applications[END_REF] or Pastry [START_REF] Rowstron | Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems[END_REF]). More generally, to pre-vent messages from being misrouted or dropped, the seminal works of Castro et al. [START_REF] Castro | Secure Routing for Structured Peer-to-peer Overlay Networks[END_REF] and Sit and Moris [START_REF] Sit | Security Considerations for Peer-to-Peer Distributed Hash Tables[END_REF] on Distributed Hash Tables (DHT)-based overlays combine routing failure tests and redundant routing to ensure robust routing. Their approach has then been successfully implemented in different structuredbased overlays (e.g., [START_REF] Hildrum | Asymptotically Efficient Approaches to Faulttolerance in Peer-to-Peer Networks[END_REF][START_REF] Fiat | Making Chord Robust to Byzantine Attacks[END_REF][START_REF] Anceaume | PeerCube: an Hypercubebased P2P Overlay Robust against Collusion and Churn[END_REF]). In all these previous works, it is assumed that at any time and anywhere in the overlay, the proportion of malicious nodes is bounded and known, allowing powerful building blocks such as Byzantine tolerant agreement protocols to be used among subsets of nodes [START_REF] Fiat | Making Chord Robust to Byzantine Attacks[END_REF][START_REF] Anceaume | PeerCube: an Hypercubebased P2P Overlay Robust against Collusion and Churn[END_REF].

When such an assumption fails, additional mechanisms are needed. For instance, Scheideler et al. [START_REF] Awerbuch | Towards a Scalable and Robust Overlay Network[END_REF] propose the Cuckoo&flip strategy, which consists in introducing local induced churn (i.e., forcing a subset of nodes to leave the overlay) upon each join and leave operations. This strategy prevents malicious nodes from predicting the exact shape of the overlay after a given sequence of join and leave operations. Subsequently to this theoretical work, experiments have been conducted to verify the practical feasibility of global induced churn, which consists in having all the nodes of the overlay periodically leaving their positions [START_REF] Condie | Induced Churn as Shelter from Routing-Table Poisoning[END_REF]. For instance, researchers [START_REF] Anceaume | Dependability Evaluation of Cluster-based Distributed Systems[END_REF] have analyzed several adversarial strategies, and have shown that an adversary can very quickly subvert DHTbased overlays by simply never triggering leave operations.

Jesi et al. [START_REF] Jesi | Secure Peer Sampling[END_REF] propose a random sampling algorithm taking explicitly into account malicious nodes. Their solution assumes that the ultimate goal of the malicious nodes is to mutate the random graph into a hub-based graph, hub for which malicious nodes gain the lead. Once this goal is reached, malicious nodes can very quickly and easily subvert the whole overlay by performing denial-ofservice attacks. Conducting a hub attack mainly consists for malicious nodes in increasing their in-degree. Jesi et al. [START_REF] Jesi | Secure Peer Sampling[END_REF] propose to detect highly popular nodes by extending classic peer sampling services with a module that identifies and blacklists nodes that have an in-degree much higher than the other peers of the overlay. This approach, also adopted in several structured based systems [START_REF] Singh | Eclipse Attacks on Overlay Networks: Threats and Defenses[END_REF] through auditing mechanisms, or in sensor networks [START_REF] Liu | Detecting Malicious Beacon Nodes for Secure Location Discovery in Wireless Sensor Networks[END_REF], is effective only if the number of malicious nodes is very small with respect to the size of the system (i.e., typically of O(log |S|)).

Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF] have recently proposed a uniform but non-fresh node sampling algorithm tolerating up to a linear number of malicious nodes. This sampling mechanism exploits the properties offered by min-wise permutations. Specifically, the sampling component is fed with the stream of node identifiers periodically gossiped by nodes, and outputs the node identifier whose image value under the randomly chosen permutation is the smallest value ever encountered. Thus eventually, by the property of min-wise permutation, the sampler converges towards a random sample. By limiting the number of requests malicious nodes can periodically issue, their solution requires a single node id to be stored in the local memory. Nevertheless, this approach does not satisfy the freshness property as convergence toward a random sample is definitive.

In previous papers whose results form the basis of this article, Anceaume, Busnel and Gambs [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF][START_REF] Anceaume | Characterizing the adversarial power in uniform and ergodic node sampling[END_REF] have shown that imposing strict restrictions on the number of messages sent by malicious nodes during a given period of time and providing each honest node with a very large memory (i.e., proportional to the size of the system) are necessary and sufficient conditions to obtain uniform and fresh (i.e., non definitive) sampling. These findings complement two previous results [START_REF] Busnel | On the Uniformity of Peer Sampling based on View Shuffling[END_REF][START_REF] Gurevich | Correctness of Gossip-Based Membership under Message Loss[END_REF], in which an analysis of the class of uniform and fresh sampling protocols is presented. Both previous works provide a complete analytical proof of a gossip-based protocol achieving both uniformity and freshness. However, in contrast to the present work, adversarial behaviors were not considered.

Finally, taking a completely different approach from the previously mentioned papers based on gossip algorithms or on properties on distance functions, the techniques presented in [START_REF] Yu | SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks[END_REF][START_REF] Yu | SybilGuard: Defending against Sybil Attacks via Social Networks[END_REF] rely on social network topologies to guard against Sybil attacks. Both protocols take advantage of the fact that Sybil attacks try to alter the fast mixing property of social networks to defend against these attacks. However, in presence of malicious nodes with a high degree, the performance of both protocols degrade drastically. Note that the analysis presented in this paper is independent from the way the stream of node ids at each node v i has been generated. For instance, it may result from the propagation of node ids through gossip-based algorithms (namely through push, pull or push-pull mechanisms initiated by v i and its neighbors), from the node ids received during random walks initiated at v i , or even from the induced churn imposed in structuredbased overlays.

System Model

Model of the Network

We consider a dynamic system S populated by a large collection of nodes in which each node is assigned a unique and permanent random identifier from an l-bits identifier space. Node identifiers (simply denoted ids in the following) are derived by applying some standard strong cryptographic hash functions on some intrinsic characteristics of nodes. The value of l (e.g., 160 for the standard SHA-1 hash function) is chosen to be large enough to make the probability of identifiers collision negligible. The system is subject to churn, which is classically defined as the rate of nodes' turnover in the system [START_REF] Godfrey | Minimizing churn in distributed systems[END_REF]. Each node knows only a small set of nodes existing within the system and this knowledge generally varies according to the activity of the system. The particular algorithm used by nodes to update this small set and to route messages induces the resulting overlay topology. In this work, we consider only unstructured overlays, which are assumed to conform with random graphs, in the sense that relationships among nodes are mostly set according to a random process.

Model of the Adversary and Security Mechanisms

A fundamental issue faced by any practical open system is the inevitable presence of nodes that try to manipulate the system by exhibiting undesirable behaviors [START_REF] Sit | Security Considerations for Peer-to-Peer Distributed Hash Tables[END_REF][START_REF] Castro | Secure Routing for Structured Peer-to-peer Overlay Networks[END_REF]. Such nodes are called malicious or Byzantine nodes. In contrast, a node that always follows the prescribed protocols is called honest. Honest nodes cannot a priori distinguish honest nodes from malicious ones, which would otherwise render the problem trivial. In our context, manipulating the system amounts to dropping messages that should normally be relayed by malicious nodes towards honest ones and injecting new messages. Injecting new messages does not mean that malicious nodes have the ability to impersonate honest nodes. Rather, their objective is to judiciously increase the frequency of chosen ids to bias the sample list maintained by nodes. We model malicious behaviors through a strong adversary that fully controls these malicious nodes. More precisely, the adversary model that we consider follows the lines of [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF][START_REF] Jesi | Secure Peer Sampling[END_REF]. However, we distinguish between two types of adversary: the omniscient adversary that is able to eavesdrop all messages exchanged within the system, and the blind adversary that can only observe messages sent or received by malicious nodes.

For both models, we assume that the adversary cannot control more than a fraction k < 1 of malicious nodes in the overlay. We also suppose that the adversary can neither drop a message exchanged between two honest nodes nor tamper with its content without being detected. This is achieved by assuming the existence of a signature scheme (and the corresponding public-key infrastructure) ensuring the authenticity and integrity of messages. The signature scheme enables to verify the validity of a signature on a message (i.e., the authenticity and integrity of this message with respect to a particular node). Recipients of a message ignore any message that is not signed properly. Nodes ids and keys (private and public) are acquired via a registration authority [START_REF] Castro | Secure Routing for Structured Peer-to-peer Overlay Networks[END_REF] and it is assumed that honest nodes never reveal their private keys to other nodes. We also assume the existence of private channels (obtained through cryptographic means) between each pair of nodes preventing an adversary from eavesdropping and unnoticeably tampering with the content of a message exchanged between two honest nodes through this channel. A malicious node has complete control over the messages it sends and receives. Finally, we do not consider Sybil attacks [START_REF] Douceur | The Sybil Attack[END_REF], which mainly consist in flooding the system with numerous fake identifiers. We assume the existence of some external mechanism for solving this problem such as an off-line certification authority.

Sampling Assumptions

Similarly to Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF], we assume that there exists a time T 0 such that after that moment, the churn of the system ceases. This assumption is necessary to make the notion of uniform sample meaningful. Thus from T 0 onwards, the population of the system S is composed of n ≪ 2 l nodes, such that at least (1k)n of them are honest and no more than kn of them are malicious, and thus are controlled by the adversary. The subset of honest nodes in the overlay is denoted by N . Finally, we assume that all the nodes in S are weakly connected from time T 0 onwards, which means that there exists a path between any pair of nodes in S in the underlying undirected graph whose vertices represent the nodes of S and edges are the communication links between these nodes. Local memory of node vi p, q Probability distributions p (U ) Uniform distribution H(p) Entropy of p H(p, q) Cross entropy of p relative to q D(p||q) Kullback-Leibler divergence of p relative to q D max Maximum value of D(q||p (U ) ) τs Robustness threshold of strategy s Table 1. List of symbols and notations

Notations

The main symbols and notations used in this article are summarized in Table 1.

Most of these notations are formally defined in the following.

4 Sampling Component

Assumptions and Terminology

Each node v i ∈ N has locally access to a sampling component4 as illustrated in Figure 1. The sampling component implements a strategy s and has uniquely access to a local data structure Γ vi , referred to as the sampling memory. The size of the sampling memory Γ vi is bounded and is denoted by |Γ vi |. The sampling component S s vi is fed with an infinite stream < v 1 , v 2 , . . . > of (possibly non unique) node ids that correspond to the node ids periodically received by node v i ∈ N . This stream results either from the propagation of node ids through gossip-based algorithms (namely through push, or pull or push-pull mechanisms initiated by v i and its neighbors), or from the node ids received during random walks initiated at v i , or even resulting from induced churn. The fingerprint of an input stream is a collection of weighted points in which each node id is weighted by the number of times it appears in the stream. Specifically, a stream of node ids can be summarized by < (v 1 , m v1 ), . . . , (v n , m vn ) >, where v i denotes the identifier of a node in S and m vi ∈ N represents the number of times v i appears in the stream. At each time t, the following three steps are atomically executed. To begin with, the first element of the stream, say node id v j , is given as input to the sampling component. Then, the sampling component S s vi reads v j and removes it from the stream. Finally, according to its strategy s, S s vi may store or not v j in Γ vi and outputs at most one node id. For example, the strategy s may consist in storing v j if Γ vi is not full, or in substituting v j for a randomly chosen node id that belongs to Γ vi , or simply in dropping v j . The output of the sampling component at time t, denoted S s vi (t), is chosen among the node ids in Γ vi according to strategy s. For instance, strategy s may consist in choosing a random node id in Γ vi [START_REF] Busnel | On the Uniformity of Peer Sampling based on View Shuffling[END_REF][START_REF] Gurevich | Correctness of Gossip-Based Membership under Message Loss[END_REF] or the smallest node id under a given min-wise permutation [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF]. The maximum finite hitting time needed for the sampling component S s vi to reach a uniform sample is denoted by T s . Clearly, T s depends on the strategy s implemented by the sampling component and also on the stream of node ids the sampling component is fed with. We assume that the sampling strategy is known by the adversary in the sense that the algorithm used is public knowledge. However, if the algorithm is a randomized one, the adversary does not have access to the local random coins used by the honest nodes.

ids stream S s vi (t) S s v i Γ vi
Finally, δ represents the number of node ids injected by the adversary in the input stream of node u during the time interval T s . Note that it does not matter whether the injected node ids correspond to the node ids of malicious nodes or not. Indeed, the unique objective of the adversary is to bias the input stream in such a way that whatever the strategy s of the sampler component, its output S s vi (t) cannot guarantee both the uniform and freshness properties.

Sampling Properties

We consider the problem of achieving an unbiased (uniform) and fresh sampling in large scale unstructured peer-to-peer systems subject to adversarial attacks.

A strategy s that solves this problem has to meet the following two properties: i) Uniformity, which states that any node in the overlay should have the same probability to appear in the sample of honest nodes in the overlay, and ii) Freshness, which states that any node should have a non-null probability to appear infinitely often in the sample of any honest node in the overlay. More formally, the sampling strategy s should guarantee the following two properties.

Property 1 (Uniformity). Let N be a weakly connected graph from time T 0 onwards, then for any time t ≥ T s , for any node v j ∈ S, and for any node

v i ∈ N , P[v j ∈ S s vi (t)] = 1 |S| .
Property 2 (Freshness). Let N be a weakly connected graph from time T 0 onwards, then for any time t ≥ T s , for any node v j ∈ S, and for any node

v i ∈ N , {t ′ > t | S s vi (t ′ ) = v j } = ∅ with probability 1.
Note that uniformity by itself does not imply freshness, and vice versa. Indeed, the former does not impose any restriction on the freshness of output node ids, while the latter one does not provide any guarantee regarding the equiprobability of node ids to be chosen as samples. Moreover, as each node v j in S has a non-null probability to be returned by S s vi at time t, v j must appear at least once in the input stream. Thus, ∀v j ∈ S, starting from time T s , m vj > 0. Note that, as previously mentioned, the model and analysis presented in this paper are independent from the way the stream of node ids at each node v i is generated.

Characterization of the Uniform and Fresh Sampling Problem

We start our characterization by showing that the adversary can bias the input stream in such a way that neither uniform nor freshness properties can be met. This is achieved by flooding the input stream with sufficiently many chosen node ids. Specifically, Lemma 1 states that for any strategy s, if the number δ of non unique node ids that appear in the input stream of node v i ∈ N during T s time units exceeds a given threshold then it is impossible for any node in the overlay to equally likely appear as a sample of node v i , and this holds forever. Let C 1 be a condition on the value of δ:

δ ≤ T s -(1 -k)|S|. (C 1 )
Condition C 1 characterizes the fact that for any honest node v i ∈ N , during the time interval T s , v i has a non-null probability to appear in the input stream. We have the following lemma.

Lemma 1. ¬(C 1 ) =⇒ ¬ U ∧ ¬F.
Proof. Let v i ∈ N . Suppose that Condition C 1 does not hold, namely it exists an adversarial behavior such that

δ > T s -(1 -k)|S|.
In this case, the number of honest node ids in the input stream at v i (i.e., T s -δ) is strictly lower than (1k)|S|, which means formally that

T s -δ < (1 -k)|S|.
By assumption (cf. Section 4.1), the overlay is populated by (1k)|S| honest nodes. Thus, as the adversary manages to flood the input stream at v i , there exists at least one node id v j ∈ S that will never appear in the stream. Therefore, whatever the strategy s, v i 's sampling component can never output v j . Thus,

∀t > T 0 , P[v j ∈ S vi (t)] = 0, (1)
which clearly violates Property U . Equation ( 1) can be rewritten as ∃t > T 0 , ∃v j ∈ S, ∀t ′ > t, P[v j ∈ S vi (t ′ )] = 0, which has for consequence that the set of instants t ′ for which v j can be sampled by v i is empty. Formally,

P[{t ′ |t ′ > T 0 ∧ v j ∈ S vi (t ′ )} = ∅] > 0,
which violates Property F, and completes the proof of the lemma.

⊓ ⊔

We now assume that Condition C 1 holds. The second lemma states that if the size of the sampling memory is large enough, then whatever the constrained adversarial behavior, the sampling component succeeds in exhibiting uniform and fresh samples. This results in a sufficient condition to solve our problem. Specifically, let C 2 be defined as follows

|Γ vi | < |S|. (C 2 )
Condition C 2 characterizes the fact that nodes cannot maintain the full knowledge of the population overlay essentially due to scalability reasons. We can now prove the following lemma.

Lemma 2. (C 1 ) ∧ ¬(C 2 ) =⇒ U ∧ F.
Proof. Proof of the lemma is straightforward. By Condition C 1 , any node v j ∈ S has a non-null probability to appear in the input stream of any node v i ∈ N .

By assumption of the lemma, |Γ vi | ≥ |S|. Consider the basic strategy s of v i 's sampling component that consists in storing into Γ vi , any new id read from the input stream. Then eventually, all the node ids will be present into Γ vi , and thus, according to an uniform selection strategy, any node v j is equally likely to be chosen in Γ vi , which guarantees Property U . Moreover, v i has the possibility to return infinitely often any node id v j present in Γ vi . Thus for any time t, the set of times t ′ with t ′ > t at which v j has been chosen in Γ vi has a zero probability to be empty, which ensure Property F and completes the proof.

⊓ ⊔

The following Lemma completes the characterization of the problem.

Lemma 3. (C 1 ) ∧ (C 2 ) =⇒ ¬(U ∧ F).
Proof. Suppose that both Conditions C 1 and C 2 hold. Proving that ¬(U ∧ F) is equivalent to showing that (¬F ∨ ¬ U ) holds, and thus, that (F =⇒ ¬ U ) is true. Suppose that (C 1 ) ∧ (C 2 ) ∧ F is met, we now show that U cannot hold. Consider any node v i ∈ N (the set of honest nodes) and let Γ vi (t) denote the content of v i 's sampling memory at the instant t. From Condition C 2 , ∀t ′ ≥ T 0 , ∃v j ∈ S, v j ∈ Γ vi (t ′ ).

(

) 2
In particular, Equation ( 2) is true for t ′ = T s . Let node v j ∈ S be such that v j / ∈ Γ vi (T s ), then by assumption Property F holds. Thus Suppose that d = 0, then ∀t ′′ ≥ t, v j ∈ Γ vi (t ′′ ), the state (v j ∈ Γ vi ) is absorbing. Consider an overlay that contains only two nodes, v i and v j . By assumption, at least one of the two nodes is honest (k < 1). Let us assume that v i is honest (the proof is similar for v j ). Then, by Condition C 2 , we have |Γ vi | = 1 (the case |Γ vi | = 0 trivially leads to an impossibility). By assumption, we have ∀t ′′ ≥ t, v j ∈ Γ vi (t ′′ ) and as |Γ vi | = 1, we also have ∀t ′′ ≥ t, Γ vi (t ′′ ) = {v j }. Consequently, whatever the strategy s implemented in v i 's sampling component,

∃t > T s , v j / ∈ Γ vi (T s ) ∧ v j ∈ Γ vi (t). (3)
∀t ′′ ≥ t, P[v i ∈ S s vi (t ′′ )] = 0 =⇒ P[{t ′′ |t ′′ > t ∧ v i ∈ S s vi (t ′′ )} = ∅] > 0,
which contradicts F and also the assumption of the lemma. Thus d > 0 and, a fortiori, b < 1, and no state is absorbing. Suppose now that U holds, we now prove the lemma by contradiction. Consider once again the situation in which the overlay is populated by only two nodes, v i and v j . As previously, suppose that node v i is honest and that |Γ vi | = 1. The evolution of the sampling memory at node v i can be modeled by a Markov chain as represented in Figure 3. By assumption, F holds, and thus infinitely often and successively, both v i and v j appear in Γ v . Moreover by assumption, U also holds, that is, ∀t ≥ T s , P[v j ∈ S s vi (t)] = P[v i ∈ S s vi (t)] = 1 2 . As a consequence, v j has the same probability as v i to be in Γ v , whatever the number of times v j and v i appear in the stream before time T s . Suppose now that node v j is malicious. By Condition C 1 , node id v j can appear in v i 's stream no more than T s -1 times during any sliding window of T s time units. As |Γ vi | = 1, only a single node id can be stored, and beyond this node id, no other additional information can be stored. We now demonstrate that whatever the strategies s implemented by v i 's sampling component, they all lead to a contradiction. Blind replacement. At any time t, the sampling component reads the first node id in the stream, and stores it in Γ vi in place of the previous one. By construction, any strategy has to select its output among the elements stored in Γ vi , thus the output of the sampling component follows the same probability distribution as the one observed in the stream. As the adversary can flood the stream with up to T s -1 malicious node ids, this means that Property U cannot be met. No replacement. Similarly to the blind replacement strategy, node ids are read from the stream and stored in Γ vi up to time t, in which t is the first time at which a specific node id is read. From time t onwards, this specific node id is kept in Γ vi , independently from the node ids read from the stream after t, leading to an absorbing state of the Markov chain. For instance, this specific node id can be the smallest image value under a random min-wise independent function such as the min-wise permutation [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF]. Clearly, this strategy violates Property F. Probabilistic replacement. This strategy consists in substituting the current node id in Γ vi with the next one read from the stream according to a given probability law. To guarantee that ∀t, P[v j ∈ S s vi (t)] = P[v i ∈ S s vi (t)] = 1 2 , then either both v i and v j have an equal probability to appear in the stream or the sampling component must be able to remember the node ids it has seen in the past to guarantee that, at any time t, each node id has the same probability to be chosen as sample. The former case does not hold as by assumption, the adversary can flood the stream with up to T s -1 malicious ids. Moreover, the latter case is impossible as by assumption |Γ vi = 1|. Therefore, only a single information can be stored (e.g., it is impossible to store both a node id and a counter), and as consequence Property U cannot hold.

vi = {v i } vi = {v j } Γ Γ
Thus (C 1 ) ∧ (C 2 ) =⇒ ¬(U ∧ F), which concludes the proof of the lemma. ⊓ ⊔

The last lemma, described below, reformulates the necessary condition of the problem characterization by combining Lemmata 1 and 3.

Lemma 4. U ∧ F =⇒ (C 1 ) ∧ ¬(C 2 ).
Proof. The contrapositive form of writing Lemma 3 is

U ∧ F =⇒ ¬((C 1 ) ∧ (C 2 )),
and thus by distribution,

U ∧ F =⇒ ¬(C 1 ) ∨ ¬(C 2 ). (4)
On the other hand, the contraposition of Lemma 1 leads to U ∨ F =⇒ (C 1 ). As (U ∧ F ⇒ U ∨ F), we have

U ∧ F =⇒ (C 1 ). ( 5
)
By combining Equations 4 and 5, the following relation holds

U ∧ F =⇒ (C 1 ) ∧ (¬(C 1 ) ∨ ¬(C 2 )),
which is equivalent to

U ∧ F =⇒ ((C 1 ) ∧ ¬(C 1 )) ∨ ((C 1 ) ∧ ¬(C 2 )) .
By contradiction, (C 1 ) ∧ ¬(C 1 ) cannot hold, leading to

U ∧ F =⇒ (C 1 ) ∧ ¬(C 2 ),
which completes the proof.

⊓ ⊔

The uniform and fresh sampling problem defined in Sections 3 and 4 is completely characterized by the following theorem. Proof. This result follows directly from the statements of Lemma 2 and 4.

⊓ ⊔

Given this coarse-grained characterization, it appears to be unreasonable to ensure such conditions in real life applications. To address this issue, the following sections provide some finer-grained characterization of sampling strategies. These strategies are capable of unbiasing an input stream according to the value of norm of the entropy of this stream.

Information Divergence of Data Streams

A natural approach to detect changes on data streams is to model it as a distribution and to compute the distance between the observed stream and the ideal one. The metric we use in our context is the Kullback-Leibler (KL) divergence, also sometimes called the relative entropy [START_REF] Cover | Elements of information theory[END_REF].

Definition 1 (Kullback-Leibler divergence).

Given two probability distributions p = {p 1 , . . . , p n } and q = {q 1 , . . . , q n }, the Kullback-Leibler divergence of p i relative to q i is defined as the expected value of the likelihood ratio with respect to q i . Specifically,

D(p||q) = n i=1 p i log 2 p i q i = H(p, q) -H(p), (6)
where H(p) =p i log 2 p i is the (Shannon) entropy of p and H(p, q) = p i log 2 q i is the cross entropy of p and q (by convention, 0 log 2 0 = 0).

The KL-divergence is a member of a larger class of distances known as the Ali-Silvey distances [START_REF] Ali | General Class of Coefficients of Divergence of One Distribution from Another[END_REF]. For the sake of clarity, we will use the notation log to denote the logarithm in base 2. Let p (U ) be the uniform distribution corresponding to a uniform stream (i.e., ∀i ∈ [1.

. n], p

(U ) i = 1
n ), and q be the probability distribution corresponding to the input stream. Following the classical use of the KL-divergence, we consider D(q||p (U ) ) as a measure of the divergence of the stream from the ideal one. Note that a probabilistic algorithm computing on the fly the KL divergence of any stream with respect to an ideal one has been proposed in [START_REF] Anceaume | A distributed information divergence estimation over data streams[END_REF]. Experimental results have shown that the estimation provided by this algorithm remains accurate even for different adversarial settings in which the quality of other methods dramatically decreases.

Definition 2 (τ -closeness).

A stream of node ids σ is τ -close if the KLdivergence between the probability distribution q corresponding to σ and the uniform probability distribution p (U ) is below or equal to a given value τ called the robustness threshold, in whch τ is a positive real value.

Finally given probability distributions, the Earth Mover's Distance (EMD) [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF] measures the minimal amount of work needed to transform one distribution to another by moving the probability mass between events. We rely on this metric to quantify the effort that an adversary exerts to bias the input stream. In our context, a unit of work corresponds to dropping one id and to pushing another id instead in the input stream.

Omniscient Adversary Model

In this section, we study the behavior of an omniscient adversary, which has the capacity to eavesdrop on all the messages sent and received by all the nodes in S. We demonstrate that the strategy pushing all the probability mass over a single id is the one maximizing the bias of the input stream so that it becomes far from the uniform distribution. We also describe an optimal strategy achieving it.

In the following, the analysis of infinite input stream is restricted to any window of length T s observed from time t ≥ T 0 . As previously said, T s depends on the sampling strategy and thus can be arbitrarily large. For the sake of simplicity, the term "stream" will denote in the remaining of the paper the stream restricted to any such window of length T s .

Let σ be a stream such that the id of each node in S appears exactly once in the stream, except for a unique id that appears in all the remaining slots. Therefore, there exists a unique v i ∈ S such that m vi = T s -(n -1) and ∀v j = v i ∈ S, m vj = 1. The following theorem states that the probability distribution associated to this particular stream is the one that has the maximal divergence from the uniform distribution.

Theorem 2. (Maximal divergence from the uniform distribution) Let p (U ) be the uniform distribution corresponding to a uniform stream, that is, ∀i ∈ [1.

. n], p

(U ) i = 1
n , and q be the probability distribution corresponding to σ ( i.e., it exists a unique v i ∈ S, q vi = Ts-(n-1) Ts and ∀v j ∈ S, v j = v i ⇒ q vj = 1 Ts . Then, for any possible probability distribution q, D(q||p (U ) ) ≤ D(q||p (U ) ).

Proof. Let q be the probability distribution representing any valid input stream on (T 0 , T s ]. We have ∀v i ∈ S, q vi = mv i Ts , where m vi is the number of times v i is present in the input stream. It follows that

D(q||p (U ) ) = H(q, p (U ) ) -H(q) = - n i=1 q i log p (U ) i -H(q) = log(n) -H(q).
Therefore, maximizing D(q||p (U ) ) amounts to minimizing H(q), which is equivalent to maximize n i=1 m vi log mv i Ts . We characterize the stream that minimizes H(q) under the following constraints:

     1 ≤ m vi ≤ T s with 1 ≤ i ≤ n, n i=1 m vi = T s . (7)
From these constraints, we immediately have 1 ≤ m vi ≤ T s -(n -1). To relax the second constraint, we pose

m vn = T s - n-1 i=1 m vi . Let function f be such that f (m v1 , . . . , m vn-1 ) = n-1 i=1 m vi log m vi T s + T s - n-1 i=1 m vi log 1 - n-1 i=1 m vi T s .
Function f is differentiable on its domain

I s = [1. . T s -n + 1] n-1 , thus we get df dm vj (m v1 , . . . , m vn-1 ) = log m vj T s + m vj T s m vj + log 1 - n-1 i=1 m vi T s + T s - n-1 i=1 m vi 1 - n-1 i=1 mv i Ts = log m vj + log T s - n-1 i=1 m vj + 2(T s -log(T s )).
According to Equation 7, we have

log m vj + log T s - n-1 i=1 m vj ≥ 0
and, as T s ≫ 1, this implies T slog(T s ) > 0. Then, we obtain that df dmv j > 0, leading to the fact that f is strictly increasing according to m vj . The maximum is then reach for m vj = T sn + 1 as f is a Schur-convex function.

From this set of constraints (cf. Equation 7), if the maximum of D(q||p (U ) ) is reached for m vj = T sn + 1 then n i=1,i =j m vi = n -1 implies that ∀i ∈ [1..n], i = j, m vi = 1, which concludes the proof.

⊓ ⊔

Theorem 2 enables us to formulate an upper-bound D max on the KL-divergence between the uniform stream and any other stream:

D max = D(q||p (U ) ) = log(n) + log(T s ) -1 - n -1 T s log (T s -n + 1) . ( 8
)
As a consequence, any input stream σ is D max -close (cf. Definition 2).

To determine the minimal effort that the adversary has to exert to bias the input stream so that both uniformity and freshness properties do not hold, we use the Earth Mover's Distance (EMD) between the uniform distribution and the target one. In the following, when we say that the adversary replaces node id v i by node id v j , we mean that he drops v i from the input stream and injects v j instead. Recall that the adversary is able to drop and inject node ids only from the nodes it controls. However, as mention in the introduction, the adversary may succeed in surrounding a honest node with malicious nodes so that it may shape by itself the input stream of this honest node. Lemma 5. (Optimal strategy to maximize the divergence) Given an input stream σ, replacing the less frequent node id in σ with the most frequent one maximizes the gain in KL-divergence with respect to the uniform distribution for the same amount of work as measured by the EMD distance.

Proof. Given an input stream σ represented by the probability distribution q, we construct the input stream σ ′ from σ by substituting one occurrence of node id v i with node id v j so that D(q ′ ||p (U ) ) is maximized after this replacement (in which q ′ denotes the probability distribution representing σ ′ ). This amounts to maximize D(q ′ ||p (U ) ) -D(q||p (U ) ) . Recall that all node ids in S must be present in σ ′ . Therefore, we search for the node id pair (v i , v j ) such that

         m ′ vj = m vj + 1 m ′ vi = m vi -1 v j = arg max vj ∈S q ′
vj log q ′ vjq vj log q vj v i = arg max vi∈S q ′ vi log q ′ viq vi log (q vi ) Consider the function f : x → x log(x), which is strictly increasing. For any k ∈ S, we have

q v k = m v k /T s . Thus,    v j = arg max vj ∈S f mv j +1 Ts -f mv j Ts v i = arg max vi∈S f mv i -1 Ts -f mv i Ts =⇒ v j = arg max vj ∈S m vj v i = arg min vi∈S m vi
This derives from the fact that the function g 1 : x → f ( x+1 Ts )-f ( x Ts ) (respectively

g 2 : x → f ( x-1
Ts ) -f ( x Ts )) is strictly increasing (respectively strictly decreasing). The optimal node id replacement maximizing the KL-divergence gain is reached by replacing the less frequent node id v i with the most frequent one v j .

⊓ ⊔ Algorithm 1 (run by the adversary) shows an optimal implementation of Lemma 5 with respect to the number of performed replacements. Specifically, the inputs of the algorithm are an input stream σ and the robustness threshold τ s . Recall that τ s is the robustness threshold of the sampling strategy s implemented by S s u , which means that for any τ s -close input stream σ, the sampling strategy s is able to output a uniform and fresh sample. The goal of the greedy Algorithm 1 is to tamper with the input stream σ in order to increase its KL-divergence above τ s with a minimum effort.

By assumption, the adversary is omniscient and therefore has the capacity to observe the entire input stream σ. From Section 4, the adversary knows the strategy s of the sampler, and thus can compute the value of τ s . The value of the maximum divergence D max is computed using Relation [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF]. If D max is larger than or equal to the robustness threshold, the algorithm returns "fail". Otherwise at each iteration, the adversary performs the optimal node id replacement until the KL-divergence exceeds the robustness threshold. Remember however, that the adversary cannot drop messages that have been sent or forwarded by nodes it does not control (i.e., the ones). Note that at Lines ( 8) and ( 9) of Algorithm 1 both m vi and m vj are updated. Counter ℓ returned by Algorithm 1 represents the number of replacements done by the adversary.

Consider a sampling strategy s, its robustness threshold τ s , and an input stream σ. Let ℓ be the number of replacements executed by Algorithm 1. If we denote by q σ(ℓ) the probability distribution derived from σ after these ℓ optimal replacements, we have the following corollary.

Corollary 1. (Lower bound on the effort exerted by an omniscient adversary)

The minimum number of replacements an omniscient adversary has to apply to exceed τ s is δ = inf ℓ ∈ N : D(q σ(ℓ) ||p (U ) ) > τ s .

8 Blind Adversary Model

In this section, we study the behavior of a blind adversary, that is an adversary that only has the capacity to observe messages sent or received by the nodes he controls. A strategy that the adversary might apply to bias the input stream is to choose a node id (possibly one that belongs to a malicious node but not necessarily) and to push it in the input stream as much as possible. We show that this strategy is optimal with respect to the effort exerted by the adversary and we derive a lower bound on the expected minimum amount of work a blind adversary has to exert to bias the input stream.

Theorem 3. (Lower bound on the expected effort exerted by a blind adversary)

Let s be a sampling strategy, τ s its robustness threshold and T s its maximum convergence time. The minimum number of replacements a blind adversary has to apply in expectation to exceed τ s is given when the input stream is the uniform one. We have δ = inf {ℓ ∈ I s : R ℓ > τ s }

where

I s = 0..T s -n + 1 - T s n R ℓ = 1 n ℓ -1 Ts n -1 log T s n + log T 2 s T s + nℓ -log T s -n 1 + (ℓ -1) mod T s n - 1
Proof. Let us consider the uniform node ids stream on a window of length T s . For any v i ∈ S, v i is present in the stream T s /n times in average. The probability distribution p (U ) is such that ∀v i ∈ S, p (U ) vi = 1/n. From Section 7, we have seen that the optimal strategy for the adversary to bias an input stream is to replace the less frequent node id in this stream with the most frequent one. By assumption, the adversary is blind and cannot observe all the node ids of the input stream. The strategy of the adversary consists in choosing a specific node id v j and repeatedly pushing v j in the input stream. Let σ be an input stream and σ ′ be the stream obtained from σ after one step of this adversarial strategy (i.e., replacing v i by v j for some v i ∈ S). We have

D(q σ ′ ||p (U ) ) -D(q σ ||p (U ) ) = 1 n log m vj m vj + 1 + log m vi m vi -1 , (11)
in which q σ and q σ ′ represent respectively the probability distributions of σ and σ ′ . In the following, q σ(ℓ) denotes the probability distribution derived from σ after ℓ replacements. Given a sampling strategy s, we prove by induction on the number of optimal replacements ℓ that, starting from a uniform stream, the maximum KL-divergence after ℓ replacements is given by D

(q σ(ℓ) ||p (U ) ) = R ℓ , in which R ℓ = 1 n ℓ -1 Ts n -1 log T s n + log T 2 s T s + nℓ (12)
-log T s -n 1 + (ℓ -1) mod T s n -1 .
Note that ℓ cannot be greater than T s -n + 1 -Ts n . Indeed, all node ids in the initial uniform stream are present at least Ts n times and the maximum number of times a unique id can appear in the stream is (T s -n + 1). For ℓ = 1, the claim follows immediately from Equation 11. Now, assume that the claim also holds for all 1 ≤ j ≤ ℓ. We show that it holds for j = ℓ + 1. The KL-divergence with respect to the uniform stream after ℓ + 1 steps is

D(q σ(ℓ+1) ||p (U ) ) = D(q σ(ℓ) ||p (U ) ) + D(q σ(ℓ+1) ||p (U ) ) -D(q σ(ℓ) ||p (U ) ). (13)
The term D(q σ(ℓ+1) ||p (U ) ) -D(q σ(ℓ) ||p (U ) ) represents the gain of step (ℓ + 1), and D(q σ(ℓ) ||p (U ) ) is given by Equation 12. Two sub-cases need to be considered: (i) ℓ mod Ts n -1 = 0 and (ii) ℓ mod Ts n -1 = 0. Case (i ): the less frequent node id v i in the stream at step ℓ + 1 is the same as the one removed at step ℓ. After ℓ steps, m vj = Ts n + ℓ and m vi = Ts n -1 + (ℓ -1) mod

+ ℓ + 1 + log Ts n -1 + (ℓ -1) mod Ts n -1 Ts n -1 + (ℓ -1) mod Ts n -1 -1 = 1 n log T s -n 1 + (ℓ -1) mod T s n -1 + log (T s + nℓ) -log (T s + n(ℓ + 1)) -log T s -n 2 + (ℓ -1) mod T s n - 1
.

By assumption (i), we have

ℓ-1 ⌊ Ts n -1⌋ = ℓ ⌊ Ts n -1⌋ and 1 + (ℓ -1) mod T s n -1 = ℓ mod T s n -1 .
From Equation 13, we get

D(q σ(ℓ+1) ||p (U ) ) = 1 n ℓ Ts n -1 log T s n + log T 2 s T s + n(ℓ + 1) -log T s -n 1 + ℓ mod T s n -1 ,
which ends Case (i ). Case (ii ). The argumentation is the same as above. However, as ℓ mod Ts n -1 = 0, the node id that has been previously replaced is now present exactly once in the stream. Thus, the adversary needs to randomly choose another node id in the stream before processing the next step of his strategy. Applying Equation 11 at step ℓ + 1 gives D(q σ(ℓ+1) ||p (U ) ) -D(q σ(ℓ) ||p (U ) ) =

By assumption (ℓ -1) mod Ts n -1 = Ts n -1 -1 , and by combining the induction hypothesis (Equation 12) with the gain obtained at step ℓ + 1 (Equa- As a conclusion, any value of ℓ that allows the adversary to exceed the robustness threshold τ s defeats the sampling strategy. Thus, the minimum number of replacement operations δ is the lower bound of this set of values.

⊓ ⊔

We now evaluate the minimum amount of work a blind adversary has to exert in the worst case to bias the input stream. In the worst case, the node id v i the adversary has chosen to blindly flood might be initially present only once in the input stream. In order to bias the input stream, the adversary needs to push id v i sufficiently often so that the probability of appearance of id v i reaches the uniform value, with respect to all the other node ids, and then to continue to push this id δ times so that the divergence between the resulting stream and the uniform one is maximum.

Theorem 4. (Lower bound on the worst-case effort exerted by a blind adversary) Let s be a sampling strategy, τ s its robustness threshold and T s the maximum convergence time of s. The minimum number of replacements the adversary has to apply on a stream in the worst case to exceed τ s is

δ + T s n -1.
Proof. The proof is immediate. First, the adversary has to raise the chosen id at least up to the uniform value. In the worst case, this id is present only once in the initial stream, which costs Ts n -1 replacements to reach a number of occurrences equals to Ts n . Moreover, once this id is present in the modified stream Ts n times, the adversary follows the same strategy as before, which requires δ more steps to guarantee that the robustness threshold τ s is exceeded. Note that this value is a worst-case bound and not the exact minimum value with respect to τ s because after the first ( Ts n -1) steps, the modified stream could be different from the uniform one. In this situation, the KL-divergence to the uniform stream is strictly greater than 0, reducing accordingly the amount of work of the adversary to exceed τ s .

⊓ ⊔

Conclusion and open issues

In this paper, we have focused on the problem of achieving uniform and fresh node sampling in large scale open systems potentially populated with malicious nodes. The node sampling problem consists in guaranteeing that each honest node can maintain a uniform and fresh sample of the whole population of the system. First, we have shown that if the system cannot limit the resources of the adversary, then solving either uniform sampling or fresh sampling is impossible. Then, we have demonstrated that, in the unrealistic setting in which honest nodes have access to a very large memory (i.e., proportional to the size of the system), then the problem becomes trivially solvable. Unfortunately, we have proven that both conditions are necessary and sufficient ingredients to solve the uniform and fresh sampling problem in adversarial environments. Clearly, these strong conditions highlight the damage that adversarial behavior can cause in large-scale unstructured systems. By modeling input streams as probability distributions, we have also characterized the minimum effort (measured in terms of node ids replacements) that an omniscient and a blind adversary have to exert on the input stream of node identifiers to exceed the robustness threshold that quantifies the power of a sampling strategy. We believe that uniform node sampling should be regarded as a necessary building block to derive larger classes of sampling schemes. This building block is of utmost importance in systems in which the population is continuously evolving and in which it is impossible to capture the full complexity of the network through global snapshots.

Fig. 1 .

 1 Fig. 1. Sampling component of node vi ∈ N .

v j 2 vi v j / 2 Fig. 2 .

 22 Fig. 2. Markov chain representing the evolution of vj's presence in the sampling memory Γv i of node vi ∈ N .

Fig. 3 .

 3 Fig. 3. Markov chain representing the state of the local memory Γv i of vi.

Theorem 1 .

 1 (C 1 )∧¬(C 2 ) is a necessary and sufficient condition for the uniform and freshness properties to hold.

Algorithm 1 : 2 return "fail" 3 else 4 ℓ ← 0; 5 vj

 1245 Adversary biasing strategyData: an input stream σ, the robustness threshold τs Result: the number of replacements ℓ if it exists 1 if τs ≥ D max then ← arg maxv j ∈S mv j ; 6 while D(qσ||p (U ) ) ≤ τs do 7 vi ← arg min {v∈S:mv i =1} mv i ; 8 let k be the index of an item in the part of the stream controlled by an adversary such that σ[k] = vi ; 9 σ[k] ← vj //one occurrence of vi is dropped and vj is injected instead ; 10 ℓ ← ℓ + 1; 11 return ℓ

tion 14 )- 1 ⌊ 2 s

 1412 , we getD(q σ(ℓ+1) ||p (U ) log (T s + n(ℓ + 1)) -log (T s -n) -log (n)) .By assumption of the case ℓ ⌊ Ts n -1⌋ = ℓ-Ts n -1⌋ + 1, which proves the induction:D(q σ(ℓ+1) ||p (U ) T s + n(ℓ + 1) -log T s -n 1 + ℓ mod T s n -1 .

Although malicious nodes have also access to a sampling component, we cannot impose any assumptions on how they feed it or use it as their behavior can be totally arbitrary.