Non-Determinism Replica Execution Consistency Algorithm

Junling Wang and Yan Cai

Keywords

State Machine, Distributed Object Computing, Replica, Multithreading, Non-determinism

Abstract

The state machine approach is an established way of building reliable distributed applications. However, non-determinism such as multithreading leads to divergence among replicas. Thus, classical state machine approach excludes multithreading although it is useful in widely deployed multi-core CPU and multi-CPU systems. After carefully inspecting distributed object computing, by analyzing client semantics in context, this paper proposes a replica execution consistency algorithm RECA_SM based on the state machine approach, which is distributed and deterministic supporting multithreading to execute independent objects concurrently. The paper further proves that RECA_SM satisfies the properties of safety and liveness. The algorithm localizes computation without additional communication costs among replicas, and experiments show that RECA_SM can increase system performance effectively.

Important Links:

Go Back