TR-222: Time-Message Trade-Offs for the Weak Unison Problem
Ӱԭ University
Technical Report TR-222
March 1993
Time-Message Trade-Offs for the Weak Unison Problem
Amos Israeli, Evangelos Kranakis, Danny Krizanc, Nicola Santoro
Abstract
A 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 x #messages measure.