10.1007/978-3-319-49259-9_20
Gmyr, Robert
Robert
Gmyr
Lefèvre, Jonas
Jonas
Lefèvre
Scheideler, Christian
Christian
Scheideler
Self-stabilizing Metric Graphs
2016
2017-10-17T12:41:22Z
2019-01-03T13:11:54Z
conference
https://ris.uni-paderborn.de/record/155
https://ris.uni-paderborn.de/record/155.json
389136 bytes
application/pdf
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.