Interval routing schemes allow broadcasting with linear message-complexity

Pierre Fraigniaud*, Cyril Gavoille, Bernard Mans

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

Abstract

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) while 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 can also help to perform distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows to broadcast with an O(n) message-complexity, 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 therefore the O(m + n) previous known bound.

Original languageEnglish
Title of host publicationProceedings of the Annual ACM Symposium on Principles of Distributed Computing
Place of PublicationNew York
PublisherACM
Pages11-20
Number of pages10
ISBN (Print)1581131836
DOIs
Publication statusPublished - 2000
Externally publishedYes
Event19th Annual ACM Symposium on Principles of Distributed Computing - Portland, OR, USA
Duration: 16 Jul 200019 Jul 2000

Other

Other19th Annual ACM Symposium on Principles of Distributed Computing
CityPortland, OR, USA
Period16/07/0019/07/00

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

Cite this