CS454/654 Take-home Test∗
Fall 2020
Due: 4 December 2020 (10:00pm)
The University of Waterloo subscribes to the strictest interpretation of academic integrity. Fac-
ulty members and students bear joint responsibility in assuring that cheating on assignments, tests
and exams is not tolerated. This Take-home Test is protected by copyright. Reproduction or dis-
semination of this document or the contents or format of this document in any manner whatsoever
(e.g., sharing the content with other students), without the express permission of the instructor, is
prohibited. In having access to this Test:
• you will keep the content of this Test confidential.
• in the writing of this Test, you will not access any resource other than the CS 454/654 course
material that includes slides, notes, videos, and the two textbooks referenced in the course.
• you have not received any unauthorized assistance in preparing for or writing this Test.
Question 1 (10 points) Consider a distributed system in which a data item x is replicated at
sites S1, S2 and S3. Design a valid, majority, quorum system to assign votes in this distributed
system for a read/write workload in which half of all client requests read data item x and
the other half write x. Your quorum system design should efficiently support execution of
read and write operations while guaranteeing majority quorum consensus. Justify your design
for this read/write workload. Describe the design of your quorum system in terms of vote
assignments V , read quorum Vr and write quorum Vw.
Question 2 (10 points) Suppose that there is only one coordinator site and one participant site
in a distributed system that uses 2PC. If every distributed transaction in this system executes
writes only at the coordinator site and executes only reads at the participant site, is it possible
to optimize the 2PC protocol to save on message(s) while preserving the properties of the
(original) 2PC protocol? Justify and describe your answer.
You can generally assume that:
• 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.
• the timeout value is exceeded before a failed component recovers.
Question 3 (15 points) Describe an algorithm for guaranteeing file session semantics under con-
current writers (in which multiple clients may write in parallel to the same portions of a file)
for the WatDFS upload-download model with freshness interval-based polling (from Assign-
ment 3).
∗Remember to typeset your solutions.
1

欢迎咨询51作业君