Homework 5

CS425/ECE428 Fall 2021

This assignment has 5 pages and 2 questions, worth a total of 40 points.  Solutions must be submitted via Gradescope. Solutions must be typed, not hand-written, but you may include hand-drawn diagrams.

You must acknowledge any sources you used to arrive at your solutions, other than the course materials and textbook. If you work in a group on homework assignments, please list the names of your collaborators, but make sure to write your own solution.

1. Consider a distributed transaction with a coordinator and two participants. The coordinator and partic- ipants are each implemented as a 3-node Raft cluster. During the transaction, the client communicates with the leader nodes of each of the clusters. At the end of the transaction, the coordinator performs a two-phase commit by having the leader of the coordinator cluster communicate with the leaders of the participant clusters. See Figure 1.

Assume that the one-way delay between nodes in the same cluster are 2ms and the one-way delay between nodes in different clusters is 5ms.

Assume that the replica leader has been elected and is known to the other participants.  Assume that there are no communication or node failures, unless otherwise specified.

(a)  (2 points) How long does a consensus between cluster members take?   Assume that the leader

immediately sends AppendEntries rather than waiting for the next heartbeat interval, and that the followers immediately reply.

(b)  (2 points) At what point(s) in the two-phase commit protocol do the nodes need to run the Raft

consensus protocol (i.e., commit event)?

(c)  (2 points) Calculate the delay from the start to the finish of the two-phase commit protocol using the specified delay parameters.

(d)  (4 points) At what point in the two-phase commit protocol can the coordinator reply to the client that the transaction is successfully committed?  Calculate the delay from the start of the protocol (at the coordinator) until this point.

(e)  (4 points) At what point in the two-phase commit protocol can each participant release transaction

locks? Calculate the delay from the start of the protocol until this point.

(f)  (2 points) How long would a consensus take if Paxos were used instead of Raft?  Assume that all

nodes act as acceptors; additionally, the leader node also acts as the distinguished proposer and learner.

(g)  (6 points) Now consider using Raft again but with a different delay configuration.  The leaders of

the clusters are placed nearby each other, so that the communication between any two leaders has only a 2ms delay. Each cluster has a local follower, in a different rack, with a delay of 5ms delay. The other follower is in a backup data center, with a 20ms delay.  See Figure 2  Recompute the delays in parts (c), (d), and (e) under this configuration.

Figure 1: Node configuration for Question 1.

Figure 2: Delay configuration for Question 1(g).

2. For each of the below parts, write either a MapReduce job or a chain of MapReduce jobs to solve the question. Write down brief pseudocode (Python-like, preferably) for each of the map and reduce tasks. Also write a brief description that explains the type and meaning of each of the intermediate key-value sets produced by a map task or a non-final reduce task in a chain. Here is an example specification of a chain finding common words:

(a)  (6 points) For contact tracing purposes, find people who have spent 15 minutes (or longer) in the

same location. Input will be of the form:

• Key: location identifier

• Value: a triple, (name of person, entry time, exit time)

Output should be of the form:

• Key: name of person

• Value: list of names of contacts

Note that a contact should only appear in the list once.

(b)  (6 points) Multiply two matrices P = M(1)  and M(2). Input will be of the form:

• Key: triple (i,j,n), where n = 1 or 2, representing the element at row i and column j of matrix

n

• Value: a floating point number x; x = M

The output should be of the form:

• Key: tuple (i,j)

• Value: a floating point number y representing the value at row i column j of the result matrix; y = Pi,j

Recall that Pi,j  = Pk M × M

You may assume that the dimensions of the matrices are known, fixed, and compatible.

(c)  (6 points) For each node in an undirected graph, find its 4-hop neighborhood; i.e., all nodes that are distance of at most 4 from the node. A node is included in its own 4-hop neighborhood.           The input will be of the form:

• Key: node name u

• Value: v such that (u,v) is an edge in the graph