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) 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.