Software-based active replication is expensive in terms of performance overhead. Multithreading can help improve 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. 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 and the Loose Synchronization Algorithm (LSA) proposed by the authors in an earlier paper. The results show that PDS outperforms nonpreemptive deterministic schedulers. Compared with LSA, PDS has lower throughput; 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.

Original languageEnglish (US)
Number of pages10
StatePublished - 2003
Event2003 International Conference on Dependable Systems and Networks - San Francisco, CA, United States
Duration: Jun 22 2003Jun 25 2003


Other2003 International Conference on Dependable Systems and Networks
Country/TerritoryUnited States
CitySan Francisco, CA

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'A Preemptive Deterministic Scheduling Algorithm for Multithreaded Replicas'. Together they form a unique fingerprint.

Cite this