---
_id: '619'
abstract:
- lang: eng
text: '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.'
accept: '1'
author:
- first_name: Philipp
full_name: Brandes, Philipp
last_name: Brandes
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: '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'
apa: 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
bibtex: '@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} }'
chicago: 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.
ieee: 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.
mla: 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.
short: '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.'
date_created: 2017-10-17T12:42:52Z
date_updated: 2020-05-07T05:28:03Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1145/2414815.2414818
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T06:47:15Z
date_updated: 2018-03-15T06:47:15Z
file_id: '1244'
file_name: 619-Brandes_MadHTADDS12_01.pdf
file_size: 346044
open_access: 1
relation: main_file
success: 1
file_date_updated: 2018-03-15T06:47:15Z
page: 9-14
project:
- _id: '1'
name: SFB 901
- _id: '5'
name: SFB 901 - Subprojekt A1
- _id: '2'
name: SFB 901 - Project Area A
publication: Proceedings of the 4th Workshop on Theoretical Aspects of Dynamic Distributed
Systems (TADDS)
series_title: ICPS
status: public
title: Distributed Computing in Fault-Prone Dynamic Networks
type: conference
user_id: '15504'
year: '2012'
...