[SOLVED] Cs425/ece428 homework 1 to 6 solutions

1. Consider a distributed system of four processes as shown in Figure 1. The system is synchronous, and
the minimum and maximum network delays (in seconds) between each pair of processes are shown in
the figure as [min, max] against each channel. Assume no messages are lost on the channel, and the
processing time at each process is negligible compared to network delays.
a
b
c
d
[3,11] [4,15]
[6,8]
[3,13]
[2,4]
[12,18]
Figure 1: Figure for question 1.

(a) (3 points) Consider an all-to-all heartbeat protocol, where each process sends a heartbeat to each
other process periodically every T=50s, and each process sets a timeout (computed appropriately
from the known bounds on network delay) to detect failure of other processes.
Suppose that process a crashes. For every other process, calculate how long it will take to detect
a’s failure, in the worst case.

(b) (3 points) Now consider a small extension of the protocol in in Q1(a) – as soon as a process detects
that another process p has crashed via a timeout, it sends a notification to all other processes
about p’s failure. Suppose that process a is the only process that crashes. For every other process,
calculate how long it will take to detect a’s failure, in the worst case.

(c) (2 points) If it is known that at most two processes may crash within a few hours of each other,
how would you redesign the heartbeat protocol described in Q1(a) to minimize bandwidth usage,
without increasing the worst case time taken to detect the failure of a process by at least one alive
process. [Hint: do we really need all-to-all heartbeats?]

(d) (2 points) Assuming the modification in Q1(c), list the minimal set of processes a must send heartbeats to, so as to minimize the worst case time taken to detect failure of a by at least one alive
process.
client s3
s2
s1 RTT = 36ms
RTT = 60ms
RTT = 24ms
Figure 2: Figure for question 2(a).

2. (a) (4 points) Consider Figure 2. The client has an option of using any of the three authoritative
sources of real time (s1, s2, or s3) for external synchronization via Cristian algorithm. The roundtrip times (RTT) between the client and the three servers are shown in the figure. Assume that the
observed RTT to each server remains constant across all synchronization attempts.

(i) Which server should the client choose to achieve the lowest accuracy bound right after synchronization? What is the value of this bound, as estimated by the client right after synchronization?
[1 point]

(ii) If the client’s local clock drifts at the rate of 3µs every second, what is the smallest frequency
(or the longest time-period) at which the client must initiate synchronization with the server
it chose in part (i), so as to maintain an accuracy bound within 90ms at all times. [3 points]
12
39 46
30 32
65 71
52 60
90 93
75 A
B
Figure 3: Figure for question 2(b).

(b) (6 points) Consider the series of message exchanged between two servers A and B as shown in
Figure 3. The local timestamps at the servers when sending and receiving each message are shown
in the figure.

(i) Assume symmetric mode synchronization, where the send and receive timestamps for each
message are recorded by both servers. Given A’s knowledge of the send and receive timestamps
for all six messages, what is the lowest synchronization bound (as estimated by A) with which
A can compute its offset relative to B? What is the corresponding estimated offset value?
[Hint: A may use any pair of messages exchanged between the two servers, and not just two
consecutive messages to compute offsets.] (4 points)

(ii) Now assume that A uses the same series of messages for synchronization via Cristian algorithm:
messages sent from A to B are requests, and messages from B to A are responses carrying the
timestamp when B received the last request. What is the tightest synchronization bound (as
estimated by A) with which A can compute its offset relative to B? (2 points)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
P1
P2
P3
P4
A B C D
E F
G
H
I J K L
M N O P
Figure 4: Timeline for questions 3 and 4.

3. The timeline in Figure 4 shows 16 events (A to P) across four processes. The numbers below indicate
real time.
(a) (2 points) Write down the Lamport timestamp of each event.
(b) (4 points) Write down the vector timestamp of each event.
(c) (4 points) List all events considered concurrent with: (i) A, (ii) F, (iii) K, and (iv) N.

4. (a) (4 points) Consider the timeline and events in Figure 4 again. Suppose that P2 initiates the
Chandy-Lamport snapshot algorithm at (real) time 8. Assuming FIFO channels, write down all
possible consistent cuts that the resulting snapshot could capture. You can describe each cut by its
frontier events.

(b) (6 points) Write all possible states of the incoming channels at P1 and at P3 that the above
snapshot could record. You can denote each message by its send and receive event ids.

P1
P2
A B C D E
F H I J
Figure 1: for question 1
1. (a) (4 points) Consider the timeline of events {A,B,…J} across two processes as shown in Figure 1.
List all possible linearizations for this system that includes each event.

(b) (5 points) What is the total number of consistent global states that can be possibly captured for
the above system? Identify each of them by the frontier events of the corresponding cuts.
(c) (1 point) Provide an example of an unstable global safety property (which results in unstable nonsafety). How can it be made stable? (This is unrelated to 1(a) and 1(b).)
P2
P1
P3
P4
Figure 2: for question 2(a)

2. (a) (6 points) In the execution in Figure 2, processes send messages to each other to implement FIFO
ordered multicast. To simplify the picture, messages sent by each process to itself are not shown,
but assume that such messages are received and delivered instantaneously. For the questions below,
you may use printed or hand-drawn figure with hand-drawn responses, or digitally edit the figure
from the homework PDF.

(i) Identify the messages that are buffered at the processes to ensure FIFO multicast delivery.
(Circle the receive event for the buffered messages to identify those messages.) (3 points)

(ii) For each message buffered as above, determine the earliest instant of time at which the message
may be delivered, while ensuring FIFO multicast. (To identify the instant of time draw an
arrow that begins at the time when the message is received to the time at which the message
may be delivered.) (3 points)
P2
P1
P3
P4
Figure 3: for question 2(b)

(b) (6 points) In the execution in Figure 3, processes send messages to each other to implement causal
multicast. To simplify the picture, messages sent by each process to itself are not shown, but assume
that such messages are received and delivered instantaneously. For the questions below, you may
use printed or hand-drawn figure with hand-drawn responses, or digitally edit the figure from the
homework PDF.

(i) Identify the messages that are buffered at the processes to ensure causally-ordered multicast
delivery (Circle the receive event for the buffered messages to identify those messages.) (3
points)

(ii) For each message buffered as above, determine the earliest instant of time at which the message
may be delivered, while ensuring causally-ordered multicast. (To identify the instant of time
draw an arrow that begins at the time when the message is received to the time at which the
message may be delivered.) (3 points)

3. For each of the statements below, identify whether it is true or false. If it is false, present a counterexample. If it is true, prove why.
(a) (2 points) A total ordered multicast is also causal.

(b) (3 points) If the processes in a system use R-multicast, and each channel follows FIFO order, then
causal ordering is satisfied.
(c) (3 points) We can implement the ISIS algorithm for total ordering on top of (or using) causalordered multicast, to achieve a total causal multicast.

Process ID Time when “enter” is called (since
start of system)
Time spent in critical section after
“enter” returns, before calling “exit”.
P1 250ms 50ms
P2 30ms 50ms
P3 100ms 30ms
P4 20ms 60ms
P5 15ms 20ms
Table 1: Timings for Q4

4. Consider a distributed system of five processes {P1, P2, P3, P4, P5}. Each process needs mutually exclusive access to a critical section. Table 1 lists the time when each process first makes a blocking call to
“enter” the critical section (since the start of the system). It also lists the time each process spends in
the critical section after “enter” succeeds, before calling “exit”.

(a) (5 points) Suppose the system uses the central server algorithm for mutual exclusion, electing P4
as the leader. Assume that message latency at P4 for communicating with the leader (itself) is zero,
i.e. it takes negligible time for P4’s token request to reach the leader upon calling enter, to receive
the token after its request has been granted, and for the token to be released back to the leader
upon calling exit. For all other processes, assume the one-way network latency for communicating
with the leader (P4) is fixed at 10ms, i.e. it takes 10ms each for the token request to reach P4 after
calling “enter”, 10ms for the token to reach the process after the leader has granted the request,
and 10ms for the token to reach the leader after the process has called “exit”. The leader grants
requests in the order in which it receives them. When will each process start executing its critical
section?

(b) (5 points) Now suppose that the system uses ring-based algorithm for mutual exclusion, with the
ring structured as shown below (P1 to P2 to P3 to P4 to P5 to P1).
Figure 4
At time 0ms (when the system starts up), the token is at P1. The network latency for passing
the token from a given process to its ring successor is fixed at 10ms. When will each process start
executing its critical section?

Figure 1 shows three process P1, P2, and P3 (with ids 1, 2, and 3 respectively) implementing the RicartAgrawala (RA) algorithm for mutual exclusion. The lines indicate requests for accessing the critical
section (CS) made by each process – blue, green, and red requests are from P1, P2, and P3 respectively.
Other than the replies to CS requests (not shown in the figure), no other messages are exchanged between
the processes. The timeline indicates real time. Assume that any reply sent for a CS request reaches the
requesting process after exactly one (real) time unit. Further assume that any process that enters the
CS, spends 3 (real) time units in it.

(a) (2 points) What is P1’s state as per the RA algorithm when it receives CS request from P2 – Held,
Wanted, or neither (Free)? How will P1 handle P2’s request upon receiving it – will it immediately
send back a reply or will it queue the request? Why?
(b) (2 points) What is P3’s state as per the RA algorithm when it receives CS request from P2 – Held,
Wanted, or neither (Free)? How will P3 handle P2’s request upon receiving it – will it immediately
send back a reply or will it queue the request? Why?

(c) (2 points) What is P2’s state as per the RA algorithm when it receives CS request from P1 – Held,
Wanted, or neither (Free)? How will P2 handle P1’s request upon receiving it – will it immediately
send back a reply or will it queue the request? Why?

(d) (2 points) What is P3’s state as per the RA algorithm when it receives CS request from P1 – Held,
Wanted, or neither (Free)? How will P3 handle P1’s request upon receiving it – will it immediately
send back a reply or will it queue the request? Why?

(e) (2 points) What is P2’s state as per the RA algorithm when it receives CS request from P3 – Held,
Wanted, or neither (Free)? How will P2 handle P3’s request upon receiving it – will it immediately
send back a reply or will it queue the request? Why?

Consider the following modification of the Bully algorithm: The initiating node (which we assume does
not fail) sends an Election message only to the process with the highest id. If it does not get a response
after a timeout, it then sends an Election message to the process with the second highest id. If after
another timeout it gets no response, it tries the third highest id, and so on. If no higher numbered
processes respond, it sends a Coordinator message to all lower-numbered processes.

(a) (1 point) What should a process do when it receives an Election message in order to minimize
turnaround time?
For the following parts, consider a distributed system of 8 processes {P1, P2, . . . P8}. P8 has the
highest id, followed by P7, then P6, and so on. The system uses the modified Bully algorithm for
leader election (including the solution for 2a). Initially, all 8 processes are alive and P8 is the leader.
Then P8 fails, P3 detects this, and initiates the election. P3 knows that P8 has failed and P7 has
the highest id among the remaining processes. Assume one-way message transmission time is T,
and timeout is set using the knowledge of T.

(b) (1 point) If no other node fails during the election run, how many total messages will be sent by
all processes in this election run?
(c) (1 point) If no other node fails during the election run, how long will it take for the election to
finish?

(d) (1 point) Now assume that right after P3 detects P8’s failure and initiates the election, P7 fails.
How many total messages will be sent by all processes in this election run?
(e) (1 point) For the above scenario (where P7 fails right after P3 initiates election upon detecting P8’s
failure), how long will it take for the election to finish?

(5 points) Consider a system of N process that are arranged in a ring, with each process having a ring
successor and a predecessor, and a communication channel only to its ring successor. Each process Pi has
a unique id i. Further, each process Pi maintains a value xi (which may not be unique across processes).
A process may not know the total number of other processes in the ring.
Each process Pi
is required to set the value of an output variable yi (initialized to undecided) to
minN
j=1(xj ). The safety condition for the problem requires that, at any point in time, the variable
yi at process Pi ∀i ∈ [1, N] is either undecided or minN
j=1(xj ).

A distributed algorithm designed for the above problem works as follows:
• A process Pi
initiates the algorithm by sending (propose, xi) to its ring successor.
• When a process Pj receives (propose, x) from its ring predecessor:
– if x < xj , it forwards (propose, x) to its successor.
– if x > xj , it sends (propose, xj ) to its successor.
– if x = xj , it concludes that x = xj is the minimum value, and sends (decided, x) to its successor.

• When a process Pj receives (decided, x), it sets yj = x and forwards (decided, x) to its successor
(if it had not already done so in the past). Once Pj sets yj , it ignores any subsequently received
decided messages.
Multiple processes may initiate the above algorithm simultaneously. Assume no process fails and the
communication channel delivers all messages correctly and exactly once.
Does the algorithm described above guarantee safety condition for the problem? If yes, prove how. If
not, (i) describe a scenario where safety is violated, and (ii) suggest modifications to the algorithm that
would guarantee the safety condition.

Consider a system of five processes [P1, P2, P3, P4, P5]. Each process Pi proposes a value xi
. Let x1 = 6,
x2 = 5, x3 = 8, x4 = 2, and x5 = 10.
Each process Pk must decide on an output variable yk (initialized to undecided), setting it to one of the
proposed values xi for i ∈ [1, 5]. The safety condition requires that at any point in time, for any two
processes Pj and Pk, either yj or yk is undecided, or yj = yk (in other words, the decided value must be
same across all processes that have decided).

A consensus algorithm is designed for the above problem that works as follows:
• Each process R-multicasts its proposed value at the same time t = 0ms since start of the system
(as per their local clocks).
• As soon as proposed values from all 5 processes are delivered at a process Pj , Pj sets yj to the
minimum of the proposed values it received from the five processes.

• If yj is still undecided at time (t + timeout), Pj computes the minimum of the proposed values it
has received so far and sets yj to that value.
• Once a process Pj decides on yj , it does not update yj ’s value, and ignores future proposals (if any
are received).
Assume that all clocks are perfectly synchronized with zero skew with respect to one-another. The
proposed value xi of a process Pi gets self-delivered immediately at time t = 0ms when Pi begins the
multicast of xi
. A message sent from a process to any other process takes exactly T = 10ms (and this
value is known to all processes). All communication channels are reliable. Processes may fail, but a
failed process never restarts.

Suppose the timeout value for the above algorithm is set to 25ms. Answer the following questions with
respect to local time at the processes’ clock since the start of the system.
(a) (2 points) Assume no process fails in the system. When will each process decide on a value and
what will each of their decided values be?
(b) (2 points) Assume P4 fails right after unicasting x4 to P3 and P5 but just before it could initiate
the unicast of x4 to any of the other processes. When will each of the alive processes decide on a
value and what will each of their decided values be?

(c) (2 points) Assume P4 fails at right after unicasting x4 to P3 but just before it could initiate the
unicast of x4 to any of the other processes. P3 fails right after it has relayed x4 to P5 but just
before it unicasts it to any other process. When will each of the alive processes decide on a value
and what will each of their decided values be?

(d) (2 points) Assume P4 fails right after unicasting x4 to P3 but just before it could initiate the unicast
of x4 to any of the other processes. P3 fails right after it has relayed x4 to P5 but just before it
unicasts it to any other process. P2 fails right before it could unicast x2 to any process. When will
each of the remaining alive processes decide on a value and what will each of their decided values
be?

(e) (2 points) What is the smallest value that the timeout should be set to for ensuring safety in this
system?
(f) (1 point) Answer Q4c assuming that the timeout is updated to the value in Q4e.
(g) (1 point) Answer Q4d assuming that the timeout is updated to the value in Q4e.

Consider a system of five processes that implement the Paxos algorithm for consensus. As shown in
Figure 2, P1 and P2 are proposers. P3, P4, P5 are acceptors. P1 sends a prepare message with proposal
number 2 to processes P4 and P5, receives their replies, and sends an accept message with proposed
value of 10 for proposal #2. P2 concurrently sends a prepare message with proposal #5, with an
initial intention to propose a value of 15 if it receives sufficient replies. Only a subset of responses from
processes P4, and P5 are shown in the figure. Assume no other proposals are initiated.

Answer the
following sub-questions.
0 1 2 3 4 5 6 7 8 9 10 11 12
P1
P2
P3
P4
P5
Prepare #2
13 14 15 16 17 18
Accept #2
Proposed value = 10
Prepare #5
Acceptors Proposers
Figure 2: Figure for question 5(f)
(a) (1 point) Which processes will accept P1’s proposal?
(b) (1 point) Which processes will reply back to P2’s prepare message?
(c) (2 points) Will P2 send out an accept message for its proposal #5? If yes, what will be the
corresponding proposed value?

(d) (2 points) Consider the state of the system at time 10 units. Has the proposed value 10 been
implicitly decided upon at this point? If yes, explain why? If not, construct a possible scenario that
may occur after time 10 units where the system ends up deciding on a different proposed value.
The scenario would involve a temporal sequence of events that may differ from the one shown in the
figure beyond time t=10units but must comply with what is shown until t=10units. An event in
such a sequence may include a prepare/accept request sent by a proposer or received by an acceptor,
or a prepare reply received by the proposer at some time unit.

(e) (1 point) Suppose that P1’s accept request reaches P5 at time 8 units (instead of 14 units). If we
now consider the state of the system at time 10 units, has the proposed value 10 been implicitly
decided upon?

(f) (1 point) Suppose that P1’s accept request reaches P4 at time 15 units (instead of 9 unit) and
reaches P5 at the original time 14 units. Will P2 send out an accept message for its proposal #5?
If yes, what will be the corresponding proposed value?

1. Consider a system of 5 processes {P1, P2, P3, P4, P5} using Raft’s algorithm for leader election. Suppose
P1, the leader for term 1, fails and its four followers receive its last heartbeat at exactly the same time.
Answer the following questions assuming that the election timeout is chosen uniformly at random from
the range [100,500] ms (unless otherwise specified), no processing delay exists, and the one-way delay
for all messages between two processes are as shown in Figure 1. The processes communicate with oneanother only through their direct channels (not via other processes). Each question below is independent
of others.
P2
P3
P5
P4
25ms
10ms
30ms
15ms
5ms
20ms
Figure 1: Figure for question 1

(a) (2 points) Suppose P2 and P3 both set their election timeout to 150 ms and call an election for
term 2. Assume P4 and P5 have their timeout values set to more than 400 ms. Which candidate
(P2 or P3) will each of the four alive processes vote for? Will a leader be elected for term 2? If yes,
which process?

(b) (2 points) Suppose P2 sets its election timeout to 150 ms and calls an election for term 2, and P3
sets its timeout to 170 ms and also calls an election for term 2. Assume P4 and P5 have their
timeout values set to more than 400 ms. Which candidate (P2 or P3) will each of the four alive
processes vote for? Will a leader be elected for term 2? If yes, which process?

(c) (6 points) Suppose P2 sets its election timeout to 150 ms and calls for an election for term 2.
Assume P4 and P5 have their timeout values set to more than 400 ms. What range of timeout
values for P3 (within [100,500] ms) will certainly result in:
(i) P2 winning the election?
(ii) P3 winning the election?
(iii) split vote?

(d) (5 points) Suppose P2 sets its election timeout to 105 ms and calls for an election for term 2. What
is the probability that another process (among P3, P4 and P5) also calls an election for term
2? Round your response upto 4 decimal places. [Hint: this probability can be computed as (1 –
(probability that neither P3 nor P4 nor P5 call for an election for term 2))]

2. Consider a system of three servers {S1, S2, S3} wanting to achieve log consensus using the Raft algorithm.
For each sub-part below, state whether the shown snapshot of log entries at each server could arise from
a valid run of the Raft algorithm. If yes, construct a scenario that would lead to these log entries in
Raft’s execution. If not, explain what makes the entries invalid.

Each number in the shown log entries represents the Raft term that the corresponding event is associated
with.
For the valid log entries, the scenario you construct should include, for each term: which server gets
elected as the leader, which servers vote for it, and which log entries does it append / replicate at each
server.
(a) (3 points)
S1: 1, 1, 1
S2: 1, 2, 2
S3: 1, 1
(b) (3 points)
S1: 1, 1, 1
S2: 1, 1, 2
S3: 1, 1
(c) (3 points)
S1: 1, 1, 1
S2: 1, 1, 2
S3: 1, 1, 3
(d) (3 points)
S1: 1, 1, 1
S2: 1, 2, 2
S3: 1, 2, 3
(e) (3 points)
S1: 1, 1, 3, 3
S2: 1, 2, 2
S3: 1, 1, 3

3. In a system using a blockchain for distributed consensus, in order to add a block to a chain, a participating
node must solve the following puzzle: it must find a value x such that its hash, H(x||seed), is less than
T. The hash function is such that a given value of x can uniformly map to any integer in [0, 2
256 − 1].
Assume T is set to 2226
.

(a) (2 points) What is the probability that a given value of x, randomly chosen by the participating
node, is a winning solution to the puzzle (i.e. H(x||seed) < T)?
(b) (4 points) Assume a participating node adopts the standard strategy for solving the puzzle: it
randomly picks a value x and checks if it is the winning solution. It keeps repeating this step,
until a winning solution is found. Further assume that, for simplicity, the strategy is memoryless
(unoptimized), in the sense that a value of x that has already been checked can get re-checked if
it is randomly selected again. If the node can hash and check 25 values per second, what is the
probability of finding a winning solution within 10 hours? (You may round your answer to five
decimal places.)

(c) (4 points) Assume there are 5000 participating nodes in the system, and that each node starts
solving the puzzle at exactly the same time. Assuming the same rate of computing hashes at each
node (i.e. 25 values per second), what is the probability that at least one node in the system finds
a winning solution in 5 hours? (You may round your answer to four decimal places.)

A bank uses a transaction processing system that complies with ACID properties. Within each transaction, a user can issue one or more of the following operations: (i) DEPOSIT which deposits the specified amount into the specified account, (ii) WITHDRAW which withdraws the specified amount from the specified account, and (iii) BALANCE which immediately displays the current balance in the specified account (also including the effects of operations previously executed within the same transaction).

As a consistency check, if at the end of a transaction, any account has a negative balance, the system aborts that transaction. Consider the five transactions shown below that are executed serially (one after another) in order T1, T2, T3, T4, T5. Answer the following questions, assuming all accounts referred in the transactions have a balance of zero before T1 is executed. T1: DEPOSIT A 50; DEPOSIT B 80; DEPOSIT C 10 T2: WITHDRAW A 70; WITHDRAW B 50; DEPOSIT C 50; BALANCE B T3: WITHDRAW A 40; DEPOSIT B 20; WITHDRAW C 30; BALANCE A T4: WITHDRAW A 20; WITHDRAW B 60; DEPOSIT C 30 T5: BALANCE A; BALANCE B; BALANCE C (a) (5 points) For each transaction, state whether it gets committed or aborted and why. (b) (5 points) What will be the result displayed by each of the BALANCE operations invoked in the transactions?

Consider the following two transactions, each with five operations: T1 T2 1 read A read D 2 read B write C 3 write A read A 4 read D write B 5 write B write E (a) (2 points) Write down all the conflicting pairs of operations across the two transactions. (You can refer to each operation as T n.m; e.g., T2.1 is “read D”, T2.2 is “write C”, and so on). (b) (3 points) Is the following interleaving of operations across T1 and T2 serially equivalent? Explain why or why not. T1 T2 read A read B write A read D write C read A read D write B write B write E (c) (3 points) Write down a non-serial interleaving of operations across T1 and T2, that could result from using strict two-phase locking (with read-write locks), and is equivalent in effect to a serial execution of T1 followed by T2. (d) (3 points) Write down a non-serial interleaving of operations across T1 and T2, that could result from using strict two-phase locking (with read-write locks), and is equivalent in effect to a serial execution of T2 followed by T1.

(e) (4 points) Write down a partial interleaving of the operations across T1 and T2 that is compliant with strict two-phase locking (with read-write locks) and leads to a deadlock. List which lock (and in which mode – read or write) will be waited upon by each transaction in your deadlock. (f) (4 points) Write down an interleaving of the operations across T1 and T2 that is serially equivalent, but impossible with strict two-phase locking. Explain what makes the interleaving impossible with strict two-phase locking. (g) (3 points) Write down a non-serial interleaving of operations across T1 and T2, that could result from using timestamped ordering, and is equivalent in effect to a serial execution of T1 followed by T2. It should not result in any transaction getting aborted. You can use the example format like “write X (X.committedTS = 1, X.RTS = [1,2], X.TW=[2])” to indicate the state maintained by an object (i.e. timestamps for reads and tentative writes) after an operation has been executed. (h) (3 points) Write down a partial non-serial interleaving of the operations across T1 and T2, that could result from using timestamped ordering, and leads to T1 getting aborted (assume timestamp of T2 > timestamp of T1). You can use the example format mentioned in (g).

3. Two-Phase Commit Figure 1 shows a system of three servers processing a distributed transaction. Server 1 is the coordinator and interacts with the client. The network delay between the client and the coordinator, and among the three servers is indicated in the figure. Client Server 1 (coordinator) Server 2 Server 3 50ms 20ms 10ms 5ms Figure 1: Figure for question 3 Any local processing at a server or self-messages take negligible time.

The client issues a COMMIT request for its transaction at time t=0s. Assuming no messages are lost, no server crashes, and no server wishes to abort the transaction. Answer the following questions: (a) (3 points) When will each of the three servers locally commit the transaction? (b) (2 points) What is the earliest time at which the coordinator can safely send a message to the client stating that the transaction will be successfully committed?

In Spanner and similar systems, a combination of two-phase commit (2PC) and Paxos protocols are
used. Both the coordinator and participants in 2PC are implemented as replica groups, using Paxos
to achieve consensus in the group. Each replica group has a leader, so during 2PC, the leader of the
coordinator group communicates with the leaders of the participant groups.

During the execution of 2PC in such a system, there are three points at which a consensus must be
achieved within the nodes in a replica group for a transaction to be committed: (i) at each participant
group to prepare for a commit, (ii) at the coordinator to decide on a commit after receiving a vote from
each participant, and (iii) at each participant again to log the final commit.

Suppose that there is one coordinator and three participants. Each of these has a Paxos replica group
with 5 nodes. The leader of each replica group also acts as the proposer and the distinguished learner for
the Paxos protocol, while the remaining four nodes are acceptors. The leaders of the participant and the
coordinator replica groups send appropriate messages for 2PC to one another once consensus has been
achieved (a decision has been reached) in their respective replica groups. Assume for simplicity that
the coordinator replica group only coordinates the transaction and does not participate in processing
the transaction (so the coordinator leader need not send prepare and commit messages to itself during
2PC).

The communication latency between each pair of nodes within each group is exactly 10ms and the
communication latency between any pair of nodes in two different groups is exactly 25ms. The processing
latency at each node is negligible.

Answer the following questions assuming that there are no failures or lost messages. Further assume
that the leader of each replica group has already been elected / pre-configured. All participant groups
are willing to commit the transaction, and all nodes within each replica group are completely in sync
with one-another.

(a) (6 points) With this combined 2PC / Paxos protocol,
(ai) what is the minimum amount of time it would take for each node in the participant group to
commit a transaction after the leader of the coordinator group receives the “commit” command
from the client? (3 points)

(aii) how many messages are exchanged in the system before all nodes in the participant groups
commit the transaction? (Ignore any message that a process may send to itself). (3 points)
[Hint: Think about the message exchanges required by each protocol (2PC and Paxos). Are there
messages that can be safely sent in parallel to reduce the commit latency?]

(b) (2 points) What is the earliest point at which the coordinator group’s leader can safely tell the
client that the transaction will be successfully committed? Calculate the latency until this point
(from the time since the leader of the coordinator group receives the “commit” command from the
client).

(c) (4 points) Suppose we re-configure the system such that the leader of the coordinator group also
acts as the leader (proposer and distinguished learner) for the participant Paxos groups. Four nodes
in each participant group continue to be acceptors. With this modification, what is the minimum
time it takes for each node in the participant group to commit a transaction after the leader of the
coordinator group receives the “commit” command from the client?

Consider a Chord DHT with a 16-bit address space and the following 100 nodes (hexadecimal values in
parentheses).
1127 (467), 2456 (998), 3786 (eca), 4562 (11d2),
5579 (15cb), 6016 (1780), 6134 (17f6), 6351 (18cf),
7576 (1d98), 8608 (21a0), 9379 (24a3), 9916 (26bc),
10111 (277f), 10335 (285f), 11967 (2ebf), 12158 (2f7e),
12721 (31b1), 14471 (3887), 15900 (3e1c), 16315 (3fbb),
16419 (4023), 17102 (42ce), 17193 (4329), 17460 (4434),
19257 (4b39), 19857 (4d91), 19963 (4dfb), 20012 (4e2c),
20485 (5005), 20721 (50f1), 21422 (53ae), 22029 (560d),
24052 (5df4), 24335 (5f0f), 25642 (642a), 25963 (656b),
26446 (674e), 26842 (68da), 27477 (6b55), 28481 (6f41),
28926 (70fe), 29112 (71b8), 29408 (72e0), 29548 (736c),
30729 (7809), 31428 (7ac4), 32403 (7e93), 33125 (8165),
33875 (8453), 34871 (8837), 35312 (89f0), 35526 (8ac6),
35600 (8b10), 37641 (9309), 37773 (938d), 41351 (a187),
41463 (a1f7), 42016 (a420), 42200 (a4d8), 42513 (a611),
43590 (aa46), 43934 (ab9e), 43967 (abbf), 45357 (b12d),
46305 (b4e1), 46625 (b621), 46684 (b65c), 47477 (b975),
48441 (bd39), 48679 (be27), 49659 (c1fb), 49844 (c2b4),
50069 (c395), 50135 (c3d7), 50197 (c415), 52086 (cb76),
52325 (cc65), 52368 (cc90), 53171 (cfb3), 53684 (d1b4),
54501 (d4e5), 55037 (d6fd), 55263 (d7df), 56343 (dc17),
56739 (dda3), 57289 (dfc9), 58569 (e4c9), 58640 (e510),
59317 (e7b5), 59453 (e83d), 60596 (ecb4), 60598 (ecb6),
62457 (f3f9), 62794 (f54a), 63816 (f948), 64743 (fce7),
64831 (fd3f), 65010 (fdf2), 65363 (ff53), 65423 (ff8f),
For programmatic computations, these numbers have also been made available at:
https://courses.grainger.illinois.edu/ece428/sp2022/assets/hw/hw6-ids.txt

(a) (6 points) List the fingers of node 49844.
(b) (6 points) List the nodes that would be encountered on the lookup of the following keys by node
49844:
(i) 12100
(ii) 29200

(c) (4 points) A power outage takes out a few specific nodes: the ones whose numbers are odd. Assume
that each node maintains only one successor, and no stabilization algorithm has had a chance to
run, so the finger tables have not been updated. When a node in the normal lookup protocol tries
to contact a finger entry that is no longer alive (i.e. its attempt to connect with that node fails),
it switches to the next best option in its finger table that is alive. List the nodes that would be
encountered on the lookup of the key 29200 by node 49844 (include the failed ones).

(a) (6 points) Given four vectors V1, V2, V3 and V4, each having a dimension of N. Use a map-reduce
chain to compute the dot product of (V1 + V2) and (V3 + V4). The input to the map-reduce chain is
in the following key-value format: (k, v), with k = (i, n), where i ∈ [1, N] is the index of the vector
Vn, and v is the corresponding value (Vn[i]). The output of your map-reduce chain must of the
form (-, final result). Assume there are 50 nodes (servers) in your cluster. Your map-reduce chain
must support proper partitioning and load-balancing across these nodes. In particular, assuming
a vector dimension of 10000 ensure that a single node is not required to handle more than ≈800
values at any stage. You can assume that, if allowed by your map-reduce semantics, the underlying
framework perfectly load-balances how different keys are sent to different nodes.

(b) (6 points) Given a directed graph G = (V, E), use a map-reduce chain to compute the set of
vertices that are reachable in exactly 3 hops from each vertex. For example, in a graph with
vertices {a, b, c, d} and the following directed edges, a → b → c → d, the vertex d is reachable in
exactly three hops from vertex a.

The input to the map-reduce chain is in the following key-value format: (k, v) where k is a graph
vertex and v is a list of its out-neighbors; i.e., for each x ∈ v,(k, x) is a directed edge in E. The
output must be key-value pairs (k, v), where k is a graph vertex and v is a list of vertices that are
reachable in exactly three hops from k. The list must be empty if there are no vertices reachable in
exactly three hops from k. Vertices maybe repeated in the three-hop path and need not be distinct.
It is also possible for a vertex to be exactly three hops away from itself, in which case it should be
included in the list.

For your assistance, the first map function for an exemplar map-reduce chain has been provided
below. You may choose to use the same function, or design your own.
function map1((k, v)):
for node in v do
emit ( ( node , ( “in” , k ) ) )
emit ( ( k , ( “out” , node ) ) )
end for
if v is empty then
emit ( (k, (“out”, )))
end if
end function