Cloud Computing Concepts Part 1 | Week 2

Quiz 1: Homework 2

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). ( )

1. (C, 349). ____________
2. (C, 123). ____________
3. (C, 60). _____________
4. (C, 355). ____________

1. = (C, 349), A: (C, 349, 133)
2. = (C, 123), A: (C, 340,133)
3. = (C, 60), A: (C, 340, 133)
4. = (C, 355), A: (C, 355, 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)

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,133)
3. = (C, 60), A: (C, 340, 133)
4. = (C, 355), A: (C, 355, 140)

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: ( )

• 2.5 minutes
• 0.1 hours
• 2.5 hours
• 2.5 days

---