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?