Abstract In many distributed systems robustness is a major concern since network nodes might fail spontaneously. Such failures can be a major problem when a workflow needs to be run on a set of unreliable and distributed nodes. Replication is a widely used architecture paradigm to increase system reliability. This thesis addresses robustness of workflow execution in distributed systems using replication. A workflow is a plan that describes how a number of tasks needs to be executed and is defined using a workflow definition language. A task is the description of a single operation contained within such a workflow. The first part of this thesis gives an overview over available workflow definition languages focusing mainly on declarative ones. Task types present in this languages are identified and their impact on replication is evaluated. A basic problem of workflow replication is that not all tasks within a workflow can be executed arbitrarily often. To solve this issue the execution of such tasks must be coordinated. The goal of this thesis is to propose and evaluate methods to coordinate the execution of such workflow replicas in a distributed environment. The proposed replica coordination algorithms are implemented as a peer to peer protocol and simulated using the peer to peer simulator PeerSim. A synthetic workflow generator is used to provide a large number of workflows for evaluation to test the performance, scalability and robustness under different conditions. The evaluation is concluded with the replication of a real workflow to judge the significance of the synthetic tests to the real world.