Probabilistic solitude verification on a ring

Publisher Website
Google Scholar
Abstract
Matching upper and lower bounds for the bit complexity of a problem on asynchro- nous unidirectional rings are established, assum- ing that algorithms must reach a correct conclu- sion with probability 1-e, for some e > 0. Pro- cessors can have identities, but the identities are not necessarily distinct. The problem is that of a distinguished processor verifying that it is the only distinguished processor. The complexity depends on the processors' knowledge of the size a of the ring. When no upper bound is known, only nondistributive termination is possible, and O(nlog(1/e)) bits are necessary and sufficient. When only an upper bound N is known, distri- butive termination is possible, but the complex- ity of achieving distributive termination is

This publication has 0 references indexed in Scilit: