Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs

R. Jacob, S. Ritscher, C. Scheideler, S. Schmid, Theoretical Computer Science (2012) 137.

Download
Restricted 570-Delaunay-Journal.pdf 250.05 KB
Journal Article
Author
; ; ;
Abstract
This article 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 identiers, we explore a natural and relevant 2-dimensional generalization. In particular, we present a local self-stabilizing algorithm DStab which is based on the concept of \local Delaunay graphs" and which forwards temporary edges in greedy fashion reminiscent of compass routing. DStab constructs a Delaunay graph from any initial connected topology and in a distributed manner in time O(n3) in the worst-case; if the initial network contains the Delaunay graph, the convergence time is only O(n) rounds. DStab also ensures that individual node joins and leaves aect a small part of the network only. Such self-stabilizing Delaunay networks have interesting applications and our construction gives insights into the necessary geometric reasoning that is required for higherdimensional linearization problems.Keywords: Distributed Algorithms, Topology Control, Social Networks
Publishing Year
Journal Title
Theoretical Computer Science
Page
137-148
LibreCat-ID

Cite this

Jacob R, Ritscher S, Scheideler C, Schmid S. Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs. Theoretical Computer Science. 2012:137-148. doi:10.1016/j.tcs.2012.07.029.
Jacob, R., Ritscher, S., Scheideler, C., & Schmid, S. (2012). Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs. Theoretical Computer Science, 137–148. http://doi.org/10.1016/j.tcs.2012.07.029
@article{Jacob_Ritscher_Scheideler_Schmid_2012, title={Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs}, DOI={10.1016/j.tcs.2012.07.029}, journal={Theoretical Computer Science}, publisher={Elsevier}, author={Jacob, Riko and Ritscher, Stephan and Scheideler, Christian and Schmid, Stefan}, year={2012}, pages={137–148}}
Jacob, Riko, Stephan Ritscher, Christian Scheideler, and Stefan Schmid. “Towards Higher-Dimensional Topological Self-Stabilization: A Distributed Algorithm for Delaunay Graphs.” Theoretical Computer Science, 2012, 137–48. doi:10.1016/j.tcs.2012.07.029.
R. Jacob, S. Ritscher, C. Scheideler, and S. Schmid, “Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs,” Theoretical Computer Science, pp. 137–148, 2012.
Jacob, Riko et al. “Towards Higher-Dimensional Topological Self-Stabilization: A Distributed Algorithm for Delaunay Graphs.” Theoretical Computer Science (2012): 137–148. Web.
Main File(s)
File Name
570-Delaunay-Journal.pdf 250.05 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-15T10:16:20Z

frontdoor.tabs.publications.cited_by
This publication cites the following data publications:

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar