BPEL only supports a strictly centralized and coordinated execution of Web service compositions, but this solution is clearly not the best option in many concrete cases. The conceptually monolithic BPEL process should be executed in a distributed setting, where each peer is only responsible for a fraction of the whole process and for the coordination with the other fragments. These considerations lead us to propose a formal approach to support the distributed execution of BPEL processes. The partitioning is customizable and easily intertwines with the adoption of special-purpose middleware infrastructures. In particular, the paper shows how we pair the distributed execution with a tuple-based infrastructure, to support distributed execution in mobile contexts, and with a publish and subscribe middleware, to support dynamically changing scenarios. Copyright © (2007) by Knowledge Systems Institute (KSI).