@inproceedings{GJRSST-TCDTSSCGL-10,
Title = {Time Complexity of Distributed Topological Self-Stabilization: The Case of Graph Linearization},
Author = {Gall, Dominik and Jacob, Riko and Richa, Andr\´ea and Scheideler, Christian and Schmid, Stefan and T\"aubig, Hanjo},
Booktitle = {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.},
Url = {http://www.net.t-labs.tu-berlin.de/papers/GJRSST-TCDTSSCGL-10.pdf},
Categories = {tlabs_yes, bei_anja, group_feldmann},
Projectname = {distributed_systems and distr_sys_select and thisisimportant}
}