PDF

Le graphe de de Bruijn, ou le Vilain Petit Canard deviendra-t-il Cygne ? (Pierre Fraigniaud - LRI)

At the end of the 80's, Jean-Claude Bermond was quite active supporting the de Bruijn topology as an alternative to hypercubes and meshes for the design of interconnection networks dedicated to tightly coupled parallel computers. Although he demonstrated an impressive amount of nice properties of the de Bruijn graph, the wiring of this topology was too complex for an easy practical use. As a consequence, excepted a few cases (e.g., the Viterbi decoder of the Galileo spacial mission to Jupiter), the de Bruijn graph has not been used for the design of parallel computers. Fifteen years later, the use of Distributed Hash Tables (DHT) for publish and search of resources in Peer-to-Peer (P2P) systems put back the de Bruijn on stage. Indeed, overlay networks are virtual in the sense that they do not correspond to real wires but simply to the exchanges of IP addresses, and TCP connections. Therefore, the major obstacle to the use of the de Bruijn graph does not stand anymore. This talk will survey this short story of the de Bruijn graph since the late 80's, from parallel computers to peer-to-peer networks.