Top

Theory of Computing Systems

Published in:

17-11-2017

Self-Stabilizing Metric Graphs

Authors: Robert Gmyr, Jonas Lefèvre, Christian Scheideler

Published in: Theory of Computing Systems | Issue 2/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present a self-stabilizing algorithm for overlay networks that for an arbitrary given metric specified via 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 dæmon. In the synchronous case, the algorithm stabilizes in time O(n), and after stabilization each node sends and receives only a constant number of messages per round.

previous article Editor’s Note: Special Issue on Stabilization, Safety, and Security of Distributed Systems

next article Synchronous Gathering without Multiplicity Detection: a Certified Algorithm

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Aggarwal, S., Kutten, S.: Time optimal self-stabilizing spanning tree algorithms. In: Foundations of Software Technology and Theoretical Computer Science, pp 400–410. Springer (1993)

Berns, A., Ghosh, S., Pemmaraju, S.V.: Building self-stabilizing overlay networks with the transitive closure framework. In: Proceedings of the 13Th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS’11, pp 62–76. Springer, Berlin (2011)

Clouser, T., Nesterenko, M., Scheideler, C.: Tiara: a self-stabilizing deterministic skip list and skip graph. Theor. Comput. Sci. 428, 18–35 (2012)MathSciNetCrossRefMATH

Cramer, C., Fuhrmann, T., Fakultät Für Informatik: Self-stabilizing ring networks on connected graphs. Technical report (2005)

Gärtner, F.C.: A survey of self-stabilizing spanning-tree construction algorithms. Technical report (2003)

Gmyr, R., Lefèvre, J., Scheideler, C.: Self-stabilizing metric graphs. In: Stabilization, Safety, and Security of Distributed Systems - 18Th International Symposium, SSS 2016, Lyon, France, November 7–10, 2016, Proceedings, pp 248–262 (2016)

Jacob, R., Richa, A., Scheideler, C., Schmid, S., Täubig, H.: A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. In: Proceedings of the 28Th ACM Symposium on Principles of Distributed Computing, pp 131–140. ACM (2009)

Keil, J.M., Gutwin, C.A.: The delaunay triangulation closely approximates the complete euclidean graph. In: Algorithms and Data Structures, pp 47–56. Springer (1989)

Keil, J.M., Gutwin, C.A.: Classes of graphs which approximate the complete euclidean graph. Discrete Comput. Geom. 7(1), 13–28 (1992)MathSciNetCrossRefMATH

10.

Kniesburges, S., Koutsopoulos, A., Scheideler, C.: Re-chord: a self-stabilizing chord overlay network. Theory Comput. Syst. 55(3), 591–612 (2014)MathSciNetCrossRefMATH

11.

Onus, M., Richa, A.W., Scheideler, C.: Linearization: locally self-stabilizing sorting in graphs. In: ALENEX (2007)

12.

Richa, A., Scheideler, C., Stevens, P.: Self-stabilizing De Bruijn networks. In: Stabilization, Safety, and Security of Distributed Systems, pp 416–430. Springer (2011)

13.

Shaker, A., Reeves, D.S.: Self-stabilizing structured ring topology P2P systems. In: Fifth IEEE International Conference on Peer-To-Peer Computing, 2005. P2P 2005, pp 39–46 (2005)

Title: Self-Stabilizing Metric Graphs
Authors: Robert Gmyr
Jonas Lefèvre
Christian Scheideler
Publication date: 17-11-2017
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 2/2019
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-017-9823-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2019

Making Local Algorithms Wait-Free: the Case of Ring Coloring

Synchronous Gathering without Multiplicity Detection: a Certified Algorithm

Editor’s Note: Special Issue on Stabilization, Safety, and Security of Distributed Systems

On-Line Path Computation and Function Placement in SDNs

Packet Efficient Implementation of the Omega Failure Detector

Wait-free Solvability of Colorless Tasks in Anonymous Shared-memory Model

Premium Partner