Distributed computing

CHANG SCHEME

• Tools: Token-passing scheme + positive acknowledgments + negative acknowledgements.

• Ack with counter

• Sender

• Token Site

• Broadcast

• Increment counter Commit message

BEAUTY OF NEGATIVE ACKNOWLEDGMENT

• How does a site discover that it hasn’t received a message?
• Non-token site knows that it has missed a message if there is a gap in the counter values that it has received. In that case, it requests that information from the token site (negative ack).
• Overhead: one positive acknowledgment per broadcast message vs. one acknowledgment per site per message in naïve implementation.

TOKEN TRANSFER

• Token transfer is a standard message. The target site must acknowledge. To become a token site, the target site must guarantee that it has received all messages since the last time it was a token site.
• Detect failure at a non-token site, when it fails to accept token responsibility.

• Here is token

• I can take it

• token
• site

• token

REVISIT ASSUMPTIONS

• Sites do not lie about their state (i.e., no malicious sites; could use authentication).
• Sites tell you when they fail (e.g. through redundant circuitry) or by not responding.
• If there is a network partition, then no negative ack would occur, so must keep message m around until everyone has acquired the token after m was sent.

LAMPORT Times, Clocks paper

• What is the proper notion of time for Distributed Systems?
• Time Is a Partial Order
• The Arrow Relation
• Logical Clocks
• Ordering All Events using a tie-breaking Clock
• Achieving Mutual Exclusion Using This Clock
• Correctness
• Criticisms
• Need for Physical Clocks
• Conditions for Physical Clocks
• Assumptions About Clocks and Messages
• How Do We Achieve Physical Clock Goal?