The BPEL language is currently the primary candidate for standardising Web Services orchestration. BPEL specifications are meant to be run by BPEL orchestration engines, which are therefore crucial components of today’s business-to-business infrastructures, carrying the burden of dynamically composing existing services.

In this paper, we present the design of a BPEL orchestration engine based on a multi-agent system: while the basic BPEL activities are autonomously executed by agents, workflow aspects are realised by the mediation of ReSpecT tuple centres, a coordination model extending Linda with the ability of declaratively programming the tuple space behaviour.

Our architecture separates the interaction, correlation, and workflow concerns into clearly identified tiers. In particular, we identify the workflow tier as the one encapsulating the core and most critical behaviour of the engine: due to its intrinsic complexity, we tackle its design formally. We introduce a core algebraic language of BPEL dealing with its workflow-related aspects, and provide it with a semantics based on a mapping into a net specification, modelling the dependencies between the activities to be executed by the engine. This mapping plays the role of a formal design, since it directly leads to an implementation of the workflow tier in the orchestration engine.