State Machine Replication
For the subsequent discussion a State Machine will be defined as the following tuple of values (See also Mealy machine and Moore Machine):
- A set of States
- A set of Inputs
- A set of Outputs
- A transition function (Input x State -> State)
- An output function (Input x State -> Output)
- A distinguished State called Start.
A State Machine begins at the State labeled Start. Each Input received is passed through the transition and output function to produce a new State and an Output. The State is held stable until a new Input is received, while the Output is communicated to the appropriate receiver.
It should be clear that any algorithm can be implemented using this model if driven by an appropriate Input stream. In particular, this discussion requires a State Machine to have the following property:
- Deterministic:
- Multiple copies of the same State Machine begun in the Start state, and receiving the same Inputs in the same order will arrive at the same State having generated the same Outputs.
Read more about State Machine Replication: The State Machine Approach, Historical Background
Other articles related to "replication, state machine replication, state machine":
... Byzantine fault tolerant replication protocols were long considered too expensive to be practical ... Tolerance" (PBFT) algorithm, which provides high-performance Byzantine state machine replication, processing thousands of requests per second with sub-millisecond increases ... PBFT triggered a renaissance in BFT replication research, with protocols like Q/U, HQ,, Zyzzyva, and ABsTRACTs working to lower costs and improve performance and protocols like Aardvark working to ...
... Leslie Lamport was the first to propose the state machine approach, in his seminal 1984 paper on "Using Time Instead of Timeout In Distributed Systems" ... the approach in his paper "Implementing Fault-Tolerant Services Using the State Machine Approach A Tutorial" ... Recent work by Miguel Castro and Barbara Liskov used the state machine approach in what they call a "Practical Byzantine fault tolerance" architecture that replicates especially ...
Famous quotes containing the words state and/or machine:
“What thou art is mine;
Our state cannot be severed, we are one,
One flesh; to lose thee were to lose myself.”
—John Milton (1608–1674)
“The white man regards the universe as a gigantic machine hurtling through time and space to its final destruction: individuals in it are but tiny organisms with private lives that lead to private deaths: personal power, success and fame are the absolute measures of values, the things to live for. This outlook on life divides the universe into a host of individual little entities which cannot help being in constant conflict thereby hastening the approach of the hour of their final destruction.”
—Policy statement, 1944, of the Youth League of the African National Congress. pt. 2, ch. 4, Fatima Meer, Higher than Hope (1988)