AD-A283 255 NTISRAMIE~uuhuuuEDTIC TABUnannouncedSECTION 2.2 Justification... Fault-Tolerance and Efficiency in By................. Massively Parallel Algorithms Dist; ibution I Availability Codes

We present an overview of massively parallel deterministic algorithms which combine high fault-tolerance and efficiency. This desirable combination (called robustness here) is nontrivial, since increasing efficiency implies removing re-dundancy whereas increasing fault-tolerance requires adding redundancy to computations. We study a spectrum of algorithmic models for which signif-icant robustness is achievable, from static fault, synchronous computation to dynamic fault, asynchronous computation. In addition to fail-stop processor models, we examine and deal with arbitrarily initialized memory and restricted memory access concurrency. We survey the deterministic upper bounds for the 4 ýV basic Write-All primitive, the lower bounds on its efficiency, and we identify A A, some of the key open questions. We also generalize the robust computing of 4 C\ functions to relations; this new approach can model approximate computations. We show how to compute approximate Write-All optimally. Finally, we syn- 4,. thesize the state-of-the-art in a complexity classification, which extends wit