CS454/654 Assignment 4∗
Fall 2020
Due: 26 November 2020 (5:00pm)
Appeal deadline: one week from return
Question 1 (20%) In Lamport’s logical clocks (where such a clock for an event v is denoted by
C(v)), by considering a chain of zero or more messages connecting events e and e′ and using
induction show that
e→ e′ ⇒ C(e) < C(e′)
Question 2 (20%) Consider two transactions Ti and Tj which both transfer funds from an account
x located at site 1 to an account y located at site 2. As we are interested only in the read
and write operations, the two transactions can be described by the following sequence of
operations
Ti : Ri(x) Wi(x) Ri(y) Wi(y)
Tj : Rj(x) Wj(x) Rj(y) Wj(y)
assuming that each transaction reads x, decrements this value of x it has read, writes the
new value, reads y, increments this value of y it has read, and writes the new value.
Assume that these two transactions are activated almost simultaneously and consider the
following execution at each site:
site 1 site 2
Ri(x)
Wi(x)
Rj(x) Ri(y)
Wj(x) Wi(y)
Rj(y)
Wj(y)
In this representation of execution, the fact that operation Ri(y) appears next to Rj(x) means
that these two operations start at the same time. Therefore, Tj begins reading x immediately
after Ti has written x, although Ti is not yet terminated.
1. Is this distributed execution schedule serializable? If so, explain briefly how you can infer
that it is serializable, and what is the global serialization order. If it is not serializable,
why not?
2. Can this distributed execution schedule be generated by a strict 2-phase locking protocol
(I don’t care if it is a centralized or a distributed 2PL mechanism)? If it can, indicate
the locking/unlocking sequence. If it cannot, explain why not.
∗Remember to typeset your solutions.
1
3. Can this execution be produced by the basic timestamp mechanism? If it can, indicate
what the timestamp values and conditions need to be. If it cannot, explain why not.
Question 3 (20%) Consider a distributed system in which a data item x is replicated at sites
S1, S2 and S3. Design an efficient, valid, majority quorum system to assign votes in this
distributed system for the following scenario:
• your workload is read-dominant, i.e., the vast majority of client requests read data item
x and very few requests write x. Your quorum system design should efficiently support
execution of read operations while guaranteeing majority quorum consensus. Justify your
design for this read-dominant workload. Describe the design of your quorum system in
terms of vote assignments V , read quorum Vr and write quorum Vw.
Consider the same distributed system, i.e., where data item x is replicated at sites S1, S2
and S3. Suppose the quorum system design choice is as follows: 1 vote to every site, Vr = 3,
Vw = 1. Is this a valid quorum system design? Why or why not? Justify your answer.
Provide a clear description of your justification and example(s) to illustrate your answer and
its justification.
Question 4 (20%) Describe advantages and disadvantages of using the callback promise mech-
anism for maintaining client-side cached file data over the freshness interval-based polling
mechanism.
Question 5 (20%) Consider the following scenarios in a distributed system that uses 2PC among
the coordinator component and participant components:
1. the coordinator fails after it sends the prepare message to participants and before it
receives the prepared message from all participants.
2. a participant fails after sending the prepared message to the coordinator and before it
receives the global-commit or global-abort message from the coordinator.
Assume that:
• the coordinator always processes at least a portion of a global transaction.
• messages are never lost, and that if either the coordinator or a participant waits for
messages for a period of time longer than a set timeout value, it will conclude that the
component from which it is waiting for a message has failed.
• in each of the scenarios above, the timeout value is exceeded before the failed component
recovers.
For the two failure scenarios (1) and (2) above, describe the action(s) of the component upon
recovery, justifying the action(s) you describe.
2

欢迎咨询51作业君