Agreement in Partitioned Dynamic Networks

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\ge 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\ge 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$.

A summary of these results will appear as a brief announcement in DISC 2014