Service composition based on state dependent services is a challenge if it done in a decentralized way, that is without a centralized coordinating partner knowing all involved parties. In particular, the challenge is the combination of services to a composite service, such that every party involved considers its view of the composite service to be acceptable. In the paper a protocol is proposed which incrementally derives proposals for composite services. These proposals are then evaluated by the involved parties locally and a consensus on the local decision on accepting or rejecting the proposed composite service is derived.