A Distributed Algorithm for Constructing a Generalization of de Bruijn Graphs
A Distributed Algorithm for Constructing a Generalization of de Bruijn Graphs
Files
Publication or External Link
Date
2006-04-06
Authors
Swamy, Nikhil
Frangiadakis, Nikolaos
Bitsakos, Konstantinos
Advisor
Citation
DRUM DOI
Abstract
De Bruijn graphs possess many characteristics that
make them a suitable choice for the topology of an overlay
network. These include constant degree at each node,
logarithmic diameter and a highly-regular topology that
permits nodes to make strong assumptions about the global
structure of the network.
We propose a distributed protocol that constructs an
approximation of a de Bruijn graph in the presence of an
arbitrary number of nodes. We show that the degree of each
node is constant and that the diameter of the network is no
worse than 2logN, where N is the number of nodes. The
cost of the join and the departure procedures are O(logN)
in the worst case. To the best of our knowledge, this is the
first distributed protocol that provides such deterministic
guarantees.