Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    Unit 4 Part 1 B

    Uploaded by

    phys2038

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Unit 4 Part 1 B

    Uploaded by

    phys2038
    4 views31 pages

    Original Title

    Unit 4 Part 1 b

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    4 views31 pages

    Unit 4 Part 1 B

    Uploaded by

    phys2038

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 31

    CS 3551 DISTRIBUTED

    COMPUTING
    Consensus algorithms for Byzantine failures (synchronous
    system)
    1. Upper bound on Byzantine processes
    2. Byzantine agreement tree algorithm: exponential (synchronous system)
    Recursive formulation
    3. Byzantine agreement tree algorithm: exponential (synchronous system)
    Iterative formulation
    4. Phase King Algorithm
    Upper bound on Byzantine processes
    Proof:
    Proof Key Points:
    Byzantine agreement tree algorithm: exponential
    (synchronous system) - Recursive
    Byzantine agreement tree algorithm: exponential
    (synchronous system) - Recursive
    Simple Algorithm
    1. Every process believes in majority.
    2. Round 1:
    a. Sends out value to everyone.
    b. Every process receiving a value from commander sends it to processes it knows.(Unfolding)
    3. Round 2:
    a. Each process takes majority of the values it received. (Folding)
    b. If none received => Uses default value.
    Phase-king algorithm for consensus: polynomial
    (synchronous system)
    Correctness:
    1. Among the f +1 phases, the phase king of some phase k is non-malicious because there
    are at most f malicious processes.
    2. As the phase king of phase k is non-malicious, all non-malicious processes can be seen to
    have the same estimate value v at the end of phase k.
    a. Specifically, observe that any two non-malicious processes Pi and Pj can set their estimate v in three ways:
    i. Both Pi and Pj use their own majority values.
    ii. Both Pi and Pj use the phase king’s tie-breaker value.
    iii. Pi uses its majority value as the new estimate and Pj uses the phase king’s tie-breaker as the new
    estimate
    3. All non-malicious processes have the same consensus estimate x at the start of phase k+1
    and they continue to have the same estimate at the end of phase k+1. This is self-evident
    because we have that n > 4f and each non-malicious process receives at least n−f > n/2+f
    votes for x from the other non-malicious processes in the first round of phase k+1.
    Consensus algorithms for Byzantine failures (synchronous
    system)
    1. Upper bound on Byzantine processes
    2. Byzantine agreement tree algorithm: exponential (synchronous system)
    Recursive formulation
    3. Byzantine agreement tree algorithm: exponential (synchronous system)
    Iterative formulation
    4. Phase King Algorithm
    Example
    Explanation
    Iterative Algorithm
    Iterative Algorithm
    Working:
    Correctness

    You might also like