2017/08/22 by Michael Feldmann, Feldmann, Michael, Christian Scheideler +1
Computer Science · #Advanced Data Storage Technologies #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Opportunistic and Delay-Tolerant Networks #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1708.06542
openalex publication_date 2017/08/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 = √[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(√[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(√[d]n), when the number of nodes in the system increases by factor 2d. The number of messages that are periodically sent out by nodes is constant.