Algorithms for the Certified Write-All Problem

DOI10.1137/S0097539794319126MaRDI QIDQ4376186zbMATH OpenFDO

Authors Richard J. Anderson, Heather Woll

Publication date 10 February 1998

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

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

zbMATH Keywords

adversary modelsasynchronous computationcertified write-all problemsynchronization primitives

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

Recommendations

• On the Complexity of Certified Write-All Algorithms
• A work-optimal deterministic algorithm for the asynchronous certified write-all problem
• A Work-Optimal Deterministic Algorithm for the Certified Write-All Problem with a Nontrivial Number of Asynchronous Processors
• A method for creating near-optimal instances of a certified write-all algorithm (extended abstract)
• Cooperative asynchronous update of shared memory

Cited in

(14)

• The Do-All problem with Byzantine processor failures
• Online parallel scheduling of non-uniform tasks: trading failures for energy
• Efficient gossip and robust distributed computation
• Performing work with asynchronous processors: Message-delay-sensitive bounds
• A work-optimal deterministic algorithm for the asynchronous certified write-all problem
• Oblivious Collaboration
• Efficient Algorithms for Alternating Pushdown Systems with an Application to the Computation of Certificate Chains
• Solving the at-most-once problem with nearly optimal effectiveness
• On the Complexity of Certified Write-All Algorithms
• Hundreds of impossibility results for distributed computing
• The complexity of synchronous iterative do-all with crashes
• A Work-Optimal Deterministic Algorithm for the Certified Write-All Problem with a Nontrivial Number of Asynchronous Processors
• Emulating shared-memory do-all algorithms in asynchronous message-passing systems
• A tight analysis and near-optimal instances of the algorithm of Anderson and Woll

This page was built for publication: Algorithms for the Certified Write-All Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4376186)