Distributed computing

SKEEN’S ORDERED BROADCAST PROTOCOL (cont.)

• Take max. (e.g., 29)

• Initiator
• Send message m

• Receivers

• Proposed timestamp (e.g., 17), based on local Lamport time

• Final timestamp

• Forget proposed timestamp for m.
• Wait until final timestamp for m is minimum of
• proposed or final timestamps.
• Accept m.
• Forget timestamp for m.

CORRECTNESS

• Theorem: m and m’ will be accepted in same order at all common sites.
• Proof steps:
• Every two final timestamps will be different.
• If TS(m)

Is the protocol overly complex?

• Find an example showing that changing the Skeen protocol in any one of the following ways would yield an incorrect protocol.
• The timestamps at different sites could be the same.
• The initiator chooses the minimum (instead of the maximum) proposed timestamp as the final timestamp.
• Sites accept messages as soon as they become deliverable.

ROAD MAP: COMMIT PROTOCOLS

• All-or-nothing commitment of transactions.
• Avoid partial updates.
• Fail-stop failures.

• Recovery of data following fail-stop failures

THE NEED

• Scenario: Transaction manager (representing user) communicates with several database servers.
• Main problem is to make the commit atomic (i.e., either all sites commit the transaction or none do).

NAÏVE (INCORRECT) ALGORITHM

• RESULT: INCONSISTENT STATE

• TM

• Servers

• TM

• Commit

• Done

• INVENTORY INCREMENTED

• CASH NOT DECREMENTED

• Commit

• No!