Clock-related operations are one of the many sources of replica non-determinism and of replica inconsistency in fault-tolerant distributed systems. In passive replication, if the primary server crashes, the next clock value returned by the new primary server might have actually rolled back in time, which can lead to undesirable consequences for the replicated application. The same problem can happen for active replication where the result of the first replica to respond is taken as the next clock value.

In this paper, we describe the design and implementation of a consistent time service for fault-tolerant distributed systems. The consistent time service introduces a group clock that is consistent across the replicas and that ensures the determinism of the replicas with respect to clock-related operations. The group clock is monotonically increasing, is transparent to the application and is fault-tolerant. The consistent time service guarantees the consistency of the group clock even when faults occur, when new replicas are added into the group and when failed replicas recover.