Designing Checkers for Programs that Run in Parallel

TitleDesigning Checkers for Programs that Run in Parallel
Publication TypeTechnical Report
Year of Publication1990
AuthorsRubinfeld, R.
Other Numbers604

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 Notes

ICSI Technical Report TR-90-040

Abbreviated Authors

R. Rubinfeld

ICSI Publication Type

Technical Report