Towards Higher-Dimensional Topological Self-Stabilization: A Distributed Algorithm for Delaunay Graphs

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.