CSE 552 Spring 2019 Problem Set 1
Due Friday, April 19 at 5pm
Problem 1
Paxos allows multiple ballots to run (possibly overlapping), and allows
multiple ballots to become chosen. Why is it important to allow
multiple proposals to be chosen with the same value?
Problem 2
List three potential advantages and two potential disadvantages of increasing
the number of replicas in an Egalitarian Paxos (EPaxos) deployment.
Problem 3
IronFleet blends two verification styles, TLA state machine refinement
and Hoare logic. Restrict your attention to safety properties.
What kinds of challenge is the refinement layer intended to address?
What kinds of challenge is the Hoare logic layer intended to address?
Problem 4
In chain replication, suppose the tail replica fails. During the
interval after the tail has failed and before the chain gets
reconfigured, what results do clients see? Is this consistent with
serializability?
Problem 5
In PBFT, before performing garbage collection on a slot $n,$ a replica
must obtain $2f+1$ matching checkpoint messages (including perhaps its own) for
slot $n$ or beyond. What could go wrong if it only waited for $f+1$ matching
checkpoint messages?