A preemptive deterministic scheduling algorithm for multithreaded replicas

Software-based active replication is expensive in terms of performance overhead. Multithreading can help im-prove performance; however, thread scheduling is a source of nondeterminism in replica behavior. This paper presents a Preemptive Deterministic Scheduling (PDS) algorithm for ensuring deterministic replica behavior while preserving concurrency. Threads are synchronized only on updates to the shared state. A replica execution is broken into a sequence of rounds and in a round each thread can acquire up to two mutexes. If a thread cannot acquire a mutex it requests, then it checks if all other threads are suspended. If so, the thread fires a new round; otherwise, the thread is suspended. When a new round fires, all threads ’ mutex requests are known; thus, it is possible to form a deterministic scheduling of mutex acquisitions in the round. No inter-replica communication is required. The algorithm is formally specified, and the proposed formalism is used to prove its correctness. Failure behavior and performance of a PDS algorithm’s implementation are evaluated in a triplicated system and compared with two existing solutions: nonpreemptive deterministic schedulers (e.g., Eternal and Transactional Drago) and the Loose Synchronization Algorithm (LSA) proposed by the authors in an earlier paper. The results show that PDS outperforms nonpreemptive deterministic schedulers. Comparing with LSA, PDS has lower through-put; however, it provides additional benefits in terms of system dependability and, hence, can be considered as a trade-off between performance and dependability. These characteristics are investigated with fault injection.