We present a deterministic obstruction-free implementation of leader election from O(root n) atomic O(log n)-bit registers in the standard asynchronous shared memory system with n processes. We provide also a techniqu...
详细信息
ISBN:
(纸本)9783642415272;9783642415265
We present a deterministic obstruction-free implementation of leader election from O(root n) atomic O(log n)-bit registers in the standard asynchronous shared memory system with n processes. We provide also a technique to transform any deterministic obstruction-free algorithm, in which any process can finish if it runs for b steps without interference, into a randomized wait-free algorithm for the oblivious adversary, in which the expected step complexity is polynomial in n and b. This transformation allows us to combine our obstruction-free algorithm with the leader election algorithm by Giakkoupis and Woelfel [21], to obtain a fast randomized leader election (and thus test-and-set) implementation from O(v n) O(log n)-bit registers, that has expected step complexity O(log* n) against the oblivious adversary. Our algorithm provides the first sub-linear space upper bound for obstruction-free leader election. A lower bound of Omega(log n) has been known since 1989 [29]. Our research is also motivated by the long-standing open problem whether there is an obstruction-free consensus algorithm which uses fewer than n registers.
暂无评论