Title:  Active Replication of Multithreaded Applications

Authors:  Claudio Basile, Zbigniew Kalbarczyk, Ravi Iyer, Keith Whisnant

Abstract: Software-based active replication is a well-known technique for
providing fault tolerance using space redundancy and fault-masking.
However, much of the recent research in software replication has yet
to be demonstrated using large real-world applications, in particular
multithreaded applications.  While multithreading can improve
performance, thread scheduling is a source of nondeterminism in
application behavior. Existing approaches to replication in
multithreaded applications employ a nonpreemptive deterministic
scheduler that guarantees the same scheduling on all replicas, at the
expense of concurrency.

This paper presents a replication framework for transparent active
replication of multithreaded applications.  The framework consists of:
(1) a loose synchronization algorithm for ensuring deterministic
behavior of replicas while preserving concurrency, (2) a virtual
socket layer for ensuring transparency of the replication framework,
and (3) a voter/fanout component for providing error detection (crash,
hang, and value errors), exclusion of faulty replicas, and reliable
broadcast of client requests to replicas.  The framework is used to
replicate the multithreaded version of the Apache web server, a
substantial real-world application. The measured throughput reduction
for a triplicated multithreaded Apache is about 23%, when compared to
the TCP-based noninstrumented version of Apache.