Bulk synchronous parallel

The bulk synchronous parallel (BSP) abstract computer is a bridging model for designing parallel algorithms. It is similar to the parallel random access machine (PRAM) model, but unlike PRAM, BSP does not take communication and synchronization for granted. In fact, quantifying the requisite synchronization and communication is an important part of analyzing a BSP algorithm. The BSP model was developed by Leslie Valiant of Harvard University during the 1980s. The definitive article was published in 1990. Between 1990 and 1992, Leslie Valiant and Bill McColl of Oxford University worked on ideas for a distributed memory BSP programming model, in Princeton and at Harvard. Between 1992 and 1997, McColl led a large research team at Oxford that developed various BSP programming libraries, languages and tools, and also numerous massively parallel BSP algorithms, including many early examples of high-performance communication-avoiding parallel algorithms and recursive "immortal" parallel algorithms that achieve the best possible performance and optimal parametric tradeoffs. With interest and momentum growing, McColl then led a group from Oxford, Harvard, Florida, Princeton, Bell Labs, Columbia and Utrecht that developed and published the BSPlib Standard for BSP programming in 1996. Valiant developed an extension to the BSP model in the 2000s, leading to the publication of the Multi-BSP model in 2011. In 2017, McColl developed a major new extension of the BSP model that provides fault tolerance and tail tolerance for large-scale parallel computations in AI, Analytics and high-performance computing (HPC). See also A BSP computer consists of the following: Components capable of processing and/or local memory transactions (i.e., processors), A network that routes messages between pairs of such components, and A hardware facility that allows for the synchronization of all or a subset of components. This is commonly interpreted as a set of processors that may follow different threads of computation, with each processor equipped with fast local memory and interconnected by a communication network.