Distributed computing

Problems with FIFO

• Network news application, where users distribute their articles with FIFO Broadcast. User A broadcasts an article.
• User B, at a different site, accepts that article and broadcasts a response that can only be understood by a user who has already seen the original article.
• User C accepts B’s response before accepting the original article from A and so misinterprets the response.

Causal Broadcast

• Causal broadcast: If the broadcast of m causally precedes the broadcast of m’ (in the sense of Lamport ordering), then m must be accepted everywhere before m’
• Does this solve the previous problem?

Problems with Causal Broadcast

• Consider a replicated database with two copies of a bank account x residing in different sites. Initially, x has a value of 100. A user deposits 20, triggering a broadcast of “add 20 to x” to the two copies of x.
• At the same time, at a different site, the bank initiates a broadcast of “add 10 percent interest to x”. Not causally related, so Causal Broadcast allows the two copies of x to accept these update messages in different orders.

THE NEED FOR ORDERED BROADCAST

• In the causal protocol, it is possible for two updaters at different sites to send their messages in a different order to the various processes, so the sequence won’t be consistent.

• U1

• U2

• A

• U1

• U2

• A

• B

• m

• m’

• m’

• m

• B

Total Order (Atomic Broadcast)

• If correct processes p and q both accept messages m and m’, the p accepts m before m’ if and only if q accepts m before m’

DALE SKEEN’S ORDERED BROADCAST PROTOCOL

• Idea is to assign each broadcast a global logical timestamp and deliver messages in the order of timestamps.
• As before, initiator send message m to all receiving processes (maybe not all)
• Receiver process marks m as undelivered (keeps m in buffer) and sends a proposed timestamp that is larger than any timestamp that the site has already proposed or received
• Timestamps are made unique by attaching the site’s identifier as low-order bits. Time advances at each process based on Lamport clocks.