Exercise of Basic Asynchronous Network Algorithms
Chapter 15, Lynch, Nancy A. Distributed Algorithms, Morgan Kaufmann Series in Data Management Systems. Elsevier Science. Kindle Edition.
Master student: do (5 -10) of the following exercise.
Reseach student: do all exercises
- (15.2.)Give precondition-effect code for the modification of AsynchLCR, which includes wakeup inputs and receive buffers.
- (15.4.) Consider the PetersonLeader algorithm in a ring with n = 15 nodes, in which the UIDs for processes P1,…, P16 are, respectively, 25, 3, 6, 15, 19, 8, 7, 14, 4, 22, 21, 18, 24, 1, 10, 23. Which process is elected as leader?
- (15.5.) Design a version of the PetersonLeader algorithm for the synchronous network model described in Chapters 2 and 3. The processes in your algorithm may know n. Strive to make your algorithm as simple (to write and to understand) as possible, while keeping the unidirectionality and the O (n log n) communication complexity. Analyze the time (number of rounds) complexity of your algorithm.
- (15.6.) Give a careful proof of the O (n( l + d)) upper bound for the time complexity of the PetersonLeader algorithm.
- (15.7.) Design a version of the PetersonLeader leader-election algorithm for rings with bidirectional communication. In the new version of the algorithm, the UIDs remaining in contention do not need to precess around the ring, but can stay where they originate; each process simply collects the UIDs from its two active neighbors at each phase. Give precondition-effect code for your algorithm. Analyze its message and time complexity.
- (15.12.) Consider the problem of leader election in networks based on bidirectional line graphs; such a graph consists of n processes numbered 1,…, n, arranged in a line, with bidirectional edges between each pair of neighbors. Assume that each process knows its neighbors by the local names “right” and “left,” with the orientation consistent along the line. Assume that each process knows whether or not it is an endpoint. Assume that the processes have no knowledge of n.
Give a leader-election algorithm for such networks that uses a small number of messages.
- (15.17.) Design an algorithm for broadcast and acknowledgment in asynchronous networks, in which the time complexity depends on the diameter of the network rather than the total number of nodes.
- (15.18.) Extend the spanning tree, broadcast, and convergecast algorithms to the case where the network is based on a strongly connected directed graph. Analyze the complexity of your algorithms.
- (15.22.) For the AsynchBFS algorithm,
Produce an execution that uses as many messages as you can manage; try to achieve the given upper bound of O (n | E |).
Produce an execution that takes the longest time that you can manage until a stable state is reached; try to achieve the given upper bound of O (diam. n( l + d)).
- (15.23. ) Write precondition-effect code for the modification of AsynchBFS in which processes produce parent outputs, by means of an acknowledgment protocol. Do not assume any knowledge of the size or diameter of the network graph.