TY - JOUR
T1 - A Note on the Parallel Runtime of Self-Stabilizing Graph Linearization
AU - Gall, Dominik
AU - Jacob, Riko
AU - Richa, Andrea
AU - Scheideler, Christian
AU - Schmid, Stefan
AU - Täubig, Hanjo
N1 - Funding Information:
Published online: 22 September 2013 © Springer Science+Business Media New York 2013 A preliminary version of this work without all proofs and simulations has been presented at the 9th Latin American Theoretical Informatics Symposium (LATIN) 2010. This work is partly supported by the National Science Foundation (NSF grant CCF-0830704) and by the German Research Foundation (DFG project SCHE 1592/1-1 and SFB 901: On-the-Fly Computing) D. Gall · R. Jacob · H. Täubig Department of Computer Science, Institut für Informatik, Technische Universität München, Boltzmannstr. 3, 85748 Garching, Germany
PY - 2014/7
Y1 - 2014/7
N2 - 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 where nodes forward, insert, and delete links to neighboring nodes, and that converge quickly to such a desirable topology, independently of the initial network configuration. This article 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. In order to study the main structure and properties of our model, we propose two variants of a most simple local linearization algorithm. For each of these variants, we present analyses of the worst-case and best-case parallel time complexities, as well as the performance under a greedy selection of the actions to be executed. It turns out that the analysis is non-trivial despite the simple setting, and to complement our formal insights we report on our experiments which indicate that the runtimes may be better in the average case.
AB - 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 where nodes forward, insert, and delete links to neighboring nodes, and that converge quickly to such a desirable topology, independently of the initial network configuration. This article 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. In order to study the main structure and properties of our model, we propose two variants of a most simple local linearization algorithm. For each of these variants, we present analyses of the worst-case and best-case parallel time complexities, as well as the performance under a greedy selection of the actions to be executed. It turns out that the analysis is non-trivial despite the simple setting, and to complement our formal insights we report on our experiments which indicate that the runtimes may be better in the average case.
KW - Distributed algorithms
KW - Distributed systems
KW - Overlay networks
KW - Peer-to-peer systems
KW - Performance
KW - Self-stabilization
UR - http://www.scopus.com/inward/record.url?scp=84901826595&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84901826595&partnerID=8YFLogxK
U2 - 10.1007/s00224-013-9504-x
DO - 10.1007/s00224-013-9504-x
M3 - Article
AN - SCOPUS:84901826595
SN - 1432-4350
VL - 55
SP - 110
EP - 135
JO - Theory of Computing Systems
JF - Theory of Computing Systems
IS - 1
ER -