Self-stabilizing Metric Graphs
Gmyr, Robert
Lefèvre, Jonas
Scheideler, Christian
ddc:040
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.
2016
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://ris.uni-paderborn.de/record/155
Gmyr R, Lefèvre J, Scheideler C. Self-stabilizing Metric Graphs. In: <i>Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>. LNCS. ; 2016:248--262. doi:<a href="https://doi.org/10.1007/978-3-319-49259-9_20">10.1007/978-3-319-49259-9_20</a>
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-49259-9_20
info:eu-repo/semantics/closedAccess