Today, peer-to-peer services can comprise a large and growing number of services, e.g. search services or services dealing with heterogeneous schemas in the context of Digital Libraries. For a given task, the system has to determine suitable services and their processing order (“execution plan”). As peers can join or leave the network spontaneously, static execution plans are not suf- ficient. This paper proposes a logic-based approach for dynamically computing execution plans: Services are described in the DAML-S language. These descriptions are mapped onto probabilistic Datalog. Finally, logical rules are applied on the service description facts for determining matching services and deriving an optimum execution plan.