Interval routing schemes allow broadcasting with linear message-complexity

Pierre Fraigniaud*, Cyril Gavoille, Bernard Mans

*Corresponding author for this work

Research output: Contribution to journalConference paperpeer-review

6 Citations (Scopus)


The purpose of compact routing is to provide a labeling of the nodes of a network and a way to encode the routing tables, so that routing can be performed efficiently (e.g., on shortest paths) whilst keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing may also assist in the performance of distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows broadcasting with a message-complexity of O(n), where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving the previous known bound of O(m + n). A general consequence of our result is that a shortest path interval routing scheme contains ample structural information to avoid developing ad-hoc or network-specific solutions for basic problems that distributed systems must handle repeatedly.

Original languageEnglish
Pages (from-to)217-229
Number of pages13
JournalDistributed Computing
Issue number4
Publication statusPublished - Dec 2001
Event19th Annual ACM Symposium on Principles of Distributed Computing - Portland, OR, USA
Duration: 16 Jul 200019 Jul 2000


Dive into the research topics of 'Interval routing schemes allow broadcasting with linear message-complexity'. Together they form a unique fingerprint.

Cite this