Nowadays the concepts and infrastructures of Cloud Computing are becoming a standard for several applications. Scalability is not only a buzzword anymore, but is being used effectively. However, despite the economical advantages of virtualization and scalability, some factors as latency, bandwidth and processor sharing can be a problem for doing Parallel Computing on the Cloud.

We will provide an overview on how to tackle these problems using the BSP (Bulk Synchronous Parallel) model. We will introduce the main advantages of the CGM (Coarse Grained Multicomputer) model, where the main goal is to minimize the number of communication rounds, which can have an important impact on BSP algorithms performance. We will also briefly present our experience on using BSP in an opportunistic grid computing environment. Then we will show several recent models for distributed computing initiatives based on BSP. Finally we will present some preliminary experiments presenting the performance of BSP algorithms on Clouds.