Distributed computation in dynamic networks
Authors:
Open Access
- 5 June 2010
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 513-522
Abstract
In this paper we investigate distributed computation in dynamic networks in which the network topology changes from round to round. We consider a worst-case model in which the communication links for each round are chosen by an adversary, and nodes do not know who their neighbors for the current round are before they broadcast their messages. The model captures mobile networks and wireless networks, in which mobility and interference render communication unpredictable. In contrast to much of the existing work on dynamic networks, we do not assume that the network eventually stops changing; we require correctness and termination even in networks that change continually. We introduce a stability property called T -interval connectivity (for T >= 1), which stipulates that for every T consecutive rounds there exists a stable connected spanning subgraph. For T = 1 this means that the graph is connected in every round, but changes arbitrarily between rounds. We show that in 1-interval connected graphs it is possible for nodes to determine the size of the network and compute any com- putable function of their initial inputs in O(n2) [O (n superscript 2)] rounds using messages of size O(log n + d), where d is the size of the input to a single node. Further, if the graph is T-interval connected for T > 1, the computation can be sped up by a factor of T, and any function can be computed in O(n + n2/T) [(n + n superscript 2 /T)] rounds using messages of size O(log n + d). We also give two lower bounds on the token dissemination problem, which requires the nodes to disseminate k pieces of information to all the nodes in the network. The T-interval connected dynamic graph model is a novel model, which we believe opens new avenues for research in the theory of distributed computing in wireless, mobile and dynamic networksKeywords
This publication has 34 references indexed in Scilit:
- Broadcasting in dynamic radio networksJournal of Computer and System Sciences, 2009
- Computation in networks of passively mobile finite-state sensorsDistributed Computing, 2006
- Consensus Problems in Networks of Agents With Switching Topology and Time-DelaysIEEE Transactions on Automatic Control, 2004
- Compact Routing Schemes for Dynamic Ring NetworksTheory of Computing Systems, 2004
- On the complexity of global computation in the presence of link failures: the general caseDistributed Computing, 1995
- On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomizationJournal of Computer and System Sciences, 1992
- A survey of gossiping and broadcasting in communication networksNetworks, 1988
- Probabilistic counting algorithms for data base applicationsJournal of Computer and System Sciences, 1985
- Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing TopologyIEEE Transactions on Communications, 1981
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978