Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs
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. (C) 2012 Elsevier B.V. All rights reserved.
distributed algorithms topology control social networks