Interval routing schemes allow broadcasting with linear message-complexity (extended abstract)

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.

References

1. 1.B. Awerbuch, I. Cidon, S. Kutten, Y. Mansour, and D. Peleg. Optimal broadcast with partial knowledge. SIAM Journal on Computing, 28(2):511-524, 1998.]]
2. 2.B. Awerbuch, O. Goldreich, D. Peleg, and R. Vainish. A tradeoff between information and communication in broadcast protocols. Journal of the A CM, 37(2):238-256, 1990.]]
3. 3.P. de la Torte, L. Naranayan, and D. Peleg. Thy neighbor's interval is greener: A proposal for exploiting interval routing schemes. In 5th International Colloquium on Structural information and Communication Complexity (SIROCCO '98), pages 214-228. Carleton Scientific, 1998.]]
4. 4.K. Diks, E. Kranakis, D. Krizanc, and A. Pelc. The impact of knowledge on broadcasting time in radio networks. In 7~h Annual European Symposium on Algorithms (ESA), volume 1643 of Lectures Notes in Computer Science, pages 41-52. Springer-Verlag, 1999.]]
5. 5.T. Eilam, D. Peleg, R. Tan, and S. Zaks. Broadcast in linear messages in IRS representing all shortest paths. Manuscript, 1997.]]
6. 6.M. Flammini, J. van Leeuwen, and A. Marchetti-Spaccamela. The complexity of interval routing on random graphs. In 20th International Symposium on Mathematical Foundations of Computer Sciences (MFCS), volume 969 of Lecture Notes in Computer Science, pages 37-49. Springer-Verlag, 1995.]]
7. 7.P. Flocchini, B. Mans, and N. Santoro. Sense of direction: Definitions, properties and classes. Networks, 32:165-180, 1998.]]
8. 8.P. Flocchini, B. Mans, and N. Santoro. On the impact of Sense of Direction on Message Complexity. Information Processing Letters, 63(1):23-31, 1997.]]
9. 9.P. Flocchini, B. Mans, and N. Santoro. Sense of direction in distributed computing. In 12th International Symposium on Distributed Computing (DISC), volume 1499 of Lecture Notes in Computer Science, pages 1-15. Springer-Verlag, 1998.]]
10. 10.P. Fraigniaud and C. Gavoille. Interval routing schemes. Algorithmica, 21:155-182, 1998.]]
11. 11.P. Fraigniaud, C. Gavoille, and B. Mans. Interval Routing Schemes allow Broadcasting with Linear Message-Complexity. Technical Report LRI-1241, Laboratoire de Recherche en Informatique, Univ. Paxis-Sud, 91405 Orsay, France. Jan. 2000.]]
12. 12.G. Frederickson. Searching among intervals and compact routing tables. In 20th International Colloquium on Automata, Languages and Programming (ICALP), volume 700 of Lecture Notes in Computer Science, pages 28-39. Springer-Verlag, 1993.]]
13. 13.G. Frederickson and R. Janardan. Separator-based strategies for efficient message routing. In 27eh Symposium on Foundations of Computer Science (FOCS), pages 428-437, 1986.]]
14. 14.G. Frederickson and R. Janardan. Designing networks with compact routing tables. Algorithmica, 3:171-190, 1988.]]
15. 15.G. Gallager, P. Humblet, and P. Spira. A distributed algorithm for minimal spanning tree. A CM Trans. on Programming Languages Systems, 5(1):66-77, 1983.]]
16. 16.C. Gavoille. A survey on interval routing. Theoretical Computer Science. To appear in Vol.245.]]
17. 17.C. Gavoille and E. Gu4vremont. Worst case bounds for shortest path interval routing. Journal o.f Algorithms, 27:1-25, 1998.]]
18. 18.C. Gavoille and N. Hanusse. Compact routing tables for graphs of bounded genus. In 26~h International Colloquium on Automata, Languages and Programming (ICALP), volume 1644 of Lecture Notes in Computer Science, pages 351-360. Springer-Verlag, 1999.]]
19. 19.C. Gavoille and D. Peleg. The compactness of interval routing. SIAM Journal of Discrete Mathematics, 12(4):459-473, 1999.]]
20. 20.C. Gavoille and S. P4renn~s. Memory requirement for routing in distributed networks. In 15~h Annual A CM Symposium on Principles of Distributed Computing (PODC), pages 125-133, 1996.]]
21. 21.E. Kranakis and D. Krizanc. Lower bounds for compact routing. In 13~ Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1046 of Lecture Notes in Computer Science, pages 529-540. Springer-Verlag, 1996.]]
22. 22.E. Kranakis, D. Krizanc, and S. Ravi. On multi-label linear interval routing schemes. In 19th International Workshop on Graph Theoretic Concepts in Computer Science (WG}, volume 790 of Lecture Notes in Computer Science, pages 338-349. Springer-Verlag, 1993.]]
23. 23.E. Korach, S. Kutten and S. Moran. A modular technique for the design of efficient distributed leader finding algorithms, A CM Trans. on Programming Languages Systems, 12(1):84-101, 1990.]]
24. 24.D. Peleg and E. Upfal. Efficient message passing using succinct routing tables. In 20th Annual A CM Symposium on Theory of Computing (STOC), pages 43-52, 1988.]]
25. 25.D. Peleg and E. Upfal. A trade-off between space and efficiency for routing tables. Journal of the A CM, 36(3):510-530, 1989.]]
26. 26.N. Santoro and lZt. Khatib. Labelling and implicit routing in networks. The Computer Journal, 28(1):5-8, 1985.]]
27. 27.J. van Leeuwen and R. Tan. Interval routing. The Computer Journal, 30(4):298-307, 1987.]]

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

• Networks

  • Network architectures

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Communications management

    • Software system structures

      • Distributed systems organizing principles