Counting on Anonymous Dynamic Networks through Energy Transfer ?

Counting on Anonymous Dynamic Networks through Energy Transfer ^?

G. A. D

L

, R. B

, S. B

, I. C

,

†

Cyber Intelligence and Information Security Research Center and Dipartimento di Ingegneria Informatica, Automatica e Gestionale Antonio Ruberti

Universit´a degli Studi di Roma La Sapienza, Roma, Italy {baldoni, bonomi, diluna}@dis.uniroma1.it

‡

Computer Technology Institute & Press “Diophantus” (CTI) Patras, Greece

{ichatz}@cti.gr

Abstract. This paper addresses the problem of counting the size of a network where (i) processes have the same identifiers (anonymous nodes) and (ii) the network topology constantly changes (dynamic network). Changes are driven by a powerful adversary that can look at internal process states and add and remove edges in order to contrast the convergence of the algorithm to the correct count. The paper proposes two leader-based counting algorithms.

Such algorithms are based on a technique that mimics an energy-transfer between network nodes.

The first algorithm assumes that the adversary cannot generate either disconnected network graphs or network graphs where nodes have degree greater than D. In such algorithm, the leader can count the size of the network and detect the counting termination in a finite time (i.e., conscious counting algorithm). The second algorithm assumes that the adversary only keeps the network graph connected at any time and we prove that the leader can still converge to a correct count in a finite number of rounds, but it is not conscious when this convergence happens.

Keywords: Anonymous Networks, Dynamic Networks, Counting Algorithms, Dynamic Graph Adversary.

?

This paper will appear at ICDCN14 under the title “ Conscious and Unconscious Counting on Anonymous Dynamic Networks ”

1 Introduction

Computing global properties of a distributed system based on a static topology (i.e. counting the nodes belonging to the system) is of primary importance to build applications that take decisions locally at each node, based on global information. As an example, making a distributed near-optimal load balancing among the nodes of the system cannot be computed without knowing the network size. Additionally, knowing the size of the network is needed to ensure distributed termination of algorithms (e.g, terminating broadcast). Recently, dynamic distributed systems have attracted a lot of interest [5,8], due to the fact that static ones do not capture anymore the new kind of software applications designed to run on top of emerging environment like mobile and sensors networks. In this environment, the topology of the network connecting the distributed system participants constantly changes. The high dynamicity of the topological connections between processors brings new challenges for solving problems that were already solved on the top of static distributed systems. Moreover, privacy concerns are becoming more and more important and they could be addressed considering models where processors does not have unique IDs [18]. In this paper we consider the problem of counting the size of anonymous dynamic network. More specifically, we study round-based computations under worst-case dynamicity as originally introduced by [17] and then refined in [14]. We consider that the network graph is controlled by a dynamic graph adversary that, at each round, may introduce or remove any number of edges, still ensuring the graph remains connected. Communication along edges is assumed to be bidirectional and nodes are not aware of which edges are made available by the adversary at each round. Messages are then delivered to current sender’s neighbors, as chosen by the adversary; nodes change their states, and the next round begins. Each node runs a deterministic algorithm that generates messages based on processes internal state that the adversary is able to read.

Counting on anonymous static networks with broadcast has been proved to be non-solvable when there is no leader available [16]. The authors also conjectured that counting in networks under dynamic graph adversary without having knowledge (or estimation) of some network characteristics is impossible. In this work, we introduce a technique for computing the size of an anonymous network that is resilient to a dynamic graph adversary. The technique mimics an energy-transfer and it is embedded in a leader-based algorithm to circumvent the impossibility result. Informally the technique works as follows: each node v

is assigned with a fixed energy charge, stored in the variable e

, and during each round it discharges itself by disseminating energy around to its neighbors i.e., e

decreases of a value k ≤ e

/2, then this quantity k is equally split among the neighbors of v

and this value is added to v

’s neighbors variable.

The leader acts as a sink collecting energy (i.e., energy is not transferred by the leader to neighbors). Our technique enforces, at each round, a global invariant on the sum of energy among networks’ nodes (i.e., P

vi

e

= #nodes), that resorts to the fact that energy is not created or destroyed in the anonymous dynamic distributed system (energy conservation property). Considering the behavior of the nodes, the energy is eventually transferred to the leader and stored there. The leader measures the energy received to count the size of the network. In particular, we present a leader-based algorithm that employs the energy-transfer technique and is tolerant to the dynamic graph adversary additionally constrained by the fact that it cannot generate graphs including nodes with a degree over a certain bound.

At the best of our knowledge, the algorithm proposed in this work is the first algorithm that provides, in a finite time, an exact count on an anonymous dynamic network with broadcast. In the worst-case, the algorithm requires exponential time to complete and the leader is always able to detect when the counting is over (conscious counting). As second result, we show that the conjecture presented in [16] is not valid when considering counting algorithms that are not able to detect the time at which the convergence happens (unconscious counting). To this aim, we present an unconscious leader-based algorithm exploiting the energy transfer technique that is able to reach the correct count being resilient to the dynamic graph adversary. The rest of the paper is organized as follows: Section 2 presents relevant previous work, and in Section 3 we formally define both the anonymous network model, the dynamic graph adversary and the counting problem specifying the properties of convergence and consciousness. Using the energy transfer technique, in Section 4 we present a counting algorithm, namely A

, resilient to a dynamic graph adversary with bounded degree.

Finally, Section 5 shows a counting algorithm A

, that is able to count the size of the network under dynamic graph adversary, however such algorithm does not verify the consciousness property. Section 6 concludes the paper.

2 Related Work

To the best of our knowledge, the only other work that discusses the problem of counting and naming in an anonymous

network with worst-case adversary is [16]. However, the authors just provided an algorithm that knowing an upper

bound on the maximum degree of graphs generated by the adversary, makes possible to each node to compute an upper bound on the size of the network. This algorithm is used as basic building block in our counting algorithm as shown in Section 4. In the rest of the section we consider other works done in the contexts of anonymous static networks, fully identifiable dynamic networks and adversary models that are related to our problem.

Static anonymous networks. The question concerning which problems can be solved on top of an anonymous net- work, where all nodes have the same identifier, has been pioneered by Angluin in [2]. Yamashita and Kameda [18]

proposed several characterizations for problems that are solvable under certain topological constraints when consider- ing known the size of the network. Further investigation led to the classification of computable functions [4,18]. The work presented in [7] has been the first one that removed the assumption of knowing the network size n and provided characterizations of the relations that can be computed with arbitrary knowledge.

Fraigniaud et al. [11] assumed a unique leader in order to break symmetry and assign short labels as fast as possible.

To circumvent the further symmetry introduced by broadcast message transmissions they also studied other natural message transmission models as sending only one message to a single neighbor. Recently, Chalopin et al. [9] have studied the problem of naming static anonymous networks in the context of snapshot computation; such work uses the notion of “graph covering” [4,18], that is usable only on static topologies and is not defined for highly dynamic system like the one studied in our work.

Finally, Aspnes et al. [3] studied the relative power of reliable anonymous distributed systems with different communication mechanisms: anonymous broadcast, read-write registers, or read-write registers plus additional shared- memory objects.

Dynamic distributed systems where all processes have distinct identifiers. Distributed systems with worst-case dynamicity were first studied in [17] by introducing the 1-interval connectivity model. They studied flooding and routing problems in asynchronous communication and allowed nodes to detect local neighborhood changes. Under the same model, [14] studied the problem of counting in networks where nodes have unique IDs and provided an algorithm that requires O(n

) rounds using O(log n) bits per message.

Adversarial vs Random dynamic graph. The gossiping model [12,13] can be seen as a dynamic graph where, at each round, each node randomly selects some neighbors to execute the view exchange. The adversarial model considered in this paper differs from random dynamic graph since in our case the adversary is able to read the state of nodes and compute the set of best edges to add/remove in order to break the correctness of the counting while the gossip adversary simply selects nodes randomly without any strategy.

3 System Model and Problem Specification

We consider a distributed system composed by a finite set of processes V (also called nodes). Nodes in V are anony- mous, i.e., they initially have no identifier and execute a deterministic round-based computation. We assume the set V remains the same throughout the computation.To ease of presentation, in the following we sometimes refer to pro- cesses using names as v

but such names cannot be used by processes themselves in the algorithms.

Every round is divided in three phases: (i) send where processes send all the messages for the current round, (ii) receive where processes receive all the messages sent at the beginning of the current round and (iii) computation where nodes process received messages and prepare those that will be sent in the next round. Rounds are synchronous and they are controlled by a fictional global clock accessible to all the nodes. Thus, all nodes have access to the current round number via a local variable that we usually denote by r. Processes have a local view of the network, i.e. they know a subset of processes called neighbors. Processes are arranged in a communication network and they can communicate only by exchanging messages trough an anonymous broadcast primitive. Such primitive ensures that a message m sent by node v

at the beginning of a certain round r will be delivered to all its neighbors during round r.

Dynamic Network and the Dynamic Graph Adversary. The communication network is dynamic, i.e. its topology

changes along time due to possible nodes or communication links failures. A dynamic network is modeled by a

dynamic graph G(r) = (V, E(r)), where V is the set of nodes (or processors) and E : IN → P(E

), where E

=

{{u, v} : u, v ∈ V }, is a function mapping a round number r ∈ IN to a set E(r) of bidirectional links drawn from E

[14]. The neighborhood of a node v

at round r is denoted by N

(r) = {u : {u, v} ∈ E(r)}.

Intuitively, a dynamic graph G(r) is an infinite sequence G(1), G(2), . . . of instantaneous graphs, whose edge sets are subsets of E

chosen by an adversary. If there are no topology properties imposed on the graphs generated by the adversary (e.g., upper/lower bound on the degree of a node, bound on the diameter of the network), the adversary can generate any graph ranging from a fully connected one to a graph composed by all singleton nodes.

In the paper, we assume that the dynamic graph/network G(r) = (V, E(r)) is 1-interval connected as defined in [14]. A network is 1-interval connected if for all r ∈ IN, the static graph G(r) is connected. Thus, the adversary can change arbitrarily the graphs in the sequence (by adding and removing edges) while ensuring that each graph G(r) in the sequence is connected. Additionally, the adversary is able to read each process state building thus a sequence of graphs that could prevent an algorithm to be correct. We call such adversary, dynamic graph adversary. In addition, we also consider a less powerful adversary that generates only instances G(r) = (V, E(r)) where the number of neighbors that each node v

may have is always bounded by a constant upper bound D (i.e. ∀v

∈ V, ∀r ∈ N, |N

(r) | ≤ D). We call this adversary dynamic graph adversary with bounded degree. For the easy of presentation and whenever it does not generate confusion, in the remaining of the paper we will use the term adversary and dynamic graph adversary interchangeably.

The Counting Problem. The counting problem can be formalized by the following properties:

Let g be a variable representing a guess on the size of the network at a process v.

– Convergence: There exists a round r after which at least one process p has permanently a correct guess on the size of the network, i.e., g = |V |.

– Consciousness: If a node v has a correct guess g on |V |, then there exists a round r

(with r

≥ r) such that v is aware about the correctness of the guess.

In the following, given a counting algorithm A, we will say that it is conscious if it is able to satisfy both the properties; on the contrary, if it satisfies only the convergence property we will say that it is unconscious.

4 Conscious Counting Algorithm resilient to a Dynamic Graph Adversary with Bounded Degree

This section presents a distributed algorithm, denoted as A

, that assumes (i) the existence of a leader node starting from a different initial state and (ii) all other nodes execute identical programs. In addition, A

assumes that the bound on nodes degree D (which limits the powerfulness of the adversary) is known by all processes.

A

is composed by a sequence of iterations i = 0 . . . ` run by the leader and each iteration takes several rounds.

Each iteration i starts considering two parameters: (i) the upper bound on nodes degree D and (ii) an upper bound K

on the network size; then, the algorithm computes a guess for the network size. If the guess matches the current considered bound K

, then the algorithm terminates and K

corresponds to the size of the network |V |. Otherwise iteration i + 1 is started taking D and K

= K

− 1 as inputs.

Let us notice that, starting from the upper bound D on nodes degree, an upper bound K

, to be used in the first algorithm iteration, can be easily computed (e.g. by using the algorithm shown in [16]). Thus, the hard part of A

is to compute the guess on the network size at the end of each iteration. To this aim, A

employs the idea of energy-transfer and exploits the invariant on the energy globally stored in network: the sum of the energy stored by each node at the end of each round remains constant during the algorithm execution. Note that the energy we are considering is not the real energy that nodes may have but it is rather an abstraction used to explain the details of the algorithm.

At the beginning of each iteration i (with i ≥ 0), every node is assigned with a fixed energy charge, and during each round r it discharges itself by disseminating the energy to its neighbors. The leader acts as a sink collecting energy (i.e., it does not transfer energy to its neighbors).

Considering the behavior of the nodes, the energy is eventually transferred to the leader. The leader measures the

level of energy received to verify if the energy level matches the bound K

considered in the current iteration i. More

specifically, the leader starts iteration i of A

algorithm by assuming that the network has size K

and computes the

first round r f inal

where, in the worst case, it should have received strictly more than K

− 1 energy by all the others

1

1 2⇥ 3

e

e

e

e

= 1 1

2 + (5 3) 1 2 +

X

e

Fig. 1: Send, Receive and Update of energy for a non leader node

(see Lemmas 2,3). If at round r f inal

, the leader has received such amount of energy then it outputs |V | = K

. Otherwise the algorithm starts iteration i + 1 with K

= K

− 1.

AlgorithmAD– Conscious Counting Algorithm resilient to a Dynamic Graph Adversary with Bounded Degree.

(Step 1) The algorithm starts taking as inputD and computes an upper bound K on the network size by running an estimation algorithm as the one shown in [16];

(Step 2) The leader and the anonymous nodes start the step 2 at roundr start;

leader : The leaderv_lmaintains the following local variables:e_vl← 1 representing the initial energy charge, rcv_vl ← ∅ is a set variable where vlstores all the messages received during each round,i← 0 is the iteration number, Ki← K is the upper bound on the network size at iteration i, r initi← r start is the starting round of iterationi, r f inaliis the termination round of iterationi when the leader will be able to either validate the guess (i.e.,|V | = Ki) or not (i.e.,|V | < Ki) - see Lemmas 2, 3.

start iteration i at round r init_i: takeD and K_ias inputs

The leader computes the minimumR∈ N⁺such thatR satisfies Ki−(1−(^B−1B )^R)Ki< 1, where B = (2D)^Kand setsr f inali← r initi+ RKi. for each roundr:

– Send phase of roundr: at the beginning of each round, v_lbroadcasts aENERGY RELEASE(0) message releasing no energy.

– Receive and Computation phases of roundr:ENERGY RELEASE(e⁰) messages are stored in the rcv_vlvariable. At the end of the round, when all the messages have been received,vlupdates, its local energy charge as follows:

e_vl← evl+ received

where received is the sum of all the charges received by neighbors (i.e., P

e0 ∈rcvvl

e⁰).

– When(r = r f inali) % Terminating Condition % if(Ki− e_vl< 1)

thenvlterminates and broadcasts forKiroundsSTOP(Ki) message to other nodes and then it outputs count← Ki;

elsevlsends a messageRE-START(r f inali+ Ki) to other nodes declaring that it will start a new iteration. This message is broadcast for Kirounds and thenvlstarts iterationi + 1 considering the new bound Ki+1= Ki− 1 and r initi+1= (r f inali+|Ki|).

anonymous node: Each non leader nodevimaintains the following local variables:e_vi← 1 representing the initial energy charge of vi,rcv_vi← ∅ is a set variable wherevistores all the messages received during each round.

for each roundr:

– Send phase of roundr: at the beginning of each round, vibroadcasts aENERGY RELEASE(^evi_2D) message, releasing at most half of its energy to its neighbors (at mostD).

– Receive and Computation phases of roundr:

switch

case(∃ m =^STOP(count)∈ rcvvi)

vibroadcastsSTOP(count) for count rounds, then vistops to execute the algorithm and outputs the valuecount.

case(∃ m =^RE-START(r⁰)∈ rcv_vi)

vibroadcastsRE-START(r⁰) until the current round is r⁰and thenviinitializes all local variables.

default %rcv_vicontains onlyENERGY RELEASE(e⁰) messages % v_iupdates its local energy charge as follows:

e_vi← e_vi− released + recharged + received =

where the energy released is given by the the quantity of energy sent to its current neighbors (i.e.(D×^evi_2D)), the energy recharged is the amount of energy not effectively released due a possible neighborhood over estimation (that, in the current round, is smaller thanD) and computed by considering the difference between the estimated number of neighborsD and the effective ones|rcvi| (i.e. (D − |rcv_vi|) ×^evi_2D). Thus,

e_vi← e_vi− D ×e_vi

2D
+ (D − |rcvvi|) ×e_vi

2D+ X

e0 ∈rcvvi

e⁰

v _l v ₁

e ₁ e

2D

v l

v 1

e1

2D

v 2 Set of nodes with non

zero energy

(2D)²

v 3

v l

v 1 v 2

Set of nodes with non zero energy

v _{|V | 1}

e1

(2D)^{|V | 2} e1

(2D)^{|V | 1}

Fig. 2: Lower bound on the energy received by the leader from a single node

Figure 1 shows the execution of a generic round r at node v

with initial energy 1 where D = 5 and the number of v

neighbors is 3.

Correctness Proofs. In the following, we will prove that protocol A

is correct. We first prove in Lemma 1 the existence of the following invariant: the global energy stored in the system is preserved (i.e. the sum of all the energy variables e

at each v

∈ V remain constant). Note that, this is a fundamental property to ensure the correctness of the guess computed and returned by the leader. Then, in Lemma 2, we derive a lower bound on the energy that the leader will receive during the computation. Finally, in Lemma 3, we prove the terminating condition that the leader has to verify in order to check if the bound matches the network size. From these results Theorem 1 naturally follows. In the following, we use the notation e

to indicates the quantity of energy stored at round r in v

∈ V .

Lemma 1. (Invariant - Energy Conservation) At the end of each round, the sum of the energy over all the nodes of the anonymous dynamic network is an invariant and it is equal to the total energy present in the system at the beginning of the computation.

Proof. Let us notice that energy is created only during the initialization phase and then it is only transferred. Thus, in the following, we will prove that energy is never lost. For ease of presentation, in the prove we refer only to the energy e

stored at non-leader nodes (i.e. v

V \ {v

}) as v

does not send energy. At the beginning of each round r, every v

sends

r vi

2D

energy to the set of its neighbors (i.e. the released energy is D ×

r vi

2D

). However, v

does not know the exact number of current neighbors N

(r) but it just know an upper bound on them. Thus, while sending the energy, due to a possible over estimation of its neighborhood, v

may transfer more energy that the one will never received by other processes (loss of energy of (D − |N

(r) |) ×

). However, v

will know the exact number of neighbors by counting the number of received messages in the current round ( |N

(r) | = |rcv

|) and it will compensate the extra energy released.

Thus, v

will have a remaining energy of

r vi

2

+ e

. The energy initially possessed by v

was e

, at the end of r the sum of energy over nodes in N

(r) ∪ {v

} is e

. Iterating this reasoning over all nodes we have that the conservation of energy is not violated.

2

Lemma 2. Let G(r) = (V, E(r)) be a dynamic anonymous graph, let K be an upper bound on the network size and let R ∈ N

. Given the algorithm A

, at the end of round r

, the energy stored at the leader is at least e

≥ (1 − (

)

) |V |, where B = (2D)

.

Proof. Let us first compute the energy that a single node v

provides to the leader v

when it is the only one releasing energy (i.e. v

has an energy charge of e

= 1 while all the other non-leader nodes v

has no energy and e

= 0).

At round 0, v

transfers e =

to each of its neighbors. Due to 1-interval connectivity, v

has at least one neighbor v

that will receive such energy charge and will update its residual energy to e

≥

. As a consequence, an additional node (i.e. v

) will have a quantity of energy greater than 0, no matter of the adversary move.

At round 1, due to the adversary action, v

and v

may change their neighbors and a node v

, with no energy,

may become neighbor of v

. Due to the rules of the algorithm, v

will transfer to v

a quantity of energy at least

e

≥

≥

. Let us notice that the such quantity is a lower bound on the energy that an empty node may

receive after 2 rounds.

Iterating the reasoning, it is possible to define the lower bound on the energy that the leader v

received from v

after

|V |−1 rounds in case v

is the only one releasing energy, i.e. e

≥

. Considering the individual contribution of each node in V , we obtain e

≥

. However, node contributions interfere and the real quantity of energy that each of them transfers to the leader at each round is greater than the computed one; thus the formula above represents a lower bound on the energy transferred from all nodes to the leader after |V | − 1 rounds.

Due to Lemma 1, e

+ P

vi∈V \{vl}

e

= |V |, this implies that after |V | − 1 rounds, the energy not stored at the leader is, at most, |V | − e

.

Using the same argument, after 2( |V | − 1) rounds the lower bound on the energy that the leader stores is e

≥

|V |−1 vl

(2D)^|V|

+ e

. We can use the same argument even if the distribution of energy at round r = |V | is different from the uniform initial distribution, the basic idea is to consider the contribution that each node has to send to the leader independently, then summing up these contribution we will end up with the same bound.After R( |V | − 1) rounds, the energy at the leader is at least e

≥

(R−1)(|V |−1) vl

(2D)^{|V |}

+ e

vl

that is a recurrence equation with boundary condition e

= 0.

Solving the equation we obtain: e

≥ |V | × (1 − (

)

) where b = (2D)

, that is a lower bound on the energy of the leader after R × (|V | − 1) rounds. Let us recall that K ≥ |V |, thus we can compute a lower bound for the energy in the leader after RK rounds on a network of size |V |, with B = (2D)

since

≥

the following inequality holds:

e

≥ |V | × 1 −

 (2D)

− 1 (2D)



!

2

Lemma 3. Let G(r) = (V, E(r)) be a dynamic anonymous graph, let K

be an upper bound on the network size.

Given the algorithm A

, at the end of each iteration i, the leader can either accept or reject the hypothesis |V | = K

. Proof. Let us note that the algorithm outputs the exact count when the upper bound K

is equal to the real network size |V |. Initially, K

is set by running the algorithm in [16] that has been proved to provide an upper bound on the network size (i.e. K

≥ |V |). The leader can compute the difference ∆

as follows

∆

= K

− e

≥ K

− 1 −

 B − 1 B



! K

that is the difference, at round r = RK

, between the total energy stored in a network of size |V | = K

and the lower bound on the minimum amount of energy that the leader has to receive after r rounds if |V | = K

(as computed in Lemma 2).

According to the algorithm, the leader computes the minimum R

∈ N

such that r f inal

= R

K

satisfies

∆

< 1. At round r f inal

two cases are possible:

1. The energy accumulated in the leader e

is less or equal than K

− 1: in this case, we have necessary that

|V | < K

. By construction, in fact, R

is selected in such a way that the quantity ∆

< 1; thus, if the real network size is K

, the leader must collect e

> K

−1. On the contrary, the only possibility is that |V | < K

since in this case the quantity of energy in V will not allow the leader to reach a value e

= K

− 1 +  with

 > 0.

2. The energy accumulated in the leader e

= K

− 1 +  (with  > 0): this implies that there are at least K

nodes in V . Considering that K

is an upper bound we have that necessary |V | = K

.

2

Theorem 1. Let G(r) = (V, E(r)) be a dynamic anonymous graph and let K

be an upper bound on the network

size. If the adversary is a dynamic graph adversary with bounded degree and any process v

∈ V knows the upper

bound D on the number of neighbors, then the algorithm A

satisfies the consciousness and convergence properties

Proof. Let us first prove the convergence property. A

, during the Step 1, computes an upper bound K

on the size of the network (i.e. K

≥ |V |) and then it moves to Step 2 starting a sequence of iteration I = {i

, ..., i

}, each one taking as input an upper bound K

. According to Lemma 3, at the end of an iteration i

, the leader checks the terminating condition, evaluates the hypothesis K

= |V | and in case of rejection, it decreases by one the upper bound considered in the following iteration. Considering that (i) K

is an upper bound on the real network size and (ii) every iteration i

starts with a new upper bound K

= K

− 1 it follows that, in a finite number of iterations, A

will evaluate the real size of the network accepting the hypothesis K

= |V |.

The consciousness is also ensured by Lemma 3, considering that when the leader accepts the hypothesis K

= |V | starts to disseminate a

message letting the algorithm terminate at each node.

2

4.1 Complexity and Discussion

Theorem 2. Let G(r) = (V, E(r)) be a dynamic anonymous graph and let K

be an upper bound on the network size. If the adversary is a dynamic graph adversary with bounded degree and any process v

∈ V knows the upper bound D on the number of neighbors, then the algorithm A

outputs the correct size of the network after at most O(e

K

(K

− 1)) rounds.

Proof. The claim follows from Lemma 2 and Lemma 3 by considering that each iteration i of the algorithm lasts

∆

(K

) × K

, where ∆

(K

) is the number of K

− 1 rounds that the algorithm has to execute in order to check the hypothesis |V | = K

(cfr. Lemma 3). Moreover, we have that the maximum number of iterations is K

(i.e., the worst case obtained starting from evaluating the hypothesis on the size |V | = K

when the real size is |V | = 1). ∆

(K

) can be computed by solving ∆

< 1 inequality obtaining:

∆

(K

) ≥

&

log(

i

) log(

)

' + 1

where B = (2D)

.

Let us notice that, in the worst case, D = K

, so we have ∆

(K

) = Θ



 log

(

)



. Since the limit lim



R(Ki) e^K2i

 =

0 we have that the number of rounds for each iteration is O 

e

(K

− 1) 

this seamlessly leads to the theorem.

2

The complexity aforementioned is a direct consequence of the energy release mechanism where each non leader node transfers half of its energy at each round. Let us suppose to modify the algorithm in such a way that each node sends the whole energy to its neighbors. In this case the problem became equivalent to token circulation, the trivial example is a chain {v

, v

, ..., v

}, that is transformed at odd rounds in v

, v

, ..., v

and in even rounds as v

, v

, ..., v

, this dynamic adversary will prevent the initial energy present in v

to reach other nodes apart v

. On the contrary halving the energy allow us to obtain the bound on energy dissemination (See Lemma 2). Let us remark that changing the quantity of energy sent by nodes (i.e. sending a fraction different from

) does not change the complexity from being exponential since the termination round is only influenced by a multiplicative factor.

5 Unconscious Counting resilient to a Dynamic Graph Adversary

This section shows that the impossibility of designing a counting algorithm without any network knowledge assump- tion (i.e., impossibility of designing a counting resilient to a dynamic graph adversary) presented in [16] does not hold if if we consider unconscious counting algorithms. To prove such claim, we will propose an algorithm, namely A

, that is able to eventually count the number of processes in the dynamic anonymous network without having any assumption on the network. A

is actually a modification of the algorithm presented in Section 4 where nodes have to cope with the uncertainty about the number of neighbors (and thus, with the uncertainty about the energy they have to release in each round).

A

works in the following way: each non-leader node v

starts, at round r

, with energy quantity e

← 1 and

it transfers half of its current energy to the neighbors. However, v

has no knowledge about the network and thus it cannot know the exact number of neighbors at round r before receiving messages, but it can only guess such number.

Thus, v

supposes to have D

neighbors and it broadcasts a quantity of energy

max

(as if there are really D

neighbors). Then v

starts to collect messages transmitted by its neighbors at the beginning of the round and it stores such messages in a local variable rcv

. At the end of the round, v

updates its energy, as in the previous algorithm, to preserve the quantity of energy over all the network.

Notice that, if the real number of neighbors at round r is lower than the estimation (i.e., |rcv

| ≤ D

) then the global energy conserved among all the processes is still constant (this is due to the compensation done by v

at the end of the round, based on the effective number of received messages). On the contrary, if the number of neighbors is greater than the estimation (i.e., |rcv

| > D

) then, there is the release of a local surplus of energy. As an example, consider the case where v

has energy e

the estimation of neighbors is D

= 2 and the real number of neighbors is |rcv

| = 8. When v

sends

to each neighbors, the total amount of energy transferred is twice the energy stored by v

(i.e., the energy transferred is 8 ×

= 2e

while node v

had only e

residual energy). However, since v

adjusts its local residual energy considering the number of received messages |rcv

|, it follows that its residual energy will become negative and globally the energy is still preserved. Considering the previous example at the end of the round v

stores a residual energy −e

.

Unfortunately, the local surplus of positive/negative energy could create, in the leader, a temporary value of energy e

that is greater than |V | or negative. Moreover, the adversary could change, at each round, the degree of nodes in order to avoid the convergence of the leader. To overcome these issues each processes stores locally the highest number of neighbors it has ever seen and it uses the double of such number as D

. In this way, the surplus of local negative/positive energy that the adversary can create is upper bounded by a function f ( |V |): each node v

can increase D

at most log( |V |) times, from 1 to |V |. This implies that the worst case adversary cannot create an infinite surplus of local energy. Thus, the adversary could delay the convergence of the count only a finite number of rounds.

AlgorithmAN oK– Unconscious Counting resilient to a Dynamic Graph Adversary.

leader : The leadervlmaintains the following local variables: (i)e_vl← 1 representing the initial energy charge and (ii) rcvvl← ∅ is a set variable where vl

stores all the messages received during each round. (iii)count_vl← 0 this variable is used to keep trace of the latest estimated count.

for each roundr:

– Send phase of roundr: at the beginning of each round, vlbroadcasts aENERGY RELEASE(0) message releasing no energy.

vlbroadcastsCOUNT(devle, r).

– Receive and Computation phases of roundr:ENERGY RELEASE(e⁰) messages are stored in the rcv_vlvariable. At the end of the round, when all the messages have been received,vlupdates, its local energy charge as follows:

e_vl← e_vl+ X

e0 ∈rcvvl

e⁰

vlsetscount_vl← de_vle

anonymous node: Each non leader nodev_imaintains the following local variables: (i)e_vi← 1 representing the initial energy charge of vi, (ii)rcv_vi← ∅ is a set variable wherev_istores all the messages received during each round and (iii)D_max← 1 is an integer variable storing the maximum number of neighbor vihas ever had (initially set to1 as it has no knowledge about the network). (iv) count_vi ← 0 this variable is used to keep trace of the latest count estimate seen by the node (v)r count_vi ← 0 is the round number associated with the latest count accepted.

for each roundr:

– Send phase of roundr: at the beginning of each round, vibroadcasts aENERGY RELEASE(_2Dmax^evi ) message, releasing at most half of its energy to its neighbors.

– Receive and Computation phases of roundr:

for each messagem∈ rcv_visuch thatm is anENERGY RELEASEmessage,viupdates its local energy charge as in the previous algorithm:

e_vi ← evi− Dmax× e_vi 2Dmax

+ (Dmax− |rcvvi|) × e_vi 2Dmax

+ X

e0 ∈rcvvi

e⁰

In addition, if|rcv_vi| > Dmax,vialso updates the maximum number of neighbors it has ever saw by settingDmax← 2|rcv_vi|.

for each messagem∈ rcv_visuch thatm is anCOUNTmessage, if the round number inm is greater than r count_viupdatescount_viandr count_vi with the content ofm.

Correctness Proofs. In the following, we will prove that protocol A

converges to the exact count in a finite

number of rounds. We first prove that the quantitive of negative energy that the dynamic adversary is able to create

is bounded by a function of the network size |V | (Lemma 4 ). From this result, we prove that the leader will obtain the correct count in a finite but unknown number of rounds (Lemma 6), so we will prove that A

respects the convergence property, but not the consciousness. Let us notice that since the energy transfer mechanism is the same of A

the global invariant on energy still holds, so Lemma 1 keeps holding for A

too. Moreover, it is clear that for each round r the leader will receive energy from its neighbors. So, even if it is not possible to have a bound like the one obtained in Lemma 2, it is straightforward to see that the absolute value of the sum of energy that the leader receives is a monotonically increasing function.

Lemma 4. Let G(r) = (V, E(r)) be a dynamic anonymous graph. During any execution of A

, the amount of negative energy that can be generated is finite. Moreover, during any round r a single node v

∈ V with energy e

can create at most ( |V | − 2)e

negative energy.

Proof. Let us focus on the negative energy that can be generated during the execution of the algorithm by a generic node v

∈ V . Let E

: {r

, r

, ...., r

} be the set of rounds (not necessarily consecutive) in which v

creates negative energy; we will show that the number t is finite. For the generic round r

∈ E

we must have that |rcv

| >

2D

; this follows by imposing

+ ( |rcv

| − D

)

< 0. This means that we have at least |rcv

| ≥ 2D

+ 1, and at the end of round r

the number D

will be doubled. Since |rcv

| ≤ |V | and D

≥ 1, we have that the condition |rcv

| > 2D

could happen at most log( |V |) times. So, t ≤ O(log(|V |)). Moreover, the negative energy created by a node v

with energy e during a single round is at most ( |rcv

|−2D

)e that is maximized when

|rcv

| = |V | and D

= 1. 2

Lemma 5. Let G(r) = (V, E(r)) be a dynamic anonymous graph. During any execution of A

, for any  ∈ R

there exists a round r

after which the amount of negative energy that could be transferred to the leader in the following rounds is less than .

Proof. Due to the invariant on energy (Lemma 1), we have that the negative energy that each node could create is related to the energy that the nodes already possess (since the sum of negative and positive energy has to be equal zero). In addition, for Lemma 1 and for the monotonically increasing energy received by the leader, we have that, if no negative energy is created, the absolute value of energy in V \ {v

} is a monotonically decreasing function of r. The maximum amount of negative energy that can be created starting from round r is bounded (see lemma 4) and from the previous consideration it is a monotonic function f of P

∀v∈V \{vl}

|e

|. From Lemma 2 we have that ∀

∈ R

∃r

∈ N

| P

∀v∈V \{vl}

|e

| ≤ 

, since f is monotonic exists 

such that f (

) ≤ . 2

Lemma 6. Let G(r) = (V, E(r)) be a dynamic anonymous graph and let us consider an execution of A

. Then,

∀v

lim

count

= |V |. So A

is a counting algorithm that respects the convergence property.

Proof. Lemma 5 shows that there exists a round r

after which the maximal amount of negative energy that can be created in the network is bounded by a quantity  that can be made arbitrarily small. For energy conservation Lemma, this means that the total amount of negative and positive energy in V \ {v

} is bounded at each round by a monotonically decreasing function of the round number. So lim

( |V | − e

) = 0, this means that there exists a round r such that ∀r

≥ r holds |V | − e

< 1. So the variable count

will be equals to |V | ∀r

≥ r. This means that

A

respects the convergence property. 2

The previous Lemma has an interesting implication: there exists a round r such that ∀r

≥ r holds |V | − e

< 1.

However, this condition is not detectable by any node in the network. As a consequence, A

respects convergence property but not conscious property. Unconscious algorithms can be used in any practical context where the safety of the application does not depend by a correct count and where liveness and/or fairness need just an eventually correct count (e.g. fair load balancing). In a companion paper [15], we show a performance evaluation of A

and we propose an heuristics to let A

terminate together with the comparison between the basic A

and the heuristic- based one.

Energy vs Mass Conservation. Our idea of energy transfer and the principle of energy conservation is similar to the

one used in [13] where a global invariant called conservation of mass is used and a push-only mechanism is employed

to implement a gossip-based protocol for aggregation. Despite the similarities in the principle, the underling graph

considered in [13] is obtained trough a sampling function while our model is governed by a worst case adversary (as discussed in Section 2). Moreover, Kempe et Al. assume that each node knows in advance the number of neighbors for the message-exchange while in our model this is not possible. As a consequence, they obtain probabilistic bounds on the convergence time and each node of the system converges to the average of the inputs value while in our algorithm the leader always absorbs energy converging to the correct count and the other nodes converge to zero.

6 Conclusion

We presented a distributed (deterministic) algorithm that assumes the existence of a unique leader node in order to precisely count the number of nodes of the network. The leader node executes a different code from the rest of the nodes and acts as a sink for the energy transfer. This algorithm is resilient to an adversary that can change the communication graph at any round with the constraint of not creating disconnected graphs or graphs including nodes with a degree that exceed a given bound.

Secondly, we have shown that the conjecture presented in [16] stating that “in dynamic networks ensuring 1- interval connectivity we cannot count even with a leader” is still valid but only if the count is conscious. We have indeed presented an algorithm that is able to unconsciously count the size of the network. Thus the conjecture can be reworded as follows “in dynamic networks ensuring 1-interval connectivity we cannot count consciously even with a leader”. This leaves open an interesting problem concerning the existence of a conscious counting algorithm resilient to a dynamic graph adversary only constrained to ensure 1-interval connectivity.

Let us finally remark that our algorithms work in a ever changing dynamic graph. This continuous dynamic be- havior is similar to the churn analyzed in [6] for building regular registers. We believe that these forms of dynamic behaviors are the natural way to think about dynamic distributed systems with respect to distributed systems whose form of dynamic behavior eventually stabilizes such as [1,10].

References

1. M. K. Aguilera, I. Keidar, D. Malkhi, and A. Shraer. Dynamic atomic storage without consensus. J. ACM, 58(2):7, 2011.

2. D. Angluin. Local and global properties in networks of processors (extended abstract). In STOC, pages 82–93. ACM, 1980.

3. J. Aspnes, F. E. Fich, and E. Ruppert. Relationships between broadcast and shared memory in reliable anonymous distributed systems. Distrib. Comput., 18(3):209–219, February 2006.

4. H. Attiya, M. Snir, and M. K. Warmuth. Computing on an anonymous ring. J. ACM, 35(4):845–875, October 1988.

5. R. Baldoni, M. Bertier, M. Raynal, and S. Tucci Piergiovanni. Looking for a definition of dynamic distributed systems. In PaCT, pages 1–14, 2007.

6. R. Baldoni, S. Bonomi, and M. Raynal. Implementing a Regular Register in an Eventually Synchronous Distributed System Prone to Continuous Churn. IEEE Transaction on Parallel Distributed Systems, 23(1):102–109, 1 2012.

7. P. Boldi and S. Vigna. Computing anonymously with arbitrary knowledge. In PODC, pages 181–188. ACM, 1999.

8. A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. CoRR, abs/1012.0009, 2010.

9. J. Chalopin, Y. M´etivier, and T. Morsellino. On snapshots and stable properties detection in anonymous fully distributed systems (extended abstract). In SIROCCO, volume 7355, pages 207–218. Springer, 2012.

10. G. Chockler, S. Gilbert, V. Gramoli, P. M. Musial, and A. A. Shvartsman. Reconfigurable distributed storage for dynamic networks. J. Parallel Distrib. Comput., 69(1):100–116, 2009.

11. P. Fraigniaud, A. Pelc, D. Peleg, and S. P´erennes. Assigning labels in unknown anonymous networks. In PODC, pages 101–111. ACM, 2000.

12. M. Jelasity, A. Montresor, and ¨ O. Babaoglu. Gossip-based aggregation in large dynamic networks. ACM Trans. Comput. Syst., 23(3):219–252, 2005.

13. D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In FOCS, pages 482–491, 2003.

14. F. Kuhn, N. Lynch, and R. Oshman. Distributed computation in dynamic networks. In STOC, 2010, pages 513–522, New York, NY, USA, 2010. ACM.

15. G. Di Luna, S. Bonomi, I. Chatzigiannakis, and R. Baldoni. Counting in Anonymous Dynamic Networks: An Experimental Perspective. In ALGOSENSORS (to appear), 2013, http://www.dis.uniroma1.it/˜midlab/articoli/main_

2.pdf.

16. O. Michail, I. Chatzigiannakis, and P. G. Spirakis. Naming and counting in anonymous unknown dynamic networks. In (to

appear) 15th International Symposium on Stabilization, Safety, and Security of Distributed Systems, 2013.

17. R. O’Dell and R. Wattenhofer. Information dissemination in highly dynamic graphs. In DIALM-POMC, pages 104–110, New York, NY, USA, 2005. ACM.

18. M. Yamashita and T. Kameda. Computing on an anonymous network. In PODC, pages 117–130, New York, NY, USA, 1988.

ACM.