Interval Routing for Distributed Problems

The general question ``how much a labeling can help in the solution of some distributed problems'' was posed by [FMS98a], and then further studied by [FMS97,FMS98b] in the framework of Sense of Direction.

Recently, David Peleg asked the question in [SRS97]: ``In many contexts and many areas, once a good representation is constructed, it is often useful for more than one application. Yet in the particular case of Interval Routing, IRS representations seem to be used only for routing. Given that we have invested all this time and efforts in constructing them, it should be nice if we could use them (once constructed) to solve other problems more efficiently, in addition to routing.''

Originally the investigation of Interval Routing came from distributed computing in asynchronous networks. [vLT87] proved that minimum spanning tree, leader-election (when the node-labeling is not restricted to $\{1,\ldots,n\}$), and other related distributed problems can be solved in a ring labeled with a 1-IRS by exchanging O(n) messages only, and O(|E| + n) messages for arbitrary graphs, whereas in the general case $O(n\log{n})$ messages for the ring, and $O(\vert E\vert+n\log{n})$ messages for arbitrary graph are required [GHS83].

More precisely, David Peleg posed in [SRS97] the question: ``is it possible to broadcast by exchanging a total of O(n) messages for any graph supporting a shortest path 1-IRS? (adding $O(\log{n})$ extra bits to the message)''

The general problem is still open but there are some partial results in the case of all-shortest paths k-IRS (recall that an all-shortest path IRS is a multipath IRS that encodes all the shortest paths from every source node cf. Paragraph 4.3). In particular [EPTZ97] shows that:

It implies that the algorithm which consists in sending first the message to destination 1, then, after reception, to destination 2, and so on until the node labeled n, turns out a total of at most 3n messages. It is interesting to remark that if G has a full-adaptive 1-IRS of stretch factor s, then by a simulation of the previous algorithm, G has a O(sn) messages broadcast algorithm.

Only partial results are known for (single) shortest path 1-IRS. In particular we have the property:

It follows that nodes 1 and 2, and by symmetry the nodes n-1 and n, are neighbors. Because the grid with its usual shortest path 1-SLIRS labeling, the bound of Theorem 65 is tight.

Other broadcast algorithms have been proposed in [dlTNP98] leading also to a linear time solution: The SSR-CAST algorithm. In the following, R is an IRS, s the source node, and M is the message to broadcast.

Algorithm [dlTNP98]: $\mbox{\sc ssr-cast}(R,s,M)$ itemize

Initialization: s sends the message M and the set I(s,u) to each of its neighbors u. Forwarding step for $v \neq s$: Upon receipt of the message M and a set I from some neighbor u, the node v identifies each neighbor $w \neq u$ such that $I \cap I(v,w) \neq \emptyset$, and then forwards to w the message M along with the set $I \cap I(v,w)$.

itemize

It turns out an optimal solution, i.e., n-1 messages and a time D, for graphs that admit an all-shortest paths 1-IRS. Note that the SSR-CAST algorithm must send per edge up to $4\log{n}$ extra bits added to the message to represent the set $I \cap I(v,w)$. Indeed, in [dlTNP98], it is proved that $I \cap I(v,w)$ is composed of at most two intervals. The same performances hold for graphs that admit a shortest path 1-IRS such that from each node the routing paths induced by the 1-IRS form a tree. Such IRS are denoted IRS $^{\mbox{\small tree}}$. Note that the same algorithm can be used to compute a minimum spanning tree of the graph.

Open question 14    
- Is 1-IRS = 1-IRS $^{\mbox{\small tree}}$ ?
- Same question for k-IRS and its variants, k > 1?

To conclude, we think that Interval Routing is certainly a sufficiently simple model for the theoretical study of the structural and implicit information of distributed networks. It is quite easy to predict that this model will be extended and/or exploited in many fashions. This is what seems to be the thesis of the paper of [dlTNP98].

I would like to thank the anonymous reviewers for their helpful comments.