On the Complexity of Certified Write-All Algorithms

DOI10.1006/JAGM.1994.1017zbMATH Open0804.68065OpenAlexW2022179515MaRDI QIDQ4290913FDOQ4290913

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

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

zbMATH Keywords

parallel computationsynchronizationcertified write-all problemasynchronous PRAM algorithms

Mathematics Subject Classification ID

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

Cited In (11)

• A tight analysis and near-optimal instances of the algorithm of Anderson and Woll
• Hundreds of impossibility results for distributed computing
• The Do-All problem with Byzantine processor failures
• The complexity of synchronous iterative do-all with crashes
• Clock construction in fully asynchronous parallel systems and PRAM simulation
• A method for creating near-optimal instances of a certified write-all algorithm (extended abstract)
• An algorithm for the asynchronous \textit{Write-All} problem based on process collision
• Dealing with undependable workers in decentralized network supercomputing
• Algorithms for the Certified Write-All Problem
• Writing-all deterministically and optimally using a nontrivial number of asynchronous processors
• A Work-Optimal Deterministic Algorithm for the Certified Write-All Problem with a Nontrivial Number of Asynchronous Processors

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)