Homework 2

Total points 6

Question 1 Given that there are at most two failures at a time in the system, which of the following protocols does NOT satisfy completeness? 1 point

• Ring-style heartbeating where each process heartbeats to only its clockwise neighbor

• All-to-all heartbeating

• Gossip-style heartbeating

• Ring-style heartbeating where each process heartbeats to both its clockwise neighbor and anticlockwise neighbor

SOLUTION-

Question 2 Which of the following takes O(log(log(N)) time after a majority of the nodes have received the gossip? 1 point

• Push gossip

• Pull gossip

SOLUTION-Push gossip

Question 3 Someone designs a new failure detector where processes are organized in a binary tree. In a binary tree, there is one node (process) at the root (level 1), which has 2 children (nodes or processes) at level 2, which in turn each have 2 children at level 3, and so on. If node A is a child of node B, then B is a parent of A (and vice-versa). In this heartbeat protocol, every process sends heartbeats to its parent in the tree. Heartbeats are not relayed or gossiped. This protocol is: 1 point

• Complete

• Neither complete nor accurate

• Accurate

SOLUTION-

Question 4 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). (1 point)

1. (C, 349). ____________

2. (C, 123). ____________

3. (C, 60). _____________

4. (C, 355). ____________

1 point

1. 1. = (C, 349), A: (C, 349, 140)

2. 2. = (C, 123), A: (C, 340,133)

3. 3. = (C, 60), A: (C, 340, 133)

4. 4. = (C, 355), A: (C, 355, 140)

1. 1. = (C, 349), A: (C, 349, 141)

2. 2. = (C, 123), A: (C, 355,133)

3. 3. = (C, 60), A: (C, 355, 133)

4. 4. = (C, 355), A: (C, 355, 140)

1. = (C, 349), A: (C, 349, 140)

2. = (C, 123), A: (C, 340,133)

3. = (C, 60), A: (C, 340, 133)

4. = (C, 355), A: (C, 340, 133)

1. = (C, 349), A: (C, 349, 140)

2. = (C, 123), A: (C, 340,140)

3. = (C, 60), A: (C, 340, 140)

4. = (C, 355), A: (C, 355, 140)

SOLUTION-

Question 5 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.) 1 point

• Decrease in bandwidth

• Decreases false positive rate

• Increases false positive rate

• Increases detection time

SOLUTION-Decreases false positive rate, Increases detection time

Question 6 In a datacenter with 10,000 machines, the MTTF (mean time to failure) of a single server is 48 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: 1 point

• 2.5 hours

• 0.1 hours

• 3.4 months

• 3.4 hours

SOLUTION-2.5 hours