A Generic Cost Model for Concurrent and Data-parallel Meta-computing

AbstractThe CCS (Calculus of Communicating System) process algebra is a well-known formal model of synchronization and communication, useful for the analysis of safety and liveness in protocols or distributed programs, and in more recent works their security properties. BSP (Bulk-synchronous parallelism) is an algorithm- and programming model of data-parallel computation. It is useful for the design, analysis and programming of scalable parallel algorithms.Many current evolutions require the integration of distributed- and parallel programming: grid systems for sharing resources across the Internet, secure and reliable global access to parallel computer systems, geographic distribution of confidential data on randomly accessible systems, etc. Such software services must provide guarantees of safety, liveness, and security together with scalable and reliable performance. Formal models are therefore needed to combine parallel performance and concurrent behavior. With this goal in mind, we propose here an integration of BSP with CCS semantics, generalize its cost (performance) model and sketch its application to scheduling problems in meta-computing