CSEP 552: Lab 3 design questions

Design draft due Monday, November 2 at 11:59pm on Gradescope.

Here are some questions to help you design your lab 3 protocol, based on the discussion in lecture.

Please choose at least 3 questions below that you think are interesting/challenging, and briefly sketch your ideas or questions about them. Submit your results as a PDF to Gradescope. We will then discuss these issues in class on November 3.

State and leadership

What state does each server keep? Which state is only relevant when the server is leader?
What state does a node keep to determine whether it is the leader?
How do you ensure that two servers never use the same ballot?
What is the difference between a ballot and a slot?
What does a server do when it receives a message in a higher ballot than its own?

Phase 1 (leader election)

When does a server start an election? At what point does it start expecting heartbeats from a leader?
When do you ignore a P1A? When do you act on it? Can you act on one while you are in phase 2?
Is it possible to receive a P1B with a ballot larger than your current ballot? Why or why not?
When do you ignore a P1B? When do you act on it?
What data structure records the P1Bs you have received, and when is it initialized and cleared? How do you count a majority of distinct servers?
Do you merge logs "on the fly" as P1Bs arrive, or keep them until you see a majority? Justify your choice. When does the leader stop merging?
If you merge in place, what can you still say about a value that a majority has accepted? (Hint: merging marks values accepted without a P2A. When may a server mark a slot chosen?)
Once elected, what does the new leader do with the slots it learned about? Why must it re-propose values that were accepted but not known to be chosen?
When do holes appear in the log, and what does the new leader put in them?

Phase 2 (agreement on each slot)

What causes P2As to be sent? How many can be outstanding at once?
How do you handle a P2A with a ballot larger than yours? Smaller than yours?
What do you do with a P2A or P2B for a slot you already know is chosen?
What data structure tracks P2B responses? What is it indexed by?
How do the other servers learn that a slot was chosen?
What happens when a P2A or P2B is dropped? Delivered twice? Delivered after the leader has moved on?
What is the minimum number of messages to choose a command when nothing fails? Does your design use that minimum?

Executing commands

How do you know when to advance slot_out and execute the next command? Why must the log be executed in order?
A client command can be chosen in two slots. What happens when the second one is executed? What does AMOApplication handle for you?
Which servers reply to the client, and when?

Failure detection

How does a follower decide that the leader is dead? How long does it wait, measured in what?
What happens to commands that were in flight when the leader died?
Describe a sequence in which an old leader still believes it is the leader. What stops it from getting a command chosen? How does it eventually learn that it is not the current leader?
Suppose a network partition occurs, leaving a majority of servers on one side and a minority on the other. What happens to each side? What happens to clients?

Log propagation and garbage collection

How does a server who missed a 2A message later learn about what was chosen in that slot?
Does garbage collection happen concurrently with phase 2, or in its own phase?
What data structure does the leader use to track which slots each server has executed? When may a slot be discarded, and by whom?
How does a follower that missed some decisions catch up?
Why can't a server discard a slot as soon as it has executed it locally?

Clients

Which servers does a client send a request to, and what does a server that is not the leader do with it?
When does a client resend, and what does a server do with a request it has already proposed or executed?