Self-stabilizing Metric Graphs

R. Gmyr, J. Lefèvre, C. Scheideler, in:, Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2016, pp. 248–262.

Download
Restricted 155-SSS16-GLS.pdf 389.14 KB
Conference Paper
Author
; ;
Abstract
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.
Publishing Year
Journal Title
Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
Page
248--262
LibreCat-ID

Cite this

Gmyr R, Lefèvre J, Scheideler C. Self-stabilizing Metric Graphs. In: Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). LNCS.; 2016:248-262. doi:10.1007/978-3-319-49259-9_20.
Gmyr, R., Lefèvre, J., & Scheideler, C. (2016). Self-stabilizing Metric Graphs. In Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) (pp. 248–262). http://doi.org/10.1007/978-3-319-49259-9_20
@inbook{Gmyr_Lefèvre_Scheideler_2016, series={LNCS}, title={Self-stabilizing Metric Graphs}, DOI={10.1007/978-3-319-49259-9_20}, booktitle={Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}, author={Gmyr, Robert and Lefèvre, Jonas and Scheideler, Christian}, year={2016}, pages={248–262}, collection={LNCS}}
Gmyr, Robert, Jonas Lefèvre, and Christian Scheideler. “Self-Stabilizing Metric Graphs.” In Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 248–62. LNCS, 2016. doi:10.1007/978-3-319-49259-9_20.
R. Gmyr, J. Lefèvre, and C. Scheideler, “Self-stabilizing Metric Graphs,” in Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2016, pp. 248–262.
Gmyr, Robert, Jonas Lefèvre, and Christian Scheideler. “Self-Stabilizing Metric Graphs.” Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). N.p., 2016. 248–262. Web. LNCS.
Main File(s)
File Name
155-SSS16-GLS.pdf 389.14 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T12:51:24Z

frontdoor.tabs.publications.cited_by
This publication cites the following data publications:

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar