Designing checkers for programs that run in parallel

DOI10.1007/BF01961540zbMath0843.68042OpenAlexW2026123763MaRDI QIDQ1911462

Ronitt Rubinfeld

Publication date: 13 August 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01961540

zbMATH Keywords

program correctnessP-complete problemsprogram result checking

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Related Items

Locality and checkability in wait-free computing, Pipelined algorithms to detect cheating in long-term grid computations, Problem identification using program checking, Locality and Checkability in Wait-Free Computing, Self-testing/correcting with applications to numerical problems

Cites Work

• Unbounded fan-in circuits and associative functions
• Matching is as easy as matrix inversion
• A Las Vegas RNC algorithm for maximum matching
• Constructing a perfect matching is in random NC
• A random NC algorithm for depth first search
• The complexity of parallel search
• Parallel computational geometry
• Self-testing/correcting with applications to numerical problems
• Efficient checkers for number-theoretic computations
• Parity, circuits, and the polynomial-time hierarchy
• Constant Depth Reducibility
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• A New Parallel Algorithm for the Maximal Independent Set Problem
• Parallel Transitive Closure and Point Location in Planar Structures
• Optimal bounds for decision problems on the CRCW PRAM
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item