Fast randomized consensus using shared memory
From MaRDI portal
Publication:3485848
DOI10.1016/0196-6774(90)90021-6zbMath0705.68016MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68M10: Network design and communication in computer systems
Related Items
A Tight Space Bound for Consensus, Scenario-Based Verification of Uncertain MDPs, Farkas Certificates and Minimal Witnesses for Probabilistic Reachability Constraints, 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, On the optimal space complexity of consensus for anonymous processes, Parameter-Independent Strategies for pMDPs via POMDPs, The space complexity of unbounded timestamps, Compositional probabilistic verification through multi-objective model checking, Minimal counterexamples for linear-time probabilistic verification, Combining shared-coin algorithms, Efficient execution of nondeterministic parallel programs on asynchronous systems, On the use of MTBDDs for performability analysis and verification of stochastic systems., The complexity of synchronizing Markov decision processes, Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers, Task-structured probabilistic I/O automata, A modular approach to shared-memory consensus, with applications to the probabilistic-write model, The correctness proof of Ben-Or's randomized consensus algorithm, 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, \(L^\ast\)-based learning of Markov decision processes (extended version), A complexity-based classification for multiprocessor synchronization, Probabilistic black-box reachability checking (extended version), Randomized consensus with regular registers, Communication-efficient randomized consensus, The epigenetic consensus problem, On atomic registers and randomized consensus in m\&m systems, Deciding probabilistic bisimilarity distance one for probabilistic automata, Error bounds for stochastic shortest path problems, Optimal schedulers vs optimal bases: an approach for efficient exact solving of Markov decision processes, Long-lived counters with polylogarithmic amortized step complexity, Deniable Functional Encryption, An Inductive Technique for Parameterised Model Checking of Degenerative Distributed Randomised Protocols, Randomized Consensus in Expected O(n 2) Total Work Using Single-Writer Registers, Sequential Convex Programming for the Efficient Verification of Parametric MDPs, A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment