A Self-Stabilizing General De Bruijn Graph

M. Feldmann, C. Scheideler, in:, Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Springer, Cham, 2017, pp. 250–264.

Download
No fulltext has been uploaded. References only!
Conference Paper | Published | English
Abstract
Searching for other participants is one of the most important operations in a distributed system.We are interested in topologies in which it is possible to route a packet in a fixed number of hops until it arrives at its destination.Given a constant $d$, this paper introduces a new self-stabilizing protocol for the $q$-ary $d$-dimensional de Bruijn graph ($q = \sqrt[d]{n}$) that is able to route any search request in at most $d$ hops w.h.p., while significantly lowering the node degree compared to the clique: We require nodes to have a degree of $\mathcal O(\sqrt[d]{n})$, which is asymptotically optimal for a fixed diameter $d$.The protocol keeps the expected amount of edge redirections per node in $\mathcal O(\sqrt[d]{n})$, when the number of nodes in the system increases by factor $2^d$.The number of messages that are periodically sent out by nodes is constant.
Publishing Year
Journal Title
Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)
Volume
10616
Page
250-264
LibreCat-ID

Cite this

Feldmann M, Scheideler C. A Self-Stabilizing General De Bruijn Graph. In: Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS).Vol 10616. Lecture Notes in Computer Science. Springer, Cham; 2017:250-264. doi:10.1007/978-3-319-69084-1_17.
Feldmann, M., & Scheideler, C. (2017). A Self-Stabilizing General De Bruijn Graph. In Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS) (Vol. 10616, pp. 250–264). Springer, Cham. http://doi.org/10.1007/978-3-319-69084-1_17
@inbook{Feldmann_Scheideler_2017, series={Lecture Notes in Computer Science}, title={A Self-Stabilizing General De Bruijn Graph}, volume={10616}, DOI={10.1007/978-3-319-69084-1_17}, booktitle={Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)}, publisher={Springer, Cham}, author={Feldmann, Michael and Scheideler, Christian}, year={2017}, pages={250–264}, collection={Lecture Notes in Computer Science}}
Feldmann, Michael, and Christian Scheideler. “A Self-Stabilizing General De Bruijn Graph.” In Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 10616:250–64. Lecture Notes in Computer Science. Springer, Cham, 2017. doi:10.1007/978-3-319-69084-1_17.
M. Feldmann and C. Scheideler, “A Self-Stabilizing General De Bruijn Graph,” in Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2017, vol. 10616, pp. 250–264.
Feldmann, Michael, and Christian Scheideler. “A Self-Stabilizing General De Bruijn Graph.” Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Vol. 10616. Springer, Cham, 2017. 250–264. Web. Lecture Notes in Computer Science.
frontdoor.tabs.publications.cited_by
This publication cites the following data publications:

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search