A trade-off between information and communication in broadcast protocols

ABSTRACT

This paper concerns the message complexity of broadcast in arbitrary point-to-point communication networks. Broadcast is a task initiated by a single processor that wishes to convey a message to all processors in the network. The widely accepted model of communication networks, in which each processor initially knows the identity of its neighbors but does not know the entire network topology, is assumed. Although it seems obvious that the number of messages required for broadcast in this model equals the number of links, no proof of this basic fact has been given before. It is shown that the message complexity of broadcast depends on the exact complexity measure. If messages of unbounded length are counted at unit cost, then broadcast requires &THgr;(↿V↾) messages, where V is the set of processors in the network. It is proved that, if one counts messages of bounded length, then broadcast requires &THgr;(↿E↾) messages, where E is the set of edges in the network. Assuming an intermediate model in which each vertex knows the topology of the network in radius &rgr; ≥ 1 from itself, matching upper and lower bounds of &THgr;(min{↿E↾, ↿V↾1+&THgr;(l)/&rgr;}) is proved on the number of messages of bounded length required for broadcast. Both the upper and lower bounds hold for both synchronous and asynchronous network models. The same results hold for the construction of spanning trees, and various other global tasks.

REFERENCES

• 1: Karl Abrahamson , Andrew Adler , Lisa Higham , David Kirkpatrick, Probabilistic solitude verification on a ring, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.161-173, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10604]
• 2: Yehuda Afek , Eli Gafni, Time and message bounds for election in synchronous and asynchronous complete networks, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.186-195, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323613]
• 3: Chagit Attiya , Marc Snir , Manfred Warmuth, Computing on an anonymous ring, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.196-203, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323614]
• 4: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 5: AWERBUCH, B., GOLDREICH, O., AND VAINISH, R. O1"1 the message complexity of broadcast: A basic lower bound. Tech. Memo MIT/LCS/TM-325. MIT, Cambridge, Mass., April 1987.
• 6: Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
• 7: BURNS, J.E. A formal model for message passing systems. Tech. Rep. TR-9 l. Indiana University, Bloomington, Ind., 1980.
• 8: Yogen K. Dalal , Robert M. Metcalfe, Reverse path forwarding of broadcast packets, Communications of the ACM, v.21 n.12, p.1040-1048, Dec. 1978 [doi>10.1145/359657.359665]
• 9: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• 10: Greg N. Frederickson, Tradeoffs for selection in distributed networks (Preliminary Version), Proceedings of the second annual ACM symposium on Principles of distributed computing, p.154-160, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806718]
• 11: Greg N. Frederickson , Nancy A. Lynch, The impact of synchronous communication on the problem of electing a leader in a ring, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.493-503, December 1984 [doi>10.1145/800057.808719]
• 12: R. G. Gallager , P. A. Humblet , P. M. Spira, A Distributed Algorithm for Minimum-Weight Spanning Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.1, p.66-77, Jan. 1983 [doi>10.1145/357195.357200]
• 13: Oded Goldreich , Liuba Shrira, The effects of link failures on computations in asynchronous rings, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.174-185, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10605]
• 14: GRAHAM, R. L., ROTHSCHILD, B. L., AND SPENCER, J. H. Ramsey Theory. Wiley, New York, I980.
• 15: E. Korach , S. Moran , S. Zaks, Tight lower and upper bounds for some distributed algorithms for a complete network of processors, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.199-207, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806747]
• 16: E. Korach , S. Moran , S. Zaks, The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.277-286, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323622]
• 17: LYNCH, N. A., AND FISCHER, M.J. On describing the behavior and implementation of distributed systems. Theoret. Comput. Sci. 13 ( 1981), 17-43.
• 18: Y Mansour , S Zaks, On the bit complexity of distributed computations in a ring with a leader, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.151-160, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10603]
• 19: Shlomo Moran , Manfred Warmuth, Gap theorems for distributed computing, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.131-150, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10602]
• 20: Jan K. Pachl , E. Korach , D. Rotem, A technique for proving lower bounds for distributed maximum-finding algorithms (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.378-382, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802213]
• 21: PELEG, D., AND SCH.~EFER, A. Graph spanners. J. Graph Theory 13 (1989), 99-116.
• 22: Rüdiger Reischuk , Meinolf Koshors, Lower Bounds for Synchronous Networks and the Advantage of Local Information, Proceedings of the 2nd International Workshop on Distributed Algorithms, p.374-387, July 08-10, 1987

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Measurement, Theory