Assignment 2
Remember, assignments should be done in groups of size 3
Question 1.
Consider the following five schedules marked 1 to 5 For each schedule, indicate whether it is
final-state serializable and/or view serializable and/or conflict serializable. Give a brief
explanation for each.
Schedule 1:
Schedule 2:
Schedule 3:
Schedule 4:
Schedule 5:
Question 2:
Consider the following five schedules marked 1 to 5. For each
schedule , indicate whether it is recoverable, ACA, and/or strict. Give a brief explanation for
each.
Schedule 1:
Schedule 2:
Schedule 3:
Schedule 4:
Schedule 5:
Question 3:
Which of the schedules below are 1-copy serializable. Explain why.
Schedule 1:
Schedule 2:
Schedule 3:
Question 4:
(reading assignment) Read the following 2 papers by Peter Bailis et. Al.,
1. Quantifying Eventual Consistency with PBS
2. Coordination Avoidance in Database systems.
The first is a CACM article on eventual consistency, and the second is part of his dissertation on
coordination avoidance.
Describe the main ideas of these papers using concrete examples to illustrate the main idea of
the paper. For instance, for the coordination avoidance, explain the authors intuition in defining
correctness beyond serializability. How do they define I-confluence and use it to overcome some
of the challenges faced in supporting serializability. Please make your response short. The key
is to demonstrate in a paragraph or so that you have read and understood the main idea of the
paper.
Question 5:
Create and explain an example schedule that satisfies snapshot isolation, but does not satisfy
CSR.
Question 6:
Prove that all regions in the diagram above represent non-empty sets by providing example
histories H1
-H12
.
ST - Strict
ACA - Avoids cascading abort
RC - Recoverable
