Algorithms in algorithm in general synchronous networks
(Chapter 4 Lynch, Nancy A. (1996-04-16). Distributed Algorithms (The Morgan Kaufmann Series in Data Management Systems) (Kindle Locations 1327-1335). Elsevier Science. Kindle Edition.)
Master student: do (3 to 6) of the following exercise
Research Student: do all of the following exercise
4.2. In terms of n, the number diam | E | of messages used in the FloodMax algorithm is easily seen to be O (n3). Either produce a class of digraphs in which the product diam | E | really is Ω( n3) or show that no such class of digraphs exists.
4.3. For the OptFloodMax algorithm, either prove a smaller upper bound than O (n3) on the number of messages or exhibit a class of digraphs and corresponding UID assignments in which the number of messages is Ω( n3).
4.4. Consider the “further optimized” version of OptFloodMax described at the end of Section 4.1.3, which prevents processes from resending max-uid information to processes from which they have previously received the same information. (a) Give code for this algorithm, in the same style as the other code in this chapter. (b) Prove the correctness of your algorithm by relating it to OptFloodMax, using the same sort of simulation strategy used in the proof of correctness for OptFloodMax itself (i.e., in the proof of Theorem 4.2).
4.7 Describe in detail an algorithm that extends SynchBFS to produce not only child pointers, but also information about shortest routes from children in the BFS tree to their parents. This information should be distributed along those paths so that each process on a path knows the next process along the path. Analyze the time and communication complexity.
4.10. Devise the most efficient leader-election algorithm you can, for a strongly connected directed network in which the processes have UIDs but do not have any knowledge of the number of nodes in or diameter of the network.
4.14. (a) Give code for the BellmanFord shortest paths algorithm. (b) Prove its correctness using invariant assertions.