1. Consider a distributed system of four processes as shown in Figure 1. The system is synchronous, and the minimum and maximum network delays (in seconds) between each pair of processes are shown in the figure as [min, mar against each channel. Assume no messages are lost on the channel, and the processing time at each process is negligible compared to network delays. a [10, 15] 18,10] 13,4] b [2,9] [2,5] d [1,2] Figure 1: Figure for question 1. (a) (3 points) Consider an all-to-all heartbeat protocol, where each process sends a heartbeat to each other process periodically every T=60s, and each process sets a timeout computed appropriately from the known bounds on network delay) to detect failure of other processes. Suppose that process a crashes. For every other process, calculate how long it will take to detect a's failure, in the worst case. (b) (3 points) Now consider a small extension of the protocol in in Q1(a) - as soon as a process detects that another process p has crashed via a timeout, it sends a notification to all other processes about p's failure. Suppose that process a is the only process that crashes. For every other process, calculate how long it will take to detect a's failure, in the worst case. (c) (2 points) If it is known that no more than two processes may crash within a few hours of each other, how would you redesign the heartbeat protocol described in Q1(a) to minimize bandwidth usage, without increasing the worst case time taken to detect the failure of a process by at least one alive process. (Hint: do we really need all-to-all heart beats?] (d) (2 points) Assuming the modification in Q1(c), list the minimal set of processes a must send heart- beats to, so as to minimize the worst case time taken to detect failure of a by at least one alive process. 1. Consider a distributed system of four processes as shown in Figure 1. The system is synchronous, and the minimum and maximum network delays (in seconds) between each pair of processes are shown in the figure as [min, mar against each channel. Assume no messages are lost on the channel, and the processing time at each process is negligible compared to network delays. a [10, 15] 18,10] 13,4] b [2,9] [2,5] d [1,2] Figure 1: Figure for question 1. (a) (3 points) Consider an all-to-all heartbeat protocol, where each process sends a heartbeat to each other process periodically every T=60s, and each process sets a timeout computed appropriately from the known bounds on network delay) to detect failure of other processes. Suppose that process a crashes. For every other process, calculate how long it will take to detect a's failure, in the worst case. (b) (3 points) Now consider a small extension of the protocol in in Q1(a) - as soon as a process detects that another process p has crashed via a timeout, it sends a notification to all other processes about p's failure. Suppose that process a is the only process that crashes. For every other process, calculate how long it will take to detect a's failure, in the worst case. (c) (2 points) If it is known that no more than two processes may crash within a few hours of each other, how would you redesign the heartbeat protocol described in Q1(a) to minimize bandwidth usage, without increasing the worst case time taken to detect the failure of a process by at least one alive process. (Hint: do we really need all-to-all heart beats?] (d) (2 points) Assuming the modification in Q1(c), list the minimal set of processes a must send heart- beats to, so as to minimize the worst case time taken to detect failure of a by at least one alive process