ECE428- Homework 2 Solved

This assignment has 4 questions. The solutions must be typed, and submitted via Blackboard. However, the diagrams can be hand-drawn. You must acknowledge any sources used to arrive at your solutions, other than the course materials and textbook. All homework assignments are expected to be an individual work, so no collaborations are allowed.

Question 1: The only things guaranteed in life are FIFO channels
Consider a system with pair-wise FIFO communication channels. Explain, which of the ordering properties  FIFO, causal, and/or total ordering  will be satisfied in the following four scenarios. For each ordering property, either explain (in one or two sentences) why it will be satisfied, or provide a counter-example, for example, using a diagram. The same counter-example can be used for different scenarios. For B-multicast over FIFO channels, explain whether and why it automatically satisfies causal ordering, or provide a counterexample. 

( a) B-multicast in a situation where there are no process failures;

( b) R-multicast in a situation where there are no process failures;

( c) R-multicast in a situation where process failures may occur;

(d) The sequence number-based FIFO multicast algorithm discussed in class.

                                                                    Questions 2-4 are on the next pages.                                                 

 

(6)         (a) Consider the event diagram above. To assure the FIFO multicast delivery order, which

messages will have to be delayed in a holdback buffer? For these messages, what is the earliest point at which they can be delivered? For simplicity, assume that messages

                    multicast are self-delivered at the sending process instantaneously. 

(6)        (b) Consider the same diagram, but now suppose we wanted to assure a causal multicast  delivery order. Which messages would have to be delayed?

(6)               (c) Still considering the same diagram, assume ISIS total ordering has been used. For every message and process, write down           proposed priority for the

message, and what the final priority for the message will be. Assume that no other messages have been seen, and the proposed priorities all start at 1. It can be also assumed that reply messages with their proposed priorities get delivered after time 17

 Question 3: Trickle-up Multicast

Consider an R-multicast algorithm running in a multicast group of 100 nodes.

(2)         (a) How many copies of a message will be sent at each multicast?           

(b) The R-multicast was modified, so that upon receiving a multicast request, the remulticast is sent only to the higher-numbered processes, as indicated in this Python implementation on the next page:                                            
How many messages will be sent using this modification at each multicast?           

(c) Change the Python code above to guarantee a reliable delivery. Assume that once the
call to unicast() returns, the message will always be delivered to the recipient, even if the sender may later crash. The proposed code modification should send the same number of messages as the original code given in part (b).

Question 4:                                                                    ff in This Critical Section
 

Consider the following table of processes, which lists at what time (since the system starts) the processes request to enter a critical section by calling enter, and how long each process spends in a critical section after it is admitted:

 

Process
Time critical section
Time spent in
 
is requested
critical section
P3
10 ms
20 ms
P2
15 ms
10 ms
P1
20 ms
15 ms
P4
25 ms
30 ms
P5
40 ms
25 ms
        

(5) (a) Suppose that mutual exclusion is managed by a central server algorithm, with P1 being the leader. In this system, assume a one-way delay of 8 ms between any pair of processes. Note that P1

section access take a negligible time (0 ms). List what time each process enters the critical section. You may want to include a diagram for a partial credit.

(5)         (b) Suppose now that the processes are in a token ring, with the following structure:

                                                                                      P1      P4      P2      P3      P5      P1
Assume that at time 0 ms, the token is at P1, and one-way delay between any processes is 8 ms. When would each process enter its critical section?

 

(5)               (c) Assume now that the processes are using Ricart-Agrawala mutual exclusion. Assuming again a one-way delay of 8 ms, when will each process enter the critical section? All

, and no messages other than those used in the Ricart-Agrawala exclusion are sent between any processes.