Q1. A leader election in a general network is described as below:
Every processor, p keeps a record of the maximum processor id,
pmaxid . At each round, every processor broadcast maximum id at all of its edges. After, diam (=Diameter of Network) rounds, if the current maximum id is the processors own id, the processor is a leader otherwise it is not a leader.
1) Prove that at the end of diam rounds, there is only one leader and every other processor is a non-leader.
2) What is the message complexity? Derive.
Q2. Explain how to eliminate the <already> messages from the modified flooding algorithm (See lecture notes) in the synchronous case and still have a correct algorithm. What is the message complexity of the resulting algorithm?
Q3. Observe following algorithm for n-process mutual exclusion.
Shared variables:
x ε {1,2,3,…, n}
y ε {0,1} initialized to 0
Code for pi
<Entry >:
1. 1:x=i
2. 2: ify!=0thengotoLine1 3. 3:y=1
4. 4: ifx!=ithengotoLine1
<Critical Section> <Exit> 5: y = 0 <Remainder>
For each question, either provide a proof, or display an execution where it fails.
Does this algorithm satisfy 1) mutual exclusion?
2. 2) no-lockout? 3. 3) no-deadlock?
Q4. In the tournament mutual exclusion algorithm, given n threads, how many pair-wise competitions are needed to be performed until every thread enters the critical section? Assume that each thread enters the critical section exactly once.
Q5. Prove that there is a unique maximal consistent cut preceding any given cut. Also, prove that algorithm for finding maximal consistent cut is correct.
Q6. Consider a synchronous system. Suppose that we want Byzantine consensus to satisfy the following condition: every non-faulty node’s decision must equal the input of some non-faulty processor. Show that to be able to satisfy these conditions while tolerating up to f-Byzantine faults, the number of nodes n must be at least max(3, m)f+ 1, if each node’s input is an integer value between 0 and m-1 and m > 2.