Abstract
Overlay networks, where nodes communicate with neighbors over logical links consisting of zero or more physical links, have become an important part of modern networking. From data centers to IoT devices, overlay networks are used to organize a diverse set of processes for efficient operations like searching and routing. Many of these overlay networks operate in fragile environments where faults that perturb the logical network topology are commonplace. Self-stabilizing overlay networks offer one approach for managing these faults, promising to build or restore a particular topology from any weakly-connected initial configuration.
Designing efficient self-stabilizing algorithms for many topologies, however, is not an easy task. For non-trivial topologies that have desirable properties like low diameter and robust routing in the face of node or link failures, self-stabilizing algorithms to date have had at least linear running time or space requirements. In this work, we address this issue by presenting an algorithm for building a Chord network that has polylogarithmic time and space complexity. Furthermore, we discuss how the technique we use for building this Chord network can be generalized into a “design pattern” for other desirable overlay network topologies.
An early version of this work appeared as a Brief Announcement in SPAA 2021.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Berns, A.: Avatar: a time- and space-efficient self-stabilizing overlay network. In: Pelc, A., Schwarzmann, A.A. (eds.) SSS 2015. LNCS, vol. 9212, pp. 233–247. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21741-3_16
Berns, A.: Network scaffolding for efficient stabilization of the chord overlay network. In: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2021, pp. 417–419. Association for Computing Machinery, New York (2021). https://doi.org/10.1145/3409964.3461827
Berns, A.: Network scaffolding for efficient stabilization of the chord overlay network (2021). https://arxiv.org/abs/2109.14126
Berns, A., Ghosh, S., Pemmaraju, S.V.: Building self-stabilizing overlay networks with the transitive closure framework. In: Défago, X., Petit, F., Villain, V. (eds.) SSS 2011. LNCS, vol. 6976, pp. 62–76. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24550-3_7
Delaët, S., Devismes, S., Nesterenko, M., Tixeuil, S.: Snap-stabilization in message-passing systems. J. Parallel Distrib. Comput. 70(12), 1220–1230 (2010)
Gilbert, S., Pandurangan, G., Robinson, P., Trehan, A.: Dconstructor: Efficient and robust network construction with polylogarithmic overhead. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC 2020, pp. 438–447. Association for Computing Machinery, New York (2020). https://doi.org/10.1145/3382734.3405716
Götte, T., Hinnenthal, K., Scheideler, C., Werthmann, J.: Time-optimal construction of overlay networks. In: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC 2021, pp. 457–468. Association for Computing Machinery, New York (2021). https://doi.org/10.1145/3465084.3467932
Hayes, T., Rustagi, N., Saia, J., Trehan, A.: The forgiving tree: a self-healing distributed data structure. In: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, PODC 2008, pp. 203–212. Association for Computing Machinery, New York (2008). https://doi.org/10.1145/1400751.1400779
Jacob, R., Richa, A., Scheideler, C., Schmid, S., Täubig, H.: A distributed polylogarithmic time algorithm for self-stabilizing skip graphs. In: PODC ’09: Proceedings of the 28th ACM symposium on Principles of distributed computing, pp. 131–140. ACM, New York (2009). http://doi.acm.org/10.1145/1582716.1582741
Kniesburges, S., Koutsopoulos, A., Scheideler, C.: Re-chord: a self-stabilizing chord overlay network. In: Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures, SPAA 2011, pp. 235–244. ACM, New York (2011). https://doi.org/10.1145/1989493.1989527. http://doi.acm.org/10.1145/1989493.1989527
Onus, M., Richa, A.W., Scheideler, C.: Linearization: locally self-stabilizing sorting in graphs. In: ALENEX. SIAM (2007)
Pandurangan, G., Robinson, P., Trehan, A.: Dex: self-healing expanders. Distrib. Comput. 29(3), 163–185 (2016). https://doi.org/10.1007/s00446-015-0258-3
Saroiu, S., Gummadi, K.P., Gribble, S.D.: Measuring and analyzing the characteristics of Napster and Gnutella hosts. Multimedia Syst. 9(2), 170–184 (2003). https://doi.org/10.1007/s00530-003-0088-1
Trehan, A.: Self-healing using virtual structures. CoRR abs/1202.2466 (2012). http://arxiv.org/abs/1202.2466
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Berns, A. (2021). Network Scaffolding for Efficient Stabilization of the Chord Overlay Network. In: Johnen, C., Schiller, E.M., Schmid, S. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2021. Lecture Notes in Computer Science(), vol 13046. Springer, Cham. https://doi.org/10.1007/978-3-030-91081-5_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-91081-5_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-91080-8
Online ISBN: 978-3-030-91081-5
eBook Packages: Computer ScienceComputer Science (R0)