Family name
Student ID
First name
Signature of candidate
University of Toronto Electrical and Computer Engineering
PA 1 25
2 14 3 12 4 14
5 25- 6 16 7 32 8- 9-
10 – 11 –
12
L 138
Completed by examiner:
Left exam room Early submission Special notes:
from…………. at…………..
until ………….
NI Final Exam
Course: ECE 419 Distributed Systems
Date: April 15th, 2019
–
0
Name: Student number:
0 1: Logical Clocking
4 25 points
Figure 1 shows a series of transmission and receive events between four processes. Most transmission events in the diagram are unicast (i.e. single sender, single receiver), though two of the events (indicated with a dot) are multicast (one sender, many receivers).
ro]
C
111
Figure 1: Event Diagram
a) Complete Table 1, indicating the Lamport Clock value for all events in the diagram. Events are identified using their process ID and order within the process. A(7) would be the seventh event that occurs on Process A; B(1) would be the first event occurring on B. Two examples are provided. (Note:
not every cell corresponds to an existing event)
(8 points)
12345678 A1
–
B2
C
D
Table 1: Lamport Clock values for Figure 1
2
Name: Student number:
b) Complete Table 2 for the events in Figure 1 using the Vector Clock algorithm instead.
1234 Al000
B1100
4
(8 points)
C D
A
B C D
5678
Table 2: Vector Clock values for Figure 1
Prove and list using only Lamport Clocks three pairs of events that are concurrent. Use A(11) 11 B(12) to indicate that the 11th event on A is concurrent with the 12th event on B. (3 points)
Prove and list using Vector Clocks three pairs of events that have a happened-before relationship. Use the A(l1) -* B(12) to indicate that the 11thevent on A happened before the 12th event on B. (3 points)
For the events listed in (d), can you determine a happened-before relationship using only Lamport Clock values? Why or why not? Provide an example if possible. (3 points)
3
Name: Student number:
0 2: Physical Clocks
4 14 points
A set of processes synchronize their clocks according to the Berkeley algorithm as illustrated in Figure 2. The threshold value for acceptable deviation is y = 4000ms. For a given round of the algorithm, the times of all individual processes have been collected by the Master (cf. Figure 3).
I P2 (Slave)
– – – – –T I I
P1 P2 P3 P4
I (Master)
Figure 2: Synchronization setup
P1
I I p (Slave) J (Slave)
PROCESS
PROCESS TIME #1
(hh:mm:ss:fff)
08:34:48:000 08:34:42:000 08:34:46:500 08:34:45:000
PROCESS TIME #2
(hh:mm:ss:fff)
08:35:27:000 08:35:23:000 08:35:21:500 08:35:19:500
What time does the Master calculate for synchronization (i.e., the new global time) for Time #1?
(2 points)
What values does the Master calculate and send to individual processes for Time #1?
PROCESS VALUE P1
P2 P3 P4
c) What values does the Master calculate and send to individual processes for Time #2?
PROCESS VALUE P1
P2 P3 P4
(6 points)
Figure 3: Process times gathered at Master
(6 points)
Name: Student number:
0 3: Consistency Models
4 12 points
Consider the execution sequence depicted in Figure 4) for a system with three processes (P1, P2, and P3) and two memory locations (x and y). The execution sequence represents the order in which each process performed its own operations and the results of any read operations.
P1 w(x)1 P2 r(x)1 P3 r(y)3
t
10
r(x)2 w(y)1 w(y)3 r(y)1 w(x)2 r(x)1
Figure 4: Execution sequences
Is this execution sequence FIFO consistent? If it is, find valid execution sequences for each process to prove it. If it is not, give an explanation. (4 points)
Is this execution sequence causally consistent? If it is, find valid execution sequences for each process
to prove it. If it is not, give an explanation.
(4 points)
Is this execution sequence sequentially consistent? process to prove it. If it is not, give an explanation.
If it is, find valid execution sequences for each (4 points)
5
Name: Student number:
46
Q 4: Peer-to-peer systems
14 points
a) Let C be the Chord ring given in Figure 5. The system contains 12 peers, each of which maps to a node N E C via a uniform hash function with identifier length m = 6. Key k is assigned to the first peer whose identifier is equal to or follows k on C. For instance, in Figure 5, key K35is assigned to node N39.
N4
N42
N:
10
N15
120
IJ34
N62
N32
Figure 5: Chord ring C
(1) In Chord every peer has a finger table. Complete the finger tables of peers at node N15and N34- (6 points)
Table 3: N15’s finger table Table 4: N34’s finger table Peer ID Successor Peer ID Successor
Name: Student number:
4
(2) Execute a lookup for key K16from peer N34. Complete the graph in Figure 6. Vertices correspond to peer nodes Ni E C, edges represent forwarding requests. Use only as many vertices of Figure 6 as you need (there are too many). (2 points)
Figure 6: Lookup graph for key K16.
b) Given the virtual 2-d coordinate spaces in Figure 7, determine for each one of them whether it is a correctly partitioned content-addressable network (CAN) network or not. Provide a short justification for your answer (one line, no more). (6 points)
Figure 7: Virtual coordinate spaces
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
………………………………………………………………………………
fA
Name: Student number:
0 5: Mutual Exclusion
4 25 points
Suppose we adapt Lamport’s mutual exclusion algorithm in order to tolerate message loss. In ,Lamport’s algorithm, process P, enters the critical section if the following two conditions are met:
Upon a request, P1receives replies with timestamps larger than (ts1, i) from all other processes (tsi is the Lamport clock timestamp of the request message sent by P1and i is Pi’s unique process identifier.)
Pi’s request is at the top of its local priority queue Q1.
Suppose we change the first condition – instead of receiving reply messages from all other processes, P1only needs to receive reply messages from a majority of all other processes; i.e., if the total number of processes is 2N, then besides P, there are 2N- 1 other processes, and P1only needs to collect replies from N of these processes.
The full algorithm is as follows:
Request Phase
For any process P1who wants to enter the critical section, it broadcasts request message REQUEST(ts, i), and places REQUEST(ts, i) in its local queue Q1.
Receive Phase
For any process Pk who receives a request message (ts1, i) from P, it
puts message (ts, i) into its local queue Qk and sends a reply message REPLY(tsk, k) back to P1.
Execution Phase
Any requester P1who broadcasts a request REQUEST(ts,, i) checks the following conditions:
–
whether it has collected replies from a majority of the processes Pk: REPLY(tsk, k) and
whether REQUEST(ts,,i) is at the top of its local queue Q1. If these conditions are met, P, enters the critical section.
Release Phase
For any requester P1who exits the critical section, it removes REQUEST(ts, i) from its local queue Q1, broadcasts RELEASE(i) to all other processes.
For any other processes Pk who receives a RELEASE(i) message, it 1. removes REQUEST(ts1, i) from its local queue Qk.
–
Name: Student number:
(1) Suppose messages may be lost in the network. Does this algorithm satisfy liveness? Please explain
your answer. (5 points)
(2) Suppose messages may be lost in the network. Give a counterexample to show that it does not satisfy safety. (5 points)
(3) Suppose messages may be lost in the network. Does this algorithm satisfy fairness? Discuss this property from both fairness perspectives (determine in each case whether fairness is met or not (yes or no)):
Ordering: (5 points)
No starvation: (5 points)
(4) Suppose messages may be lost in the network. If we change the algorithm to use vector clock timestamps instead of Lamport clock timestamps, would the algorithm satisfy fairness? Justify your answer. (5 points)
4
Name: Student number:
Q6:Paxos
46 16 points
(1) In this question, we run Paxos in a synchronous distributed system model, under strong (unrealistic) assumptions. We assume that each message takes precisely 0.5 milliseconds to reach its destination and that the processing times can be ignored. As shown in Figure 8, we assume that there are three acceptors (A, B, C), two proposers (D, E) and one learner (F). Proposer D proposes “write” with Proposal Number 1, and it sends its prepare message at time 0. Then, 0.75 milliseconds later, Proposer E, proposes “read” with Proposal Number 2. Furthermore, we assume there are no failures and that no message gets lost-or is duplicated. Unlike in the Paxos protocol studied in lecture, here, we assume that a proposer stops working if its own proposal is unsuccessful. Also, in this system, the quorum set size for acceptors is three and optional NACK messages are required.
Under the stated assumptions and specified behavior, complete the diagram in Figure 8, showing all messages exchanged and showing exact message labels for all message phases (e.g., the prepare (1) message label in the initial prepare phase that is sent with all prepare messages from Proposer D to acceptors A, B, C) during the execution of the Paxos algorithm. Finally, determine which value will be chosen in the end.
tt9(O
D–
A
B
C
E ————
F
The chosen value is:
%
.
:i
.
—- —— —— ———-” ———————-.——–
” .
0.5 0.75 1.0 1.25 1.5 1.75 2.0 2.25 2.5 2.75 3.0 Figure 8: Incomplete Paxos message diagram
10
—
(10 points)
Name: Student number:
4
(2) Figure 9 shows the execution of Basic Paxos under its standard distributed system model and its standard failure model assumptions with a quorum set size of two and optional NACK messages, with two proposers (D, E), three acceptors (A, B, C) and one learner (F). The diagram in Figure 9 contains exactly four errors which are not allowed in Basic Paxos. Identify these errors in the space below.
(6 points) ……………………………………………………………………………..
……………………………………………………………………………..
……………………………………………………………………………..
……………………………………………………………………………..
Figure 9: Incorrect Paxos message diagram
11
Name: Student number:
0 7: Erasure Codes
4 32 points
For the text string “DS is fun” (excluding quotes) with corresponding simplified character representation – 13 2 4 3 2 5 6 7 – a (3,2)-erasure code based on Reed-Solomon coding is to be designed. All calculations should be based on conventional decimal arithmetic. Hint: Carefully consider which calculations are indeed necessary.
For an (n,m)-erasure code, what is the meaning of n and m, briefly explain. (2 points) n. ……………………………………………………………………………….
m: ………………………………………………………………………………
Against the erasure of how many databytes does a (3,2)-erasure code protect us? (1 points)
(c) Against the erasure of how many paritybytes does a (3,2)-erasure code protect us? (1 points)
Professor Reed is divided about what encoding matrix is to be used for this (3,2)-code and suggests the
following four Options.
r , . . 1 (8 points) IUIUU
010
001 10 9 12 18 0 1
10 010
01 001
4 6
34 32 346
.
i
6 8 12
(1) (2) (3) (4)
L 41 31 121
For each matrix, does it constitute a correct encoding matrix for our (3,2)-code, yes or no? Briefly explain your answer (one line or less).
Answer:
Answer:
Answer:
Answer:
Explanation. ……………………………………………………
Explanation. ……………………………………………………
Explanation: ……………………………………………………
Explanation: ……………………………………………………
12
Name: Student number:
–
I , ,
(e) Professor Solomon recommends the use of the following encoding matrix fragment for the (3,2)-code:
4 6 12 346
Given the above text to be protected, (1) provide the original data matrix, (2) provide the encoding matrix, (3) determine the parity matrix, and (4) provide the parity data. (10 points)
Original data matrix (D):
Encoding matrix (E):
Determine the parity matrix (P). Hint: The parity matrix results through calculations from the encoding matrix and the original data matrix (briefly explain your steps on the left):
Parity data (you may simply refer to the correct parts of the above parity matrix or extract the information into the space below):
13
Name: Student number:
4
(0 Due to unforeseen storage medium failures, the first and second junk of our input string was erased (i.e., “DS “and “is ” ; including the trailing spaces.) Based on the information above, give the data reconstruction matrix for this scenario. Briefly explain how you obtain the data reconstruction matrix (i.e., from which of the above matrices). (1 points)
In order to recover the lost data, what is the required next step? Simply explain in abstract terms, – one line or less and no calculations! (1 points)
In a Eureka moment, Professor Solomon had scribbled down a bunch of matrices on a napkin, next to the encoding matrix from above. We were able to recover a partial matrix from this writing where missing items are denoted by ” ? ” . Assuming Professor Solomon already calculated the correct information for the various data loss scenarios, and provided we found the correct partial matrix that corresponds to our data loss scenario for the given text, (1) determine the missing elements in the matrix below and (2) verify that the matrix is correct. Explain all your steps for partial marks. Hint: Use your result from above Part (f). (6 points)
Partial matrix recovered from Professor Solomon’s writings (determine the missing entries):
6 ¡ª2 3 ¡ª6 1.5 ¡ª2 ???
Explain how the lost data can be recovered (no need for calculations). (2 points)
14
Name: Student number:
4
This page left blank for extra work
Please be specific as to the question you’re answering
15
Name: Student number:
4
This page left blank for extra work
Please be specific as to the question you’re answering
16