Fast randomized consensus using shared memory
From MaRDI portal
Publication:3485848
DOI10.1016/0196-6774(90)90021-6zbMath0705.68016OpenAlexW1999787317MaRDI QIDQ3485848
James Aspnes, Maurice P. Herlihy
Publication date: 1990
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://figshare.com/articles/journal_contribution/Fast_randomized_consensus_using_shared_memory/6605600
Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10)
Related Items
On atomic registers and randomized consensus in m\&m systems, Scenario-Based Verification of Uncertain MDPs, Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints, The space complexity of unbounded timestamps, Error bounds for stochastic shortest path problems, Efficient execution of nondeterministic parallel programs on asynchronous systems, Compositional probabilistic verification through multi-objective model checking, Minimal counterexamples for linear-time probabilistic verification, A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment, Parameter-Independent Strategies for pMDPs via POMDPs, A modular approach to shared-memory consensus, with applications to the probabilistic-write model, The correctness proof of Ben-Or's randomized consensus algorithm, On the use of MTBDDs for performability analysis and verification of stochastic systems., Long-lived counters with polylogarithmic amortized step complexity, Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler, On the importance of having an identity or, is consensus really universal?, Coupling and self-stabilization, Naming symmetric processes using shared variables, Atomic snapshots using lattice agreement, Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study, Randomized two-process wait-free test-and-set, Randomized protocols for asynchronous consensus, Optimal schedulers vs optimal bases: an approach for efficient exact solving of Markov decision processes, Combining shared-coin algorithms, Sequential Convex Programming for the Efficient Verification of Parametric MDPs, The complexity of synchronizing Markov decision processes, \(L^\ast\)-based learning of Markov decision processes (extended version), Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers, Task-structured probabilistic I/O automata, A complexity-based classification for multiprocessor synchronization, Probabilistic black-box reachability checking (extended version), On the optimal space complexity of consensus for anonymous processes, Deniable Functional Encryption, An Inductive Technique for Parameterised Model Checking of Degenerative Distributed Randomised Protocols, Deciding probabilistic bisimilarity distance one for probabilistic automata, Randomized consensus with regular registers, Randomized Consensus in Expected O(n 2) Total Work Using Single-Writer Registers, Communication-efficient randomized consensus, A Tight Space Bound for Consensus, The epigenetic consensus problem
