Lamport Shostak Pease Algorithm Assignment Help

Lamport Shostak Pease Algorithm : Recursively defined,

OM( m ), m 0

• Source x broadcasts value to any or all processes
• Let vi = value received through process i from source ( 0 if no value received ). Process i acts as a new source as well as initiates OM( m -1 ), sending vi to remaining ( n – 2 ) processes
• For each i, j, i ≠ j, let vj = value received by process i from process j in step 2 using O( m-1 ). Process i uses the value majority( v1, v2, …, vn -1 )

OM(0)

1. Source x broadcasts value to any or all processes
2. Every process uses the value, if no value received, 0 can be used

• Time complexity = m+1 rounds
• Message Complexity = O( n^m )
• You can reduce message complexity to polynomial by increasing time