Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS131 Parallel and Distributed Systems
HW2: CONSISTENCY AND REPLICATION
50 points
Problem 1 - Sequential Consistency (15 points):
Read Section 7.2 in the book on sequential consistency and understand figures 7-6 and 7-7 (pages 365-366). Assume that initially, x, y, and z are 0.
Given the output print strings below for the three processes in Figure 7-6, which print strings indicate sequentially consistent execution and which do not? Explain your answers and generate a possible execution sequence, like those in Figure 7-7, for the output print strings 1) and 2) below that are sequentially consistent:
1) 111100
2) 001100
Problem 2 - Client Centric Consistency Models (20 points):
A client is the only reader and writer of a data item X. Client moves between locations L1 and L2. A server at each location has a replica of the item X which also stores X's local version number (generation). The client reads and writes are always performed locally. A read operation R returns a local version number of the item X. The initial version number of each copy is equal to 0. A write W increments the (local) version number by 1 (shown as W(Xi)).
UP is an update operation performed at the remote copy (initiated by any local W). UP uses the version number of X and stores it with the update. The time line goes from left to right.
For each sub-problem below write the version number next to each R, W, and PW operation and answers the questions.
1) Does the sequence of operations below provide monotonic-read consistency? Explain why it does or does not. If your answer is no, can you add an operation(s) to the sequence so that it does provide monotonic-read consistency (and explain why it does).
Use this definition: the monotonic-read consistency guarantees that if a process accessed a version of x at time t, it will never read an older version of x at a later time.
L1 WS(x1) R(x1) R(x1)
-------------------------------------------------------------------------------------------------------------------------------
L2 UP WS(x1;x2) R(x2)
2) Does the sequence of operations below provide monotonic-write consistency? Explain why it does or does not. If your answer is no, can you add operations to the sequence so that it does provide monotonic-write consistency (and explain why it does).
Use this definition: monotonic-write consistency guarantees that a write is executed on the value of a variable that is the result of all the previous write operations.
L1 WS(x1) WS(x1;x2) R(x2) R
-------------------------------------------------------------------------------------------------------------------------------
L2 UP R(x1) WS(x1,x3)
Problem 3 - Remote write primary- backup protocols (15 points):
A client moves between locations where replicated servers reside. Replica update is performed using a version of the primary backup protocol.
1) Is read-your-writes consistency guaranteed if replica update is performed using the blocking primary-backup protocol (e.g. under the algorithm used to obtain Fig. 7-27 on page 399)? Explain why it does or it does not.