PDL Abstract

Static Analysis Meets Distributed Fault-Tolerance: Enabling State-Machine Replication with Nondeterminism

Proceedings of the 2nd Workshop on Hot Topics in System Dependability (HotDep '06), Seattle, WA. Nov. 8, 2006.

Joseph G. Slember, Priya Narasimhan

Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213


Midas is an inter-disciplinary approach to supporting state-machine replication for nondeterministic
distributed applications. The approach exploits compile-time static analysis to identify both first-hand
and second-hand sources of nondeterminism. Subsequent runtime compensation occurs through either the transfer of nondeterministic checkpoints or the reexecution of inserted code, and restores consistency
among replicas before each new client request. The approach avoids the need for lock-step synchronization
and leverages application-level insight to address only the nondeterminism that matters. Our preliminary
evaluation demonstrates Midas’ feasibility and current performance overheads.