Exercise of Asynchronous Network Algorithms (II)
Chapter 15, Lynch, Nancy A. Distributed Algorithms, Morgan Kaufmann Series in Data Management Systems. Elsevier Science. Kindle Edition.
Master student: do (2 -6) of the following exercise.
Reseach student: do all exercises
- (15.28.) Give an upper bound for the time complexity of the AsynchBellmanFord shortest paths algorithm. It should be as tight as you can make it.
- (15.29.) Write precondition-effect code for a modification of AsynchBellmanFord in which processes produce parent and distance outputs, by means of an acknowledgment protocol. Prove the correctness correctness of your protocol and analyze its complexity.
- (15.30.) Design an algorithm to find the shortest paths from a fixed source node i0 to all other nodes in the network. Your algorithm should have a much better time bound than the AsynchBellmanFord algorithm, say, O (n( l + d)).
- (15.32.) Give complete precondition-effect code for the GHS minimum spanning tree algorithm.
- (15.33.) Consider the GHS minimum spanning tree algorithm. (a) State and prove carefully an upper bound on the time from when the first process awakens until the last process announces its results. You may assume that a preliminary protocol is used to awaken all the nodes as quickly as possible. (b) How tight is the upper bound you proved in (a)? That is, describe a particular execution of the algorithm that takes time that is as close as you can get to your upper bound. 15.34. Describe an execution of GHS in which a reject message arrives at process i along channel Cj,i, in response to a previous test message by i, at a time when i classifies edge (i, j) as a branch edge. Argue that the algorithm handles this case correctly.
- (15.43.) Consider a “banking system” in which each process in a network keeps a number indicating an amount of money. We assume, for simplicity, that there are no external deposits or withdrawals, but messages travel between processes at arbitrary times, containing money that is being “transferred” from one location to another. The channels preserve FIFO order. Design a distributed network algorithm that allows each process to decide on (that is, to output) its own balance, so that the total of all the balances is the correct amount of money in the system.
Assume that the execution of this algorithm is triggered by signals arriving from the outside, at one or more of the system locations. (These signals could happen at any time and could happen at different times at different locations.)