Towards Higher-Dimensional Topological Self-Stabilization: A Distributed Algorithm for Delaunay Graphs
METADATA ONLY
Loading...
Author / Producer
Date
2012-10-26
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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 identifiers, 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(n 3 ) 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 affect 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 higher-dimensional linearization problems.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
457
Pages / Article No.
137 - 148
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Distributed algorithms; Topology control; Social networks
Organisational unit
03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)