Abstract

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)
Pages149-158
Number of pages10
DOIs
StatePublished - Dec 1 2003
Event2003 International Conference on Dependable Systems and Networks - San Francisco, CA, United States
Duration: Jun 22 2003Jun 25 2003

Other

Other2003 International Conference on Dependable Systems and Networks
CountryUnited States
CitySan Francisco, CA
Period6/22/036/25/03

Fingerprint

Scheduling algorithms
Scheduling
Synchronization
Fires
Throughput
Communication

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Basile, C., Kalbarczyk, Z. T., & Iyer, R. K. (2003). A Preemptive Deterministic Scheduling Algorithm for Multithreaded Replicas. 149-158. Paper presented at 2003 International Conference on Dependable Systems and Networks, San Francisco, CA, United States. https://doi.org/10.1109/DSN.2003.1209926

A Preemptive Deterministic Scheduling Algorithm for Multithreaded Replicas. / Basile, Claudio; Kalbarczyk, Zbigniew T; Iyer, Ravishankar K.

2003. 149-158 Paper presented at 2003 International Conference on Dependable Systems and Networks, San Francisco, CA, United States.

Research output: Contribution to conferencePaper

Basile, C, Kalbarczyk, ZT & Iyer, RK 2003, 'A Preemptive Deterministic Scheduling Algorithm for Multithreaded Replicas' Paper presented at 2003 International Conference on Dependable Systems and Networks, San Francisco, CA, United States, 6/22/03 - 6/25/03, pp. 149-158. https://doi.org/10.1109/DSN.2003.1209926
Basile C, Kalbarczyk ZT, Iyer RK. A Preemptive Deterministic Scheduling Algorithm for Multithreaded Replicas. 2003. Paper presented at 2003 International Conference on Dependable Systems and Networks, San Francisco, CA, United States. https://doi.org/10.1109/DSN.2003.1209926
Basile, Claudio ; Kalbarczyk, Zbigniew T ; Iyer, Ravishankar K. / A Preemptive Deterministic Scheduling Algorithm for Multithreaded Replicas. Paper presented at 2003 International Conference on Dependable Systems and Networks, San Francisco, CA, United States.10 p.
@conference{b3abdac07b714fa2b05182632c899c9b,
title = "A Preemptive Deterministic Scheduling Algorithm for Multithreaded Replicas",
abstract = "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.",
author = "Claudio Basile and Kalbarczyk, {Zbigniew T} and Iyer, {Ravishankar K}",
year = "2003",
month = "12",
day = "1",
doi = "10.1109/DSN.2003.1209926",
language = "English (US)",
pages = "149--158",
note = "2003 International Conference on Dependable Systems and Networks ; Conference date: 22-06-2003 Through 25-06-2003",

}

TY - CONF

T1 - A Preemptive Deterministic Scheduling Algorithm for Multithreaded Replicas

AU - Basile, Claudio

AU - Kalbarczyk, Zbigniew T

AU - Iyer, Ravishankar K

PY - 2003/12/1

Y1 - 2003/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=1542330157&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=1542330157&partnerID=8YFLogxK

U2 - 10.1109/DSN.2003.1209926

DO - 10.1109/DSN.2003.1209926

M3 - Paper

AN - SCOPUS:1542330157

SP - 149

EP - 158

ER -