Non-Determinism Replica Execution Consistency Algorithm

Junling Wang and Yan Cai


State Machine, Distributed Object Computing, Replica, Multithreading, Nondeterminism


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