Scribd Logo
Upload

Welcome to Scribd!

  • 5 views

    LPS and Phase King Algorithm IIITH

    Uploaded by

    Arza Siddiqui

    Copyright:

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

    LPS and Phase King Algorithm IIITH

    Uploaded by

    Arza Siddiqui
    5 views11 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    5 views11 pages

    LPS and Phase King Algorithm IIITH

    Uploaded by

    Arza Siddiqui

    Copyright:

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

    Edited slides of Pallabh Dasgupta and

    content from Kshemkalyani text book

    1
    Lamport-Shostak-Pease Algorithm
     Algorithm Broadcast( N, t ) where t is the resilience

    For t = 0, Broadcast( N, 0 ):

    Pulse
    1 The general sends value, xg to all processes,
    the lieutenants do not send.
    Receive messages of pulse 1.
    The general decides on xg.
    Lieutenants decide as follows:
    if a message value, x was received from g in pulse-1
    then decide on x
    else decide on udef

    2
    Lamport-Shostak-Pease Algorithm contd..
    For t > 0, Broadcast( N, t ):
    Pulse Pulse
    1 The general sends value, xg to t +1 Receive messages of pulse t +1.
    all processes, the lieutenants The general decides on xg.
    do not send. For lieutenant p:
    Receive messages of pulse 1. A decision occurs in
    Lieutenant p acts as follows: Broadcastq( N – 1, t – 1 ) for
    if a message value, x was each lieutenant q
    received from g in pulse-1 Wp[q] = decision in
    then xp = x else xp = udef ; Broadcastq( N – 1, t – 1 )
    Announce xp to the other yp = majoity (Wp)
    lieutenants by acting as
    a general in
    Broadcastp( N – 1, t – 1 ) in
    the next pulse

    3
    Conclusion
    In case of a faulty general all the arrays of the correct processes are the same.
    Example: For two correct process Pi and Pk
    If Pi has 001101 then Pk too has 001101

    In case of a loyal general, all correct process agree on the same value. That is, the subarray
    compassing of the positions of the loyal lieutanents of every correct process has the same bit
    (either 0 or 1). Say among the 6 (N) bits the first 4 (first 2N/3) are those of the loyal lieutenants and
    the last 2 (last N/3 )are of the faulty ones. Then for two correct process Pi and Pk then
    If Pi has 111101 then Pk has 111110. The first four bits will be the same for all.

    4
    To Prove all correct processes decide on the same value

    Two cases:
    General is loyal
    General is not loyal

    5
    Loyal general
    Lemma 1: If the general is correct, if there are f faulty processes , and if N>2f+t, then all correct
    processes decide on the input of the general.

    Lemma 2: Given t, the algorithm is correct if t>=f and there are a total of 3t+1 or more processes.

    6
    Features
     Termination: If Broadcast( N, t ) is started in pulse 1, every process decides
    in pulse t + 1

     Dependence: If the general is correct, if there are f faulty processes, and if


    N > 2f + t, then all correct processes decide on the input of the general

     Agreement: All correct processes decide on the same value

    The Broadcast( N, t ) protocol is a t-Byzantine-robust broadcast protocol for t <


    N/3

    Time complexity: O( t + 1 ) Message complexity: O( Nt )

    7
    Phase King Algorithm

    8
    Proof
    There are f+1 phases but only f malicious process hence at least one of the phase kings is non
    malicious. Let that be for phase K.

    Consider the three cases that might be true for two non malicious process Pi and Pj.
    1. Pi and Pj decided on their majority value at the end of round K
    2. Pi and Pj decided on the phase king value at the end of round K
    3. Pi decided on majority and Pj decided on phase king value at the end of round K

    9
    Proof

    10
    Proof
    Once a non malicious phaseking executes his two rounds; the values of the non malicious
    processes will not change with any further phase king rounds

    Going forward, all the non faulty processes already have agreed on a same value. That is
    more than 3n/4 process now have the same value of v which they send everyone else in round1 of
    future phases. So all non faulty ppl will get a clear majority of > n/2+f and will continue to decide
    on their v value.

    11

    You might also like