TITLE: Interval Routing Schemes Allow Broadcasting with Linear Message-Complexity
AUTHORS: Pierre Fraigniaud, Cyril Gavoille and Bernard Mans
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.