Distributed Computing in Fault-Prone Dynamic Networks

P. Brandes, F. Meyer auf der Heide, in: Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14.

Download
Restricted 619-Brandes_MadHTADDS12_01.pdf 346.04 KB
Conference Paper
Author
Abstract
Dynamics in networks is caused by a variety of reasons, like nodes moving in 2D (or 3D) in multihop cellphone networks, joins and leaves in peer-to-peer networks, evolution in social networks, and many others. In order to understand such kinds of dynamics, and to design distributed algorithms that behave well under dynamics, many ways to model dynamics are introduced and analyzed w.r.t. correctness and eciency of distributed algorithms. In [16], Kuhn, Lynch, and Oshman have introduced a very general, worst case type model of dynamics: The edge set of the network may change arbitrarily from step to step, the only restriction is that it is connected at all times and the set of nodes does not change. An extended model demands that a xed connected subnetwork is maintained over each time interval of length T (T-interval dynamics). They have presented, among others, algorithms for counting the number of nodes under such general models of dynamics.In this paper, we generalize their models and algorithms by adding random edge faults, i.e., we consider fault-prone dynamic networks: We assume that an edge currently existing may fail to transmit data with some probability p. We rst observe that strong counting, i.e., each node knows the correct count and stops, is not possible in a model with random edge faults. Our main two positive results are feasibility and runtime bounds for weak counting, i.e., stopping is no longer required (but still a correct count in each node), and for strong counting with an upper bound, i.e., an upper bound N on n is known to all nodes.
Publishing Year
Proceedings Title
Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS)
forms.conference.field.series_title_volume.label
ICPS
Page
9-14
LibreCat-ID
619

Cite this

Brandes P, Meyer auf der Heide F. Distributed Computing in Fault-Prone Dynamic Networks. In: Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS). ICPS. ; 2012:9-14. doi:10.1145/2414815.2414818
Brandes, P., & Meyer auf der Heide, F. (2012). Distributed Computing in Fault-Prone Dynamic Networks. In Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS) (pp. 9–14). https://doi.org/10.1145/2414815.2414818
@inproceedings{Brandes_Meyer auf der Heide_2012, series={ICPS}, title={Distributed Computing in Fault-Prone Dynamic Networks}, DOI={10.1145/2414815.2414818}, booktitle={Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS)}, author={Brandes, Philipp and Meyer auf der Heide, Friedhelm}, year={2012}, pages={9–14}, collection={ICPS} }
Brandes, Philipp, and Friedhelm Meyer auf der Heide. “Distributed Computing in Fault-Prone Dynamic Networks.” In Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS), 9–14. ICPS, 2012. https://doi.org/10.1145/2414815.2414818.
P. Brandes and F. Meyer auf der Heide, “Distributed Computing in Fault-Prone Dynamic Networks,” in Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14.
Brandes, Philipp, and Friedhelm Meyer auf der Heide. “Distributed Computing in Fault-Prone Dynamic Networks.” Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed Systems (TADDS), 2012, pp. 9–14, doi:10.1145/2414815.2414818.
Main File(s)
File Name
619-Brandes_MadHTADDS12_01.pdf 346.04 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-15T06:47:15Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar