Publication Details
Title: Designing Checkers for Programs that Run in Parallel
Author: R. Rubinfeld
Group: ICSI Technical Reports
Date: August 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-040.pdf
Overview:
We extend the theory of program result checking to parallel programs, and find general techniques for designing such result checkers. We find result checkers for many basic problems in parallel computation. We show that there are P-complete problems (evaluating straight-line programs, linear programming) that have very fast (even constant depth) parallel result checkers. Sorting, multiplication, parity, majority and the all pairs shortest path problem all have constant depth result checkers. In addition, the sequential versions of the parallel result checkers given for integer sorting and the all pairs shortest path problems are the first deterministic sequential result checkers for those problems.
Bibliographic Information:
ICSI Technical Report TR-90-040
Bibliographic Reference:
R. Rubinfeld. Designing Checkers for Programs that Run in Parallel. ICSI Technical Report TR-90-040, August 1990
Author: R. Rubinfeld
Group: ICSI Technical Reports
Date: August 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-040.pdf
Overview:
We extend the theory of program result checking to parallel programs, and find general techniques for designing such result checkers. We find result checkers for many basic problems in parallel computation. We show that there are P-complete problems (evaluating straight-line programs, linear programming) that have very fast (even constant depth) parallel result checkers. Sorting, multiplication, parity, majority and the all pairs shortest path problem all have constant depth result checkers. In addition, the sequential versions of the parallel result checkers given for integer sorting and the all pairs shortest path problems are the first deterministic sequential result checkers for those problems.
Bibliographic Information:
ICSI Technical Report TR-90-040
Bibliographic Reference:
R. Rubinfeld. Designing Checkers for Programs that Run in Parallel. ICSI Technical Report TR-90-040, August 1990