AbstractA set of anonymous processors is interconnected forming a complete synchronous network with sense of direction. Weak unison is the problem where all processors want to enter the same state (in our case ``wakeup'' state) in the absence of a global start-up signal. As measure of complexity of the protocols considered we use the ``bits'' times ``lag'' measure, i.e. the total number of (wakeup) messages transmitted throughout the execution of the protocol times the number of steps which are sufficient in order for all the processors to wakeup. We study trade-offs in the complexity of such algorithms under several conditions on the behavior of the processors (oblivious, non-oblivious, balanced, etc) and provide tight upper and lower bounds on the time times #messages measure.
Categories and Subject Descriptors: C.2.1 [Computer-Communication Networks]: Network Architecture and Design
Additional Key Words and Phrases: anonymous network, balanced, chordal rings, t-step protocol, non-oblivious, oblivious, time-message complexity, unbalanced, unison, wakeup protocol, weak unison
Selected references
- Hagit Attiya, Marc Snir, and Manfred K. Warmuth. Computing on an anonymous ring. Journal of the ACM, 35(4):845-875, October 1988.
- Shimon Even and Sergio Rajsbaum. The use of a synchronizer yields maximum computation rate in distributed networks (extended abstract). In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 95-105, Baltimore, Maryland, 14-16 May 1990.
- Michael J. Fischer, Shlomo Moran, Steven Rudich, and Gadi Taubenfeld. The wakeup problem (extended abstract). In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 106-116, Baltimore, Maryland, 14-16 May 1990.
- Mohamed G. Gouda and Ted Herman. Stabilizing unison. Information Processing Letters, 35(4):171-175, 7 August 1990.