A self-stabilizing general de Bruijn graph

DOI10.1007/978-3-319-69084-1_17MaRDI QIDQ5045447zbMATH OpenOpenAlexFDO

Authors Michael Feldmann, Christian Scheideler

Publication date 4 November 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.06542

zbMATH Keywords

distributed systemsde Bruijn graphtopological self-stabilization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Network protocols (68M12)

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 $mathcalO(sqrt[d]n)$, which is asymptotically optimal for a fixed diameter $d$. The protocol keeps the expected amount of edge redirections per node in $mathcalO(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.

Recommendations

• D2B: A de Bruijn based content-addressable network
• \(\mathrm{SKIP}^{+}\), a self-stabilizing skip graph
• Self-stabilizing overlays for high-dimensional monotonic searchability
• Self-stabilizing deterministic network decomposition
• Self-stabilization with \(r\)-operators

Cited in

(1)

• D2B: A de Bruijn based content-addressable network

This page was built for publication: A self-stabilizing general de Bruijn graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5045447)