A Distributed Algorithm for Constructing a Generalization of de Bruijn Graphs

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.