* The material and content uploaded on this website are for general information and reference purposes only. Please do it by your own first.

Homework 1

Total points 10

Question 1 A ring of processes with the following node ids in clockwise order is running the Ring Election protocol discussed in lecture: 10, 3, 2, 4, 7, 6, 8, 9, 5 (this list does not include the failed leader). The process with id 2 initiates a new leader election run, in order to elect the highest-id process as leader. Assuming no further failures, the total number of messages incurred until the protocol terminates is: 1 point

• 25

• 8

• 26

• 7

SOLUTION-25

Question 2 The Safety condition discussed in the lecture for the Leader Election said that each process’ “elected” (current leader) variable either points to that unique non-faulty process with the highest attribute in the group, or it is null. Someone proposes a slightly different election problem statement, with a modified safety property. Which of the following new safety properties would also be reasonable to define the Leader election problem? 1 point

• Each process’ “elected” variable points to some non-faulty process.

• All processes’ “elected” variables are eventually either null or all of them point to the same non-faulty process p, irrespective of p’s attribute.

• Each process’ “elected” variable points to itself.

• None – this is the only safety condition possible.

SOLUTION-All processes’ “elected” variables are eventually either null or all of them point to the same non-faulty process p, irrespective of p’s attribute.

Question 3 In a Google Chubby system of 6 servers, what is the minimum size of quorum sets? 1 point

• 4

• 1

• 5

• 6

SOLUTION-4

Question 4 Someone designs a Maekawa-style mutual exclusion system for 6 processes with the following voting sets. P1: {P1,P2,P3}; P2: {P2,P3,P4}; P3: {P3,P4,P5}; P4: {P4,P5,P6}; P5:{P5,P6,P1}; P6:{P6,P1,P2}. The resulting algorithm: 1 point

• Is Live but not Safe

• Is neither Safe nor Live

• Is both Live and Safe

• Is Safe but not Live

SOLUTION-Is neither Safe nor Live

Question 5 In a synchronous system of N=12 processes running the Bully algorithm (with attribute = id) for leader election, the coordinator as well as the next (N/3-1), or 3, processes with the next highest ids after the coordinator fail simultaneously (at the same instant of time). Thereafter, no more processes fail. In this version of the Bully algorithm, the old (failed) coordinator is also sent Election messages. Then the exact worst-case (maximum) number of messages that are sent by the Bully algorithm until the leader election algorithm has run completely is: 1 point

SOLUTION- Yet to be uploaded

Question 6 A new open-source system (intended for asynchronous systems) uses a leader election protocol in a group of N processes that is akin to the following (you can assume that no additional processes join, fail from, or leave the group during the election). When a process discovers the leader has failed, it initiates an election. It sends out an “ElectMe!” message to all N-1 processes including itself. Every process has a unique priority (e.g., its id), and the ElectMe! message contains this priority. When a process receives an ElectMe! Message (notice that a process has to receive its own ElectMe! too and vote on it), immediately it does the following: it compares its own priority with that in the message. If its own priority is higher, it multicasts out an ElectMe! message to everyone; otherwise it responds back with a unicast “Vote” message. However, once a process has sent out a Vote message, it cannot send out any more Vote or ElectMe! Messages (i.e., a process can vote at most once). A process also can send out at most one ElectMe! message. Finally, when a process receives at least 2N/3 (i.e., a super-majority of N) Vote messages, it declares itself as a leader.

There may be multiple correct answers below. Given that safety requires only the highest-priority process to be elected and everyone to know about this new leader, this protocol is (MULTIPLE answers): 1 point

• Safe

• Not live

• Not safe

• Not enough information to reason about safety

SOLUTION-Not live, Not safe

Question 7 A group of 5 processes P1 through P5 are running the Ricart and Agrawala’s algorithm for mutual exclusion. Initially the critical section is empty. Then, simultaneously, three processes P2, P4, and P5 initiate requests for the critical section. If the Lamport timestamps of the requests from P2, P4, P5 are respectively 32, 10, 21, then the process that gets access to the critical section first is: 1 point

• P1

• P5

• P3

• P2

• P4

• None – the situation is deadlocked.

SOLUTION-P4

Question 8 A group of 4 processes P1 through P4 are running the Ricart and Agrawala’s algorithm for mutual exclusion. Initially the critical section is empty. Then, simultaneously, two processes P1 and P3 initiate requests for the critical section.If the Lamport timestamps of the requests from P1 and P3 are respectively 110 and 110, then the process that gets access to the critical section first is: 1 point

• P1

• None – the situation is deadlocked.

• P3

• P4

• P2

SOLUTION-P3

Question 9 A group of 5 processes P1 through P5 are running the Ricart and Agrawala’s algorithm for mutual exclusion. Initially the critical section is empty. Then, simultaneously, three processes P2, P4 and P5 initiate requests for the critical section. Assuming all messages are unicast messages, the total number of messages exchanged un till all of P2, P4 and P5 release their critical section is: 1 point

• 30

• 24

• Dependent on the timestamps of the requests

• 8

SOLUTION-24

Question 10 A group of 5 processes P1 through P5 are running the Ricart and Agrawala’s algorithm for mutual exclusion. Initially the critical section is empty. Then, simultaneously, three processes P2, P4, and P5 initiate requests for the critical section. If the Lamport timestamps of the requests from P2, P4, P5 are respectively 21, 21, 21, then the process that gets access to the critical section first is: 1 point

• None – the situation is deadlocked.

• P2

• P4

• P5

SOLUTION-P2

* The material and content uploaded on this website are for general information and reference purposes only. Please do it by your own first.