algorithm-daixie

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

本次分布式系统算法代写为6道简答题,需要按照给定的问题使用PDF回答交付。

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?
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.

 


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

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


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

 


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

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


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

发表评论