conference paper published Michael Feldmann author 23538 Christian Scheideler author 20792 79 department SFB 901 project SFB 901 - Subprojekt A1 project SFB 901 - Project Area A project 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. https://ris.uni-paderborn.de/download/125/5214/Feldmann-Scheideler2017_Chapter_ASelf-stabilizingGeneralDeBrui.pdf application/pdf Springer, Cham2017 eng 978-3-319-69083-4 1708.0654210.1007/978-3-319-69084-1_17 10616250-264 M. Feldmann and C. Scheideler, “A Self-Stabilizing General De Bruijn Graph,” in <i>Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, 2017, vol. 10616, pp. 250–264. Feldmann, Michael, and Christian Scheideler. “A Self-Stabilizing General De Bruijn Graph.” In <i>Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, 10616:250–64. Lecture Notes in Computer Science. Springer, Cham, 2017. <a href="https://doi.org/10.1007/978-3-319-69084-1_17">https://doi.org/10.1007/978-3-319-69084-1_17</a>. Feldmann M, Scheideler C. A Self-Stabilizing General De Bruijn Graph. In: <i>Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>. Vol 10616. Lecture Notes in Computer Science. Springer, Cham; 2017:250-264. doi:<a href="https://doi.org/10.1007/978-3-319-69084-1_17">10.1007/978-3-319-69084-1_17</a> Feldmann, M., &#38; Scheideler, C. (2017). A Self-Stabilizing General De Bruijn Graph. In <i>Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i> (Vol. 10616, pp. 250–264). Springer, Cham. <a href="https://doi.org/10.1007/978-3-319-69084-1_17">https://doi.org/10.1007/978-3-319-69084-1_17</a> @inproceedings{Feldmann_Scheideler_2017, series={Lecture Notes in Computer Science}, title={A Self-Stabilizing General De Bruijn Graph}, volume={10616}, DOI={<a href="https://doi.org/10.1007/978-3-319-69084-1_17">10.1007/978-3-319-69084-1_17</a>}, 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.” <i>Proceedings of the 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)</i>, vol. 10616, Springer, Cham, 2017, pp. 250–64, doi:<a href="https://doi.org/10.1007/978-3-319-69084-1_17">10.1007/978-3-319-69084-1_17</a>. 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. 1252017-10-17T12:41:16Z2022-01-06T06:51:19Z