A DETERMINISTIC SCHEDULER

As it has been told before, the main difficulty in active replication is to keep replica determinism to prevent any divergence in their behavior that would yield inconsistencies [18]. The traditional approach to active replication has been to implement single-threaded servers so their determinism can be easily guaranteed just by ensuring that the order of external events is the same in all the replicas. However, the use of sequential servers is not always feasible or advisable. In this section we present a new approach that allows multithreaded replicated servers in a transactional environment. In our approach a replicated server is a group of replicated processes and clients multicast their requests to the server group. The multicast used is reliable and totally ordered. We assume that there are no network partitions and processes are fail-stop [17]. The client-server interaction is based on multithreaded rendezvous described in the previous section and so, each server thread can impose easily a protocol of calls to its client transaction. In this framework, it is not admissible a sequential server as the whole interaction with client transactions would be executed sequentially. In our proposal the execution of requests from different client transactions can be interleaved due to the multithreaded nature of the server. Replica consistency is guaranteed by both:

• A reliable fifo totally ordered multicast. As the only external events are client requests (as well as some internal messages), it is enough to use this kind of multicast to ensure that all the replicas see the same set of external events in the same order. It must be noticed that reliability is an important feature as it prevents the situation where some replicas receive a client request while others do not.
• A deterministic scheduler. This component is the one that allows multithreading (concurrency) within the server and it ensures that the scheduling is the same in all the replicas. Of course server thread code must be deterministic.