算法代写 | Distributed System 分布式系统算法

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: if y != 0 then go to Line 1
3. 3: y = 1
4. 4: if x != i then go to Line 1
<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?

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.

E-mail: [email protected]  微信:dmxyzl003

E-mail: [email protected]  微信:itcsdx