TY - CONF
AB - We present a self-stabilizing algorithm for overlay networks that, for an arbitrary metric given by a distance oracle, constructs the graph representing that metric. The graph representing a metric is the unique minimal undirected graph such that for any pair of nodes the length of a shortest path between the nodes corresponds to the distance between the nodes according to the metric. The algorithm works under both an asynchronous and a synchronous daemon. In the synchronous case, the algorithm stablizes in time O(n) and it is almost silent in that after stabilization a node sends and receives a constant number of messages per round.
AU - Gmyr, Robert
AU - LefĂ¨vre, Jonas
AU - Scheideler, Christian
ID - 155
T2 - Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
TI - Self-stabilizing Metric Graphs
ER -