Distributed computing

INVARIANTS while first TM active

• No server can be in the willing state while any other server (live or failed) is in the committed state
• No server can be in the aborted state while any other server (live or failed) is in the ready-to-commit state

• Some may have aborted

• No one has committed.

• Active

• Willing

• Ready to Commit

• Committed

• No one has aborted. Some may have committed.

CONTRAST WITH TWO-PHASE COMMIT

• Some may have aborted

• Active

• Ready to Commit

• Committed

• Some may have committed.

RECOVERY IN THREE-PHASE COMMIT after first TM fails or slows down too much

• What the newly elected TM does:

• Any
• Ready-to-Commit
• or
• Committed

• Any
• Aborted?

• Send
• ABORT

• Some Dead

• All Willing

• Send
• Committed

• Send
• ABORT;

• All Servers Alive

• Send
• PREPARE; COMMITTED

ROAD MAP: KNOWLEDGE LOGIC AND CONSENSUS

• Knowledge Logic: consensus.
• Fail-stop.
• Network perhaps.

• Commitment
• fail-stop
• site only

EXAMPLE: COORDINATED ATTACK

• Forget about computers. Think about a pair of allied generals A and B.
• They have previously agreed to attack simultaneously or not at all. Now, they can only communicate via carrier pigeon (or some other unreliable medium).
• Suppose general A sends the message to B
• “Attack at Dawn”
• Now, general A won’t attack alone. A doesn’t know whether B has received the message. B understand A’s predicament, so B sends an acknowledgment.
• “Agreed”

• Attack

• Agreed

• A

• A

• B

• B