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?