## Agreement in Partitioned Dynamic Networks

Adam Sealfon and Aikaterini Sotiraki

Massachusetts Institute of Technology {asealfon,katesot}@mit.edu

Abstract. In the dynamic network model, the communication graph is assumed to be connected in every round but is otherwise arbitrary. We consider the related setting of p -partitioned dynamic networks , in which the communication graph in each round consists of at most p connected components. We explore the problem of k -agreement in this model for k ≥ p . We show that if the number of processes is unknown then it is impossible to achieve k -agreement for any k and any p ≥ 2. Given an upper bound n on the number of processes, we provide algorithms achieving k -agreement in p n ( -p ) rounds for k = p and in O n//epsilon1 ( ) rounds for k = (1 + /ceilingleft /epsilon1 ) p /ceilingright .

Keywords: distributed algorithms, dynamic networks, agreement, partitioned networks

## 1 Introduction

Dynamic graphs are a model for distributed algorithms which were introduced by Kuhn, Lynch and Oshman [1]. In this paper we explore the capabilities and limitations of a modification to the dynamic graph model addressing additional challenges arising in wireless communication.

In the dynamic graph model, the network is assumed merely to be connected in each round, with no additional assumptions about consistency from round to round. We weaken this assumption further, allowing the network to consist of more than one connected component. Formally,

Definition 1. A dynamic graph G = ( V, E ) is said to be p -partitioned if at each round t , it consists of at most p connected components.

Processes communicate in synchronous rounds using local broadcast. The edges in each round are chosen by an adaptive adversary.

In this setting, many of the problems usually considered in the dynamic network model cannot be solved. In particular, tasks such as token dissemination, leader election and consensus which cannot be solved in partitioned static networks clearly are also impossible in partitioned dynamic networks. We consider the problem of k -agreement for constant k , which can be solved in static p -partitioned networks as long as k ≥ p . The conditions for k -agreement are the following:

- 1. Agreement: All decision values are in W, where W is a subset of the initial values with | W | = k .
- 2. Validity: Any decision value is the initial value of some process.
- 3. Termination: All processes eventually decide.

We show that k -agreement is not possible in the setting of p -partitioned dynamic networks if the number of processes is unknown, but that it can be achieved for any k ≥ p given an upper bound on the number of processes. Our results are qualitatively different from the case of ordinary dynamic networks, for which there are known consensus protocols which do not assume knowledge of the size of the network [2].

Theorem 1. For all p ≥ 2 , k ≥ 1 there is no algorithm which will solve k -agreement on p -partitioned dynamic graphs given no information about the size of the network.

Theorem 2. For any p ≥ 1 , we can solve p -agreement in p n ( -p -1) + 1 rounds on any p -partitioned dynamic graph, where n is a known upper bound on the number of vertices.

Theorem 3. For any /epsilon1 &gt; 0 , p ≥ 1 , we can solve /ceilingleft (1+ ) /epsilon1 p /ceilingright -agreement in O n//epsilon1 ( ) rounds on any p -partitioned dynamic graph, where n is a known upper bound on the number of vertices.

## 2 Impossibility with unknown network size

It suffices to consider the case p = 2. Let k ≥ 1, and assume there exists some algorithm which solves k -agreement on 2-partitioned dynamic networks. We construct an execution with k +1 distinct decision values 1 , . . . , k +1.

Consider some process v . If after some point in the execution v has no neighbors for sufficiently many rounds, v will eventually decide on some value it has heard and terminate. If all values it has received up to this point are equal to its input value, then by the validity requirement this must be its decision value.

We divide the execution into k + 1 phases. In phase i , the communication graph G consists of a single isolated process a i and a path P i connecting all the other processes. The communication graph will stay unchanged within each phase, and at the end of phase i process a i will decide on the value i .

Let t &gt; 0 be sufficiently large, as determined later. Path P consists of k +1 segments, each containing 2 t +1 processes. Each process in the i th segment has input value i . Let a i be the middle vertex in segment i , and let a , a ′ i ′′ i be its neighbors in P . In phase i , G will be produced from P by turning a i into an isolated vertex and adding an edge connecting a ′ i and a ′′ i to form path P i .

If phase i begins on round t i &lt; t , then at the beginning of the phase process a i has heard from 2 t i other processes, all of which share its input value i . During phase i process a i has no neighbors, so as observed above, it must decide on value i within finitely many rounds. Note that this number of rounds is independent of t as long as t &gt; t i . Consequently, taking t &gt; t k +1 , we have produced an execution in which process a i decides on value i for each i , proving the impossibility result.

## 3 Algorithms for known network size

The proof in the previous setting relied heavily on processes not knowing the total number n of processes. This is no coincidence. In this section we show that if processes do know the number of process n or an upper bound on n , they can solve k -agreement in a p -partitioned dynamic network for any k ≥ p .

The algorithm is extremely simple. Each process v stores the smallest value m v it has seen so far. On each round, the process broadcasts this value to its neighbors. If it receives a smaller value, it updates m v . After some fixed number γ of rounds, each process outputs the smallest value it has seen.

We now show that with γ = p n ( -p -1) + 1 rounds, this algorithm solves p -agreement on p -partitioned graphs with at most n vertices. Since the number of rounds depends on n , this does not violate the impossibility result of the previous section. Consider some dynamic network G = ( V, E ) with initial inputs x . Let m t v ( ) be the value of variable m v at the beginning of round t , and let S t ( ) = { m t v ( ) : v ∈ V } be the set of the minimum values heard by each process by some round t . For each i ≤ p , let s i ( ) t be the i th smallest value in S t ( ), let V i ( ) t ⊆ V be the set of processes with value s i ( ) t in round t , and let A t i ( ) = | V 1 ( ) t | + · · · + | V i ( ) t | be the number of processes with value at most s i ( ). Let t V p +1 ( ) = t V \ ( V 1 ( ) t ∪·· ·∪ V p ( )). Observe that the value t s i ( ) depends t on the round, so the value of the processes in the set V i ( ) may be different in t different rounds. We make use of the potential function

$$\Phi ( t ) = p \cdot | V _ { 1 } ( t ) | + ( p - 1 ) \cdot | V _ { 2 } ( t ) | + \dots + 2 \cdot | V _ { p - 1 } ( t ) | + | V _ { p } ( t ) | = A _ { 1 } ( t ) + \dots + A _ { p } ( t ).$$

We will show that as long as there are more than p values in S t ( ), Φ t ( +1) &gt; Φ t ( ).

Note that S t ( + 1) ⊆ S t ( ) and that for any process v the variable m v is nonincreasing. Consequently for all i we have that the variable A t i ( ) never decreases. It remains to show that as long as | S t ( ) | &gt; p , there is an i such that A t i ( +1) &gt; A i ( ). t But the communication graph in round t consists of at most p connected components, so there must be a pair of vertices u ∈ V j ( ) t , v ∈ V /lscript ( ) t with j &lt; /lscript and j ≤ p such that uv ∈ E t ( ). Then in round t +1 process v has value at most s j ( ), so t A j ( t +1) &gt; A j ( ). Since each t A t i ( ) is nondecreasing, this implies that Φ t ( +1) &gt; Φ t ( ).

But the initial value Φ (0) ≥ p +( p -1) + · · · +1 = p p ( +1) 2. The maximum / value of Φ in any round t ′ for which | S t ( ′ ) | &gt; p occurs for | V 1 ( t ′ ) | = n -p , | V 2 ( t ′ ) | = | V 3 ( t ′ ) | = · · · = | V p ( t ′ ) | = 1, so if | S t ( ) | &gt; p then we have that

$$\Phi ( t ) \leq p ( n - p ) + p ( p - 1 ) / 2.$$

Since Φ t ( ) must increase by at least one in each round as long as | S t ( ) | &gt; p , after at most

$$\gamma = 1 + \Phi ( t ^ { \prime } ) - \Phi ( 0 ) \leq p ( n - p - 1 ) + 1$$

rounds we will have that | S γ ( ) | ≤ p , and so the algorithm above achieves p -agreement.

We now show that if k ≥ (1 + /epsilon1 ) p , the same algorithm achieves k -agreement after γ = O n//epsilon1 ( ) rounds. Similarly to the above, for i ≤ k let V i ( ) t be the

set of processes with the i th smallest value s i ( ) t in round t , and let V k +1 ( ) = t V \ ( V 1 ( ) t ∪ · · · ∪ V k ( )). We will show that the potential function t

$$\Phi ( t ) = k \cdot | V _ { 1 } ( t ) | + ( k - 1 ) \cdot | V _ { 2 } ( t ) | + \cdots + 2 \cdot | V _ { k - 1 } ( t ) | + | V _ { k } ( t ) |$$

increases by at least 1 + k -p in each round. Define a graph G t ′ ( ) on vertex set { V 1 ( ) t , . . . , V k +1 ( ) t } with an edge between V i ( ) t , V j ( ) t ∈ V ′ if there are vertices v i ∈ V i ( ), t v j ∈ V j ( ) which are connected by an edge on round t t in the original graph G . Since G consists of at most p connected components, by construction G t ′ ( ) must also consist of at most p connected components. If V i ( ) t and V j ( ) t are in the same connected component of G t ′ ( ) for i &lt; j , then we can consider some simple path connecting them. Let the indices of the vertices on this path be ( i = a (0) , a (1) , . . . , a ( r ) = j ). For each edge V a q ( ) ( ) t V a q ( +1) ( ) in the path with t a q ( +1) &gt; a q ( ), we have that the potential function Φ increases by a q ( +1) -a q ( ). Consequently a component containing V i ( ) and t V j ( ) for t i &lt; j corresponds to an increase in Φ by at least j -i . Therefore a connected component in G t ′ ( ) consisting of at least s sets V i ( ) t corresponds to an increase in Φ by at least s -1. There are k +1 sets V 1 ( ) t , . . . , V k +1 ( ) but only t p connected components, so we must have that Φ increases in each round by at least k +1 -p &gt; 1+ k/epsilon1/ (1+ ). /epsilon1 But identically to the above we have that Φ t ( ′ ) -Φ (0) ≤ k n ( -k -1) in any round t ′ for which k -agreement has not yet been achieved. Consequently after at most

$$\gamma = 1 + \frac { k ( n - k - 1 ) } { 1 + k \epsilon / ( 1 + \epsilon ) } < 1 + \frac { ( 1 + \epsilon ) n } { \epsilon } = O ( n / \epsilon )$$

rounds the algorithm above will achieve k -agreement.

## 4 Discussion

We have introduced a variant of dynamic networks in which the network is no longer assumed to be connected in each round. We show that it remains possible to solve nontrivial problems under the weaker assumption that the network at each round consists of at most p connected components. In particular, we show that given an upper bound on the size of the network, it is possible to solve k -agreement in a p -partitioned dynamic network.

It would be interesting to consider whether it is possible to achieve agreement in fewer rounds in a p -partitioned dynamic network. Our algorithms solve /ceilingleft (1 + /epsilon1 ) p /ceilingright -agreement in O n//epsilon1 ( ) rounds and p -agreement in p n ( - -p 1)+1 rounds. It is unclear whether this dependence on p is intrinsic or whether p -agreement can be achieved in O n ( ) rounds regardless of p . It would also be interesting to explore whether p -agreement can be achieved in fewer rounds with high probability against a nonadaptive adversary. It also remains open what additional problems can be solved in this model.

Acknowledgments. We would like to thank Mohsen Ghaffari and Nancy Lynch for helpful discussions. This material is based upon work supported in part by

the National Science Foundation Graduate Research Fellowship under Grant No. 1122374.

## References

- 1. Fabian Kuhn, Nancy Lynch and Rotem Oshman. Distributed Computation in Dynamic Graphs. In Proc. 42nd ACM Symp. on Theory of Computing (STOC) , 2010.
- 2. Rotem Oshman. Distributed Computation in Wireless and Dynamic Networks. PhD Thesis.
Adam Sealfon Aikaterini Sotiraki
Agreement in Partitioned Dynamic Networks
In the dynamic network model, the communication graph is assumed to be
connected in every round but is otherwise arbitrary. We consider the related
setting of $p$-partitioned dynamic networks, in which the communication graph
in each round consists of at most $p$ connected components. We explore the
problem of $k$-agreement in this model for $k\geq p$. We show that if the
number of processes is unknown then it is impossible to achieve $k$-agreement
for any $k$ and any $p\geq 2$. Given an upper bound $n$ on the number of
processes, we provide algorithms achieving $k$-agreement in $p(n-p)$ rounds for
$k=p$ and in $O(n/\epsilon)$ rounds for $k=\lceil (1+\epsilon)p \rceil$.