Technical reports:
Two Lower Bounds In Asynchronous Distributed Computation
Pavol Duris; Zvi Galil
Downloads:
- Title:
- Two Lower Bounds In Asynchronous Distributed Computation
- Author(s):
-
Duris, Pavol
Galil, Zvi - Date:
- 1987
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:11874
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-304-87
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- Abstract:
- We introduce new techniques for deriving lower bounds on the message complexity in asynchronous distributed computation. These techniques combine the choice of specific patterns of communication delays and crossing sequence arguments with consideration of the speed of propagation of messages, together with careful counting of messages in different parts of the network. They enable us to prove the following results, settling two open problems: An Ω(n log* n) lower bound for the number of messages sent by an asynchronous algorithm for computing any nonconstant function on a bidirectional ring of n anonymous processors. An Ω(n log n) lower bound for the average number of messages sent by any maximum finding algorithm on a ring of n processors, in case n is known.
- Subject(s):
- Computer science
- Item views:
- 58