On the Complexity of Certified Write-All Algorithms

DOI10.1006/JAGM.1994.1017MaRDI QIDQ4290913zbMATH OpenOpenAlexFDO

Authors Ramesh Subramonian, Chip Martel

Publication date 5 May 1994

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1994.1017

zbMATH Keywords

asynchronous PRAM algorithmscertified write-all problemparallel computationsynchronization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• A Work-Optimal Deterministic Algorithm for the Certified Write-All Problem with a Nontrivial Number of Asynchronous Processors
• A work-optimal deterministic algorithm for the asynchronous certified write-all problem
• Asynchronous PRAMs with memory latency
• Algorithms for the Certified Write-All Problem

Cited in

(13)

• Clock construction in fully asynchronous parallel systems and PRAM simulation
• The Do-All problem with Byzantine processor failures
• A work-optimal deterministic algorithm for the asynchronous certified write-all problem
• Algorithms for the Certified Write-All Problem
• Dealing with undependable workers in decentralized network supercomputing
• Writing-all deterministically and optimally using a nontrivial number of asynchronous processors
• An algorithm for the asynchronous \textit{Write-All} problem based on process collision
• 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
• A method for creating near-optimal instances of a certified write-all algorithm (extended abstract)
• Faster randomized repeated choice and DCAS
• A tight analysis and near-optimal instances of the algorithm of Anderson and Woll

This page was built for publication: On the Complexity of Certified Write-All Algorithms

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