Zeyuan Hu's page

State Machine Replication Approach

State Machine Replication

  • State Machine Replaction system properties:

    • Available
    • Fault tolerant
    • Appear to behave like a single machine
  • t fault tolerant: A system consisting of a set of distinct components is t fault tolerant if it satisfies its specification provided that no more than t of those components become faulty during some interval of interest.

  • t fault-tolerant state machine implementation: replicating that state machine and running a replica on each of the processors in a distributed system. Provided each replica being run by a nonfaulty processor starts in the same initial state and executes the same requests in the same order, then each will do the same thing and produce the same output.

  • When processors can experience Byzantine failures, an ensemble implementing a t fault-tolerant state machine must have at least \(2t + 1\) replicas, and the output of the ensemble is the output produced by the majority of the replicas. (因为Byzantine failures可以产生错误的结果,因此需要大多数replica的结果正确。由于我们是t fault-tolerant, 因此有t replicas可以产生Byzantine failures,因此我们需要额外t+1产生正确结果的replica,也就是2t+1 total replicas)

  • If processors experience only fail-stop failures, then an ensemble containing \(t + 1\) replicas suffices, and the output of the ensemble can be the output produced by any of its members. (Fail-stop failures的话,replica产生错误就停止工作了,因此我们总共只需要t+1 replicas因为只要保证有一个replica工作就可以了)

  • Implementing Replication:

    • Agreement: Every nonfaulty state machine replica receives every request.

      • Implemented by clients
      • When a client makes a request, it broadcasts the request to all servers in the system
    • Order: Every nonfaulty state machine replica processes the requests it receives in the same relative order.

      • Implemented by servers
      • Define a total order of requests in the system and execute requests in that order
      • Process a request with the lowest timestamp that has been received by that replica
      • Stability: The replica can never receive an event with a lower timestamp

        • Implementing stability: Receive requests from a client in increasing order (Given by FIFO channels and logical clocks)
        • A request is stable once a request has been received from each client with a greater timestamp


comments powered by Disqus