Distributed computing

PERSISTENT DATA STRUCTURES AND WAIT-FREEDOM

• One node added, one node removed. To establish change, change the current pointer.
• Old tree would still be available.
• Important point: If process doing change should abort, then no other process is affected.

• current

• Original Data Structure

• current

Logical Level is Nice, but…

• We have talked about some programming constructs one can use above a communications infrastructure.
• Understanding that infrastructure will be necessary to understand performance and fault tolerance considerations.
• Our discussion of that will come from Joe Conron’s lecture notes datacomessence.ppt

ORDER-PRESERVING BROADCAST PROTOCOLS ON BROADCAST NET

• Proposes a virtual distributed system that implements ordered atomic broadcast and failure detection.
• Shows that this makes designing the rest of system easier.
• Shows that implementing these two primitives isn’t so hard.
• Paradigm: find an appropriate intermediate level of abstraction that can be implemented and that facilitates the higher functions.
• Build Facilities that use Broadcast Network.
• Implement Atomic Broadcast Network.

• Framework: Chang, Jo-Mei. “Simplifying Distributed Database Systems Design by Using a Broadcast Network,” ACM SIGMOD, June 1984.

RATIONALE

• Use property of current networks, which are naturally broadcast, although not so reliable.
• Common tasks of distributed systems: Send same information to many sites participating in a transaction (update all copies); reach agreement (e.g. transaction commitment).

DESCRIPTION OF ABSTRACT MACHINE

• Services and assurances it provides:
• Atomic broadcast: failure atomicity. If a message is received by an application program at one site, it will be received at all operational sites.
• System-wide clock and all messages are timestamped in sequence. This is the effective message order.
• Assumptions: Failures are fail-stop, not malicious. So, for example token site will not lie about messages or sequence numbers.
• Network failures require extra memory.