Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420960 | Discrete Applied Mathematics | 2007 | 6 Pages |
Abstract
We consider the fundamental problem of waking up n processors sharing a multiple access channel. We assume the weakest model of synchronization, the locally synchronous model, in which no global clock is available: processors have local clocks ticking at the same rate, but each clock starts counting the rounds in the round in which the correspondent processor wakes up. Moreover, the number n of processors is not known to the processors. We propose a new deterministic algorithm for this problem in time O(n3log3n)O(n3log3n), which improves on the currently best upper bound of O(n4log5n)O(n4log5n).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gianluca De Marco, Marco Pellegrini, Giovanni Sburlati,