Paxos question

Suppose you have a replicated state machine running on three servers, using the optimized Paxos algorithm described in the paper. During normal-case operation (no failures or network timeouts), how many network messages must be exchanged between the three replicas for each new command applied to the replicated state machine? Explain what these are.

If it is helpful, you may assume that messages can contain multiple piggybacked requests. But do not assume that the replicas know about more than one state machine command at a time. That would render the question meaningless by allowing replicas to combine multiple commands into a giant compound command that potentially executes arbitrarily many commands in a fixed number of network messages.


Answers need only be a few sentences.

Turn in your answer on paper at the start of class. Be sure both your SUNet ID and your name are on the paper.

SCPD students may submit via SCPD before the start of class.