Reference no: EM133248206

Assignment:

Although the NE Patriots team did not win the last Superbowl, their coach is still paranoid. Due to their paranoia they decide to design a failure detector for an asynchronous system of N processes (N very large). A cornerback has designed a ring-based failure detection protocol that works as follows: each process i selects a set of target processes (once selected, these targets don't change) and asks these processes to send to it (i.e., to process i) heartbeats directly. Targets are selected as follows. All processes are organized in a virtual ring. Targets of a process i include three subsets: its k predecessors, its k successors, and k further processes chosen randomly among all non-predecessor/successor/i processes. Once the list of targets is selected, it is not changed (including the randomly selected members). k is a fixed number much smaller than N, and known to all. Heartbeats are not relayed (so this is not gossip, but more like ring failure 6 detection, except there is no ring), and process i times out if it doesn't receive heartbeats. A process is detected as failed if any of its heartbeat receivers do not receive expected heartbeats within a pre-specified timeout

When is completeness violated? That is, find the value M so that if there are (M-1) simultaneous failures, all of them will be detected, but if there are M simultaneous failures then not all of them may be detected.

Is the algorithm 100% accurate?

If the period is fixed (say 1 s) at all processes, what is the load on each process in terms of heartbeats that it needs to send? Calculate the worst case, best case, and average load.