Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs Jacob, Riko Ritscher, Stephan Scheideler, Christian Schmid, Stefan ddc:040 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 Elsevier 2012 info:eu-repo/semantics/article doc-type:article text http://purl.org/coar/resource_type/c_6501 https://ris.uni-paderborn.de/record/570 Jacob R, Ritscher S, Scheideler C, Schmid S. Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs. <i>Theoretical Computer Science</i>. 2012:137-148. doi:<a href="https://doi.org/10.1016/j.tcs.2012.07.029">10.1016/j.tcs.2012.07.029</a> info:eu-repo/semantics/altIdentifier/doi/10.1016/j.tcs.2012.07.029 info:eu-repo/semantics/closedAccess