State MachinesIntroductionAn Example: MemoryOrdering of CommandsFault-toleranceAgreementOrder and StabilityAchieving Stability with Lamport ClocksAchieving Stability with Real-Time ClocksReplica-Generated UidsImplementing Replica-Generated UidsPaxos: Another ApproachStabilityLeader ElectionSetupRoundsAlgorithmAlgorithm (2)VotingExample of PaxosAnchored RoundsAny Two Successful Rounds Have the Same ValueAnchoring the RoundsAn ExampleAnother ExampleSummary of Paxon SynodThe Paxon ParliamentSummaryState MachinesCS 614Thursday, Feb 21, 2002Bill McCloskeyIntroductionState machines provide fault-tolerance through replication.They consist of state variables and commands to change the state.Clients request the state machine to execute commands.State AState AState BState BCommandClientAn Example: MemoryState variables:store: array[0..n] of wordCommands:read: command(loc: 0..n)send store[loc] to clientwrite: command(loc: 0..n, value: word)store[loc] := valueReads and writes values to and from storage.Ordering of CommandsThe machine will have multiple clients.Commands from the same client must be executed in the order they were issued.Commands from different clients must be executed in an order determined by causality.Fault-toleranceReplicas of state machine are run on multiple processors for fault-tolerance.Replicas must start in the same initial state and must process the same set of requests in the same order. This is a consensus problem.Agreement: Every non-faulty replica receives the every request.Order: Every non-faulty replica processes the requests in the same order.There are several ways of achieving these conditions…AgreementOften, agreement is met using a Byzantine Agreement protocol. Every non-faulty processor will receive each command.Clients can transmit commands to the replicas, or a single replica can serve as transmitter for the client.More efficient techniques for fail-stop failures are can be used instead.Other techniques are also possible, such as the Paxos algorithm (more later).Order and StabilityA request can be labeled with a unique ID (uid).The request is considered stable at a certain state machine replica when requests with lower uids cannot be received from correct clients.The replica must wait until a request is stable before executing it.So, a state machine processes requests in order of uids. Therefore, uid ordering is constrained by causality of requests (from earlier).Possible stability tests use Lamport clocks or real-time clocks. Replicas may also agree on a uid using agreement.Achieving Stability with Lamport ClocksMessages marked with a logical timestamp. This is its uid.Causality requirements are satisfied.Clients must periodically make “null” requests.A request is stable at a replica when a request with a larger timestamp has been received from every client. Then no lower uids can arrive.Requires FIFO channels (easy). Works in the presence of fail-stop failures.Achieving Stability with Real-Time ClocksReal-time clock value, together with the identity of the sending process, is the uid.To satisfy causality, a client can make only one request per clock tick, and message delivery must take longer than the difference between clocks on different processors.Let  be the time for a request to reach every correct processor.A request is stable if its timestamp is at least  time units in the past, according to the local clock. This imposes a delay in processing.Replica-Generated UidsOrdering using Lamport clocks requires all processors to communicate (null requests).Real-time clock ordering requires clock synchronization, also expensive.Could also have the replicas themselves agree on a uid for each request.Each replica proposes a candidate uid. The replicas agree on a uid, accepting the request.Clients cannot execute a request until the previous request is accepted, to guarantee causality.Implementing Replica-Generated UidsFinal uid is always at least the candidate uid.A request r’ seen after a request r has been accepted has a higher candidate uid than the final uid of r.A new candidate uid will be one greater than any candidate or final uid so far, plus a factor of i/N to make it unique.Each replica broadcasts its candidate uid.The final uid is selected as the maximum of all the uids received.Paxos: Another ApproachLamport’s Paxon Synod is an agreement algorithm.It is efficient and practical.It assumes a partially synchronous model.Messages are not always delivered on time.Messages may be lost or duplicated.Processors may fail silently.Guarantees:Agreement: Everyone agrees on the same value.Validity: The chosen values was one of the candidates.Termination is not guaranteed.StabilityAn execution fragment  is stable if:No processors fail or recover in .No packets are lost or duplicated in .Delivery of messages is on time. is nice if it is stable and if a majority of processes are alive.We’ll see that Paxos terminates if there is an execution fragment which is nice for long enough.Leader ElectionPaxos requires a leader to “run” the algorithm.Processes exchange “Alive” messages to try to detect failures.When the current leader fails, a new one is selected which has the largest processor ID.Failure detector doesn’t always work, so there may be multiple leaders or no leader.The algorithm may not terminate if there are always too many leaders.SetupThe algorithm operates in a sequence of rounds.Multiple rounds may be ongoing at the same time.In each round, the leader tries to get a majority for a certain value.Processes vote in each round.If a majority of processes vote in a round, then the value chosen is the one proposed by the leader.If too few processes vote in the round, it fails and a new one is started.RoundsEach round is numbered with a tuple (l, r), where l is the process ID of the leader and r is the leader’s index for that round.Lexicographic ordering is used on the rounds.This way, round numbers are unique.Thus, each round has a unique value, since a leader only proposes one value, and a round only has one leader.Algorithm1. Leader informs other replicas that round R is starting.2. Each replica finds the last round before R in which it voted. It sends this vote to the leader.3. The leader waits for these