Timemessage tradeoffs for the weak unison problem 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 xe2x80x9cwakeupxe2x80x9d state) in the absence of a global startup signal. As measure of complexity of the protocols considered we use the xe2x80x9cbitsxe2x80x9d times xe2x80x9clagxe2x80x9d 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 tradeoffs in the complexity of such algorithms under several conditions on the behavior of the processors (oblivious, nonoblivious, balanced, etc) and provide tight upper and lower bounds on the time xc3x97 messages measure.

On the benefits of saturating information in consensus networks with noise Abstract   In a consensus network subject to nonzero mean noise, the system state may be driven away even when the disagreement exhibits a bounded response. This is unfavourable in applications since the nodes may not work properly and even be faulty outside their operating region. In this paper, we propose a new control algorithm to mitigate this issue by assigning each node a favourite interval that characterizes the nodes desired convergence region. The algorithm is implemented in a selftriggered fashion. If the nodes do not share a global clock, the network operates in a fully asynchronous mode. By this algorithm, we show that the state evolution is confined around the favourite interval and the node disagreement is bounded by a simple linear function of the noise magnitude, without requiring any priori information on the noise. We also show that if the nodes share some global information, then the algorithm can be adjusted to make the nodes evolve into the favourite interval, improve on the disagreement bound and achieve asymptotic consensus in the noiseless case.