Q1. Given that there are at most two failures at a time in the system, which of the following protocols does NOT satisfy completeness? ( )
Ring-style heartbeating where each process heartbeats to both its clockwise neighbor and anticlockwise neighbor
Gossip-style heartbeating
All-to-all heartbeating
Ring-style heartbeating where each process heartbeats to only its clockwise neighbor
Q2. Which of the following takes O(log(log(N)) time after a majority of the nodes have received the gossip? ( )
Pull gossip
Push gossip
Q3. Alice and Bob are employees in your company who have each been given the task of inventing a failure detection algorithm for an asynchronous system that tolerates 3 simultaneous process failures. You are called to judge whether their protocols satisfy the requirement. Alice’s protocol has each process p randomly pick 3 other processes to send its heartbeats to, and thereafter p periodically sends its heartbeats to these processes. Bob’s protocol has each process p randomly pick 3 other processes to receive heartbeats from, and thereafter each of these 3 picked processes periodically send its heartbeats to p. Note that in each of these protocols, the heartbeats are direct ones rather than gossip-style.
Then, which of the following statements is correct? ( )
Both Alice’s and Bob’s protocols are complete, i.e., they do not miss any failures.
Bob’s protocol is complete but Alice’s protocol is not.
Alice’s protocol is accurate but Bob’s protocol is not.
Alice’s protocol is complete but Bob’s protocol is not.
Q4. A startup in your home garage is designing a new gossip-style failure detection similar to that discussed in lecture. In this new protocol, at a node (process or server) A, at local time = 140, its local entry for a node C is (address, counter, time) = (C, 340, 133). Tfail = 40. A receives a gossip message from node B containing one heartbeat as (sender-id, heartbeat counter), as shown below. Select the choice below where in all (four) cases, the left entry (heartbeat) leads to the right entry (updated heartbeat at A for C after receiving this heartbeat). ( )
Q5. In a heartbeat protocol for failure detection, increasing the timeout (used for declaring a member as failed), without changing any other protocol parameter, results in which of the following? (Select multiple correct answers.) ( )
Increases false positive rate
Decreases false positive rate
Increases detection time
Decrease in bandwidth
Q6. In a datacenter with 10,000 machines, the MTTF (mean time to failure) of a single server is 36 months. You can assume each month has 30 days. The MTTF (mean time to failure) until the next server fails in the data center is approximately: ( )
