Service networks of arbitrary network topology are known from stream and complex event processing systems. As service networks are often required to be highly available, this raises the question, whether replication mechanism known from traditional database or client/server systems can be transferred to generic service networks. State machine replication is well-known to provide both, availability and strong consistency, even in the presence of node failures. When nodes crash and recover, it is, however, not clear, whether, and in what way, these consistency guarantees can be transferred to the service network as a whole. To solve this, we propose a protocol that enables the interconnection of replicated services to a consistent, semi-dynamic service network. Our protocol is built upon a persistent enumeration system for messages produced by the state machine and upon a replicated log, which provides “intelligent” guarantees on the entries that are committed. A formal proof verifies the correctness of the protocol for normal operation as well as during recovery. We finally conduct a quantitative evaluation to give an impression of the possible performance of the protocol.