Interval Routing Schemes allow Broadcasting with Linear Message-Complexity
P. Fraigniaud, C. Gavoille and B. Mans
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
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.