| Citation key |
GJRSST-TCDTSSCGL-10 |
| Author |
Gall, Dominik and Jacob, Riko and Richa, Andréa and Scheideler, Christian and Schmid, Stefan and Täubig, Hanjo |
| Title of Book |
Proceedings of 9th Latin American Theoretical Informatics Symposium (LATIN '10) |
| Pages |
294–305 |
| Year |
2010 |
| ISBN |
978-3-642-12199-9 |
| ISSN |
0302-9743 |
| DOI |
http://dx.doi.org/10.1007/978-3-642-12200-2_27 |
| Location |
Oaxaca, Mexico |
| Address |
Berlin / Heidelberg, Germany |
| Volume |
6034 |
| Month |
April |
| Publisher |
Springer |
| Series |
Lecture Notes in Computer Science (LNCS) |
| Abstract |
Topological self-stabilization is an important concept to build robust open distributed systems (such as peer-to-peer systems) where nodes can organize themselves into meaningful network topologies. The goal is to devise distributed algorithms that converge quickly to such a desirable topology, independently of the initial network state. This paper proposes a new model to study the parallel convergence time. Our model sheds light on the achievable parallelism by avoiding bottlenecks of existing models that can yield a distorted picture. As a case study, we consider local graph linearization–i.e., how to build a sorted list of the nodes of a connected graph in a distributed and self-stabilizing manner. We propose two variants of a simple algorithm, and provide an extensive formal analysis of their worst-case and best-case parallel time complexities, as well as their performance under a greedy selection of the actions to be executed. |
