गुरुर्ब्रह्मा गुरुर्विष्णु गुरुर्देवो महेश्वरा गुरुर्साक्षात परब्रह्म तस्मै श्री गुरवे नमः !

WEEK-5

Homework 5

Total points 15

Question 1 In an asynchronous system, the Paxos protocol: 1 point

Is always live
Is always guaranteed to converge within a time bound
Shows that the Impossibility of Consensus (FLP) result is wrong
Is always safe

SOLUTION-Is always safe

Question 2 Someone tells you the consensus protocol discussed in lecture for synchronous systems is wrong because we do not know f (i.e., the number of failures in a group of processes). Your response is: 1 point

This is a hard problem, and an unsolved one.
Yes, the algorithm discussed in lecture is incorrect if we don’t know f.
You can always set f=N, and the discussed algorithm would then be correct for synchronous systems.
You can always set f=1, and the discussed algorithm would then be correct for synchronous systems.

SOLUTION-You can always set f=N, and the discussed algorithm would then be correct for synchronous systems.

Question 3

For the run of the Chandy-Lamport algorithm, answer the following question. Wherever you have to write your answer as a list, give a comma-separated list in alphabetical order. (1 point)

· The list of all messages (among a-f) captured by the snapshot as a part of channel states is:

SOLUTION-b, e, f

Question 4

For the run of the Chandy-Lamport algorithm, answer the following question. (1 point)

· Consider all messages such that both its send and receive events are present as part of the state of some process captured by the snapshot. The number of such messages is:

SOLUTION-

Question 5

For the run of the Chandy-Lamport algorithm, answer the following question. (1 point)

· The number of messages such that both its send and receive happen causally after the snapshot is:

SOLUTION-2

Question 6

For the run of the Chandy-Lamport algorithm, answer the following question. (1 point)

· The number of messages such that its send happens causally after the snapshot but its receive is before the snapshot is:

SOLUTION-

Question 7 A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using FIFO ordering for multicasts. All sequence numbers start with zeros.

Answer the following question. (1 point)

· The sequence vector at the end of the run at P0, as a comma-separated list (without the brackets), is:

SOLUTION-1, 3, 0, 1

Question 8 A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using FIFO ordering for multicasts. All sequence numbers start with zeros.

Answer the following question. (1 point)

· The sequence vector associated with the send event of the only multicast that P3 sends out, as a comma-separated list (without the brackets), is: 1 point

SOLUTION-0, 0, 0, 1

Question 9 A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using FIFO ordering for multicasts. All sequence numbers start with zeros.

Answer the following question. (1 point)

· The sequence vector at the end of the run at P2, as a comma-separated list (without the brackets), is:1 point

SOLUTION-

Question 10 A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using FIFO ordering for multicasts. All sequence numbers start with zeros.

Answer the following question. (1 point)

· The total number of multicasts that are buffered across all processes in this entire run is: 1 point

SOLUTION-

Question 11 A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using causal ordering for multicasts. All sequence numbers start with zeros.

Answer the following question. (1 point)

· The vector of sequence numbers for the only multicast that P0 sends out, as a comma-separated list (without the brackets), is: 1 point

SOLUTION-

Question 12 A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using causal ordering for multicasts. All sequence numbers start with zeros.

Answer the following question. (1 point)

· The sequence vector at the end of the run at P2, as a comma-separated list (without the brackets), is:

SOLUTION-1, 2, 2, 1

Question 13 A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using causal ordering for multicasts. All sequence numbers start with zeros.

Answer the following question. (1 point)

· The sequence vector associated with the send event of the last (i.e., third) multicast that P1 sends out, as a comma-separated list (without the brackets), is: 1 point

SOLUTION-

Question 14 A group of four processes P0-P3 sends out multicasts in a run as shown below. The group is using causal ordering for multicasts. All sequence numbers start with zeros.

Answer the following question. (1 point)

· The total number of multicasts that are buffered across all processes in this entire run is: 1 point

SOLUTION-

Question 15 A group of 3 processes, P1 through P3, is running virtual synchrony. In this run, initially all three processes have the view {P1,P2,P3}. In this view a single multicast M is sent by process P2. Following this, P2 crashes, and thereafter P1 and P3 deliver a new view containing only {P1,P3}. Which of the following scenarios DO NOT satisfy virtual synchrony? Please select all correct answers, as there are multiple correct answers. 1 point

M is delivered by both P1 and P3 in the view {P1,P3}.
M is delivered by P3 in the view {P1,P2,P3} and by P1 in the view {P1,P3}.
M is never delivered by P1 or P3.
M is delivered by both P1 and P3 in the view {P1,P2,P3}.

SOLUTION-

M is delivered by both P1 and P3 in the view {P1,P3}, M is delivered by P3 in the view {P1,P2,P3} and by P1 in the view {P1,P3}.

Page updated

Google Sites

Report abuse