interval routing schemes allow broadcasting with linear message-complexity (extended 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.
interval interval routing routing scheme broadcasting message abstraction compact routing label network encode tables shortest path paper help distributed computing graph space memorialized complexity