TU Berlin

Internet Network ArchitecturesStefan Schmid's Publications

Page Content

to Navigation

Stefan Schmid's Publications

A Self-Stabilizing and Local Delaunay Graph Construction
Citation key JRSS-SLDGC-09
Author Jacob, Riko and Ritscher, Stephan and Scheideler, Christian and Schmid, Stefan
Title of Book Algorithms and Computations: Proceedings of 20th International Symposium on Algorithms and Computation (ISAAC)
Year 2009
ISBN 978-3-642-10630-9
ISSN 0302-9743
DOI http://dx.doi.org/10.1007/978-3-642-10631-6_78
Location Hawaii, USA
Address Berlin / Heidelberg, Germany
Volume 5878
Month December
Publisher Springer
Series Lecture Notes in Computer Science (LNCS)
Abstract This paper studies the construction of self-stabilizing topologies for distributed systems. While recent research has focused on chain topologies where nodes need to be linearized with respect to their identifiers, we go a step further and explore a natural 2-dimensional generalization. In particular, we present a local self-stabilizing algorithm that constructs a Delaunay graph from any initial connected topology and in a distributed manner. This algorithm terminates in time O(n_3) in the worst-case. We believe that such self-stabilizing Delaunay networks have interesting applications and give insights into the necessary geometric reasoning that is required for higher-dimensional linearization problems.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe