Fast randomized consensus using shared memory
From MaRDI portal
Publication:3485848
DOI10.1016/0196-6774(90)90021-6zbMATH Open0705.68016OpenAlexW1999787317MaRDI QIDQ3485848FDOQ3485848
Authors: James Aspnes, Maurice 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
Recommendations
- Fast and simple distributed consensus
- Communication-efficient randomized consensus
- Space-efficient asynchronous consensus without shared memory initialization
- Fast deterministic consensus in a noisy environment
- Faster randomized consensus with an oblivious adversary
- Faster randomized consensus with an oblivious adversary
- Randomized protocols for asynchronous consensus
Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10)
Cited In (51)
- \(L^\ast\)-based learning of Markov decision processes (extended version)
- A complexity-based classification for multiprocessor synchronization
- Fast deterministic consensus in a noisy environment
- Minimal counterexamples for linear-time probabilistic verification
- Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study
- Fast deterministic consensus in a noisy environment
- The complexity of synchronizing Markov decision processes
- Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers
- Randomized consensus in expected \(O(n \log n)\) individual work
- Optimal schedulers vs optimal bases: an approach for efficient exact solving of Markov decision processes
- Approximate shared-memory counting despite a strong adversary
- On atomic registers and randomized consensus in m\&m systems
- Atomic snapshots using lattice agreement
- The strong at-most-once problem
- Scenario-based verification of uncertain MDPs
- Farkas certificates and minimal witnesses for probabilistic reachability constraints
- Efficient execution of nondeterministic parallel programs on asynchronous systems
- On the importance of having an identity or, is consensus really universal?
- Coupling and self-stabilization
- Title not available (Why is that?)
- An inductive technique for parameterised model checking of degenerative distributed randomised protocols
- Task-structured probabilistic I/O automata
- Sequential convex programming for the efficient verification of parametric MDPs
- Deniable Functional Encryption
- Compositional probabilistic verification through multi-objective model checking
- Naming symmetric processes using shared variables
- On the use of MTBDDs for performability analysis and verification of stochastic systems.
- A partial equivalence between shared-memory and message-passing in an asynchronous fail-stop distributed environment
- Randomized consensus in expected \(O(n ^{2})\) total work using single-writer registers
- A tight space bound for consensus
- A modular approach to shared-memory consensus, with applications to the probabilistic-write model
- Randomized consensus with regular registers
- Does a Program Yield the Right Distribution?
- The space complexity of unbounded timestamps
- Communication-efficient randomized consensus
- Faster randomized consensus with an oblivious adversary
- Randomized registers and iterative algorithms
- Long-lived counters with polylogarithmic amortized step complexity
- Error bounds for stochastic shortest path problems
- Randomized two-process wait-free test-and-set
- Deciding probabilistic bisimilarity distance one for probabilistic automata
- The correctness proof of Ben-Or's randomized consensus algorithm
- Space-efficient asynchronous consensus without shared memory initialization
- Parameter-Independent Strategies for pMDPs via POMDPs
- Combining shared-coin algorithms
- Randomized protocols for asynchronous consensus
- Faster randomized consensus with an oblivious adversary
- The epigenetic consensus problem
- Probabilistic black-box reachability checking (extended version)
- Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler
- A modular approach to shared-memory consensus, with applications to the probabilistic-write model
This page was built for publication: Fast randomized consensus using shared memory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3485848)
