Designing Checkers for Programs that Run in Parallel
| Title | Designing Checkers for Programs that Run in Parallel |
| Publication Type | Technical Report |
| Year of Publication | 1990 |
| Authors | Rubinfeld, R. |
| Other Numbers | 604 |
| Abstract | 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. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-90-040.pdf |
| Bibliographic Notes | ICSI Technical Report TR-90-040 |
| Abbreviated Authors | R. Rubinfeld |
| ICSI Publication Type | Technical Report |