Distributed speculative execution for reliability and fault tolerance: an operational semantics |
| |
Authors: | Cristian ??pu? Jason Hickey |
| |
Affiliation: | (1) Computer Science Department, California Institute of Technology, Pasadena, USA |
| |
Abstract: | This paper examines the use of speculations, a form of distributed transactions, for improving the 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 found to be false, the computation is aborted and the state of the program is rolled back; if the assumption is found to be true, 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. We present a syntax, and an operational semantics in two forms. The first one is a speculative
model, which takes full advantage of the speculative features. The second one is a nonspeculative, nondeterministic model,
where aborts are treated as failures. We prove the equivalence of the two models, demonstrating that speculative execution
is equivalent to failure-free computation. |
| |
Keywords: | Speculations Operational semantics Distributed systems Fault tolerance Transactions |
本文献已被 SpringerLink 等数据库收录! |
|