Randomized Consensus in Expected $O(N\log ^2 N)$ Operations Per Processor

DOI10.1137/S0097539792240881zbMath0861.68039OpenAlexW2147823853MaRDI QIDQ4714556

Orli Waarts, James Aspnes

Publication date: 11 May 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539792240881

zbMATH Keywords

randomized algorithmshared memoryasynchronous computationshared-coin protocol

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42) Large deviations (60F10) Distributed algorithms (68W15)

Related Items (11)

A modular approach to shared-memory consensus, with applications to the probabilistic-write model ⋮ Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication ⋮ Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler ⋮ On the importance of having an identity or, is consensus really universal? ⋮ Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study ⋮ Hundreds of impossibility results for distributed computing ⋮ Randomized protocols for asynchronous consensus ⋮ Combining shared-coin algorithms ⋮ Randomized Consensus in Expected O(n 2) Total Work Using Single-Writer Registers ⋮ Communication-efficient randomized consensus ⋮ A Tight Space Bound for Consensus

This page was built for publication: Randomized Consensus in Expected $O(N\log ^2 N)$ Operations Per Processor