On the time complexity of broadcast communication schemes (Preliminary Version)

ABSTRACT

In this paper, we investigate the power of such broadcast in solving a paradigmatic problem in distributed computing. Imagine a network in which each node machine Ni (1-&-le;i-&-le;n) keeps a Boolean value vi in local memory. The vi 's determine a set S-&-equil;{i: vi-&-equil;1}. The non-emptiness problem on n nodes is to find some i in S, or else find that S is empty. In practice, a problem of this type arises in two ways: 1. Consensus testing: Has any node voted -&-ldquo;no-&-rdquo;, where vi-&-equil;1 means node i votes -&-ldquo;no-&-rdquo;, and vi-&-equil;O means node i votes -&-ldquo;yes-&-rdquo;? 2. Establishing a distinguished node: S specifies a set of candidates, and solving non-emptiness selects one. For example, the nodes may be bidding for a Job or a resource. In section 2, we introduce an idealistic broadcast communication scheme which abstracts certain features of the CSMA technology.

REFERENCES

• 1: Agrawala, A. K., Bryant, R. M., and Agre, J., Analysis of an Ethernet-like protocol, Proceedings Computer Networking Symposium of the IEEE Computer Society and National Bureau of Standards (December 1977), 104-111.
• 2: Almes, G.T. and Lazowska, E.D., The Behavior of Ethernet-like Computer Communication Networks, Technical Report 79-05-01, University of Washington, 1979.
• 3: Carpenter, R., Sokol, J., Rosenthal, R., A Microprocessor-based Local Network Node, Proceedings CompCon Fall 78, IEEE Computer Society (1978), 104-109.
• 4: Donnelley, J.E., and Yeh, J.W., Interaction Between Protocol Levels in a Prioritized CSMA Broadcast Network, Proceedings Third Berkeley Workshop, Lawrence Radiation Laboratory (1978).
• 5: Gerhardstein, L.H., Schroeder, J.O., and Boland, L.A., The Pacific Northwest Laboratory Minicomputer Network, Proceedings Third Berkeley Workshop on Distributed Data Management and Computer Networks, Lawrence Radiation Laboratory (1978).
• 6: Digital-Intel-Xerox, The Ethernet Data Link Layer and Physical Layer Specifications Version 1.0, A collaborative effort of the three corporations., September, 1980.
• 7: Lam, S.S., A Carrier Sense Multiple Access Protocol for Local Networks, Computer Networks 4 (1980), 21-32.
• 8: Robert M. Metcalfe , David R. Boggs, Ethernet: distributed packet switching for local computer networks, Communications of the ACM, v.19 n.7, p.395-404, July 1976 [doi>10.1145/360248.360253]
• 9: Moura, A. and Field, J., Collision-Control Algorithms in Carrier-Sense Multiple-Access (Collision-Detection) Networks, Computer Communications 4, 1 (February 1981), 10-18.
• 10: Sherman, R.H., Gable, M.G., and McClure G., Concepts, Strategies for Local Data Network Architectures, Data Communications 7, 7 (July 1978), 39-49.
• 11: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988