ABSTRACT
One important objective of models of computation [1] is to provide a framework for the design and the analysis of algorithms that can be executed efficiently on physical machines. In view of this objective, this chapter reviews the Decomposable Bulk Synchronous Parallel (D-BSP) model, introduced in Reference 2 as an extension to BSP [3], and further investigated in References 4-7. In the present section, we discuss a number of issues to be confronted when defining models for parallel computation and briefly outline some historical developments that have led to the formulation of D-BSP. The goal is simply to put D-BSP in perspective, with no attempt to provide a complete survey of the vast variety of models proposed in the literature.
