Distributed Speculations: Providing Fault-Tolerance and Improving Performance

Author: Țăpuș, Cristian

Year: 2006

Degree: Dissertation (Ph.D.)

Advisor: Hickey, Jason J.

Committee Members: Hickey, Jason J.; Chandy, K. Mani; Murray, Richard M.; Low, Steven H.

Option: Computer Science

Abstract

This thesis introduces a new programming model based on speculative execution and it examines the use of speculations, a form of distributed transactions, for improving the performance, reliability and fault tolerance of distributed systems. A speculation is defined as a computation that is based on an assumption that is not validated before the computation is started. If the assumption is later invalidated the computation is aborted and the state of the program is rolled back; if the assumption is validated, the results of the computation are committed. The primary difference between a speculation and a transaction is that a speculation is not isolated---for example, a speculative computation may send and receive messages, and it may modify shared objects. As a result, processes that share those objects may be absorbed into a speculation.

The contributions presented in this thesis include:

the introduction of a new programming model based on speculations,
the definition of new speculative programming language constructs,
the formal specification of the semantics of various speculative execution models, including message passing and shared objects,
the implementation of speculations in the Linux kernel in a transparent manner, and
the design and implementation of components of a distributed filesystem that supports speculations and guarantees sequential consistency of concurrent accesses to files.

Files

tapus-phd.pdf (application/pdf)