direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Stefan Schmid's Publications

Stefan Schmid's website

Brief Announcement: On the Time Complexity of Distributed Topological Self-Stabilization
Citation key GJRSST-OTCDTS-09
Author Gall, Dominik and Jacob, Riko and Richa, Andréa and Scheideler, Christian and Schmid, Stefan and Täubig, Hanjo
Title of Book Stabilization, Safety, and Security of Distributed Systems – Proceedings of 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
Pages 781–782
Year 2009
ISBN 978-3-642-05117-3
ISSN 0302-9743
DOI http://dx.doi.org/10.1007/978-3-642-05118-0_58
Location Lyon, France
Address Berlin / Heidelberg, Germany
Volume 5873
Month November
Note Brief Announcement
Publisher Springer
Series Lecture Notes in Computer Science (LNCS)
Abstract This brief announcement proposes a new model to measure the distributed time complexity of topological self-stabilization. In the field of topological self-stabilization, nodes–-e.g., machines in a p2p network–-seek to establish a certain network structure in a robust manner (see, e.g., [2] for a distributed algorithm for skip graphs). While several complexity models have been proposed and analyzed over the last years, these models are often inappropriate to adequately model parallel efficiency: either they are overly pessimistic in the sense that they can force the algorithm to work serially, or they are too optimistic in the sense that contention issues are neglected. We hope that our approach will inspire researchers in the community to analyze other problems from this perspective. For a complete technical report about our model, related literature and algorithms, the reader is referred to [1].
Link to publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions