A Distributed Algorithm for Constructing a Generalization of de Bruijn Graphs

View/ Open
Date
2006-04-06Author
Swamy, Nikhil
Frangiadakis, Nikolaos
Bitsakos, Konstantinos
Metadata
Show full item recordAbstract
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.