Distributed computing

COMMUNICATION REVIEW

• Basic distributed communication when no shared memory: send/receive.
• Location transparency: broker or name server or tuple space.
• Synchrony and asynchrony are both useful (e.g. real-time vs. informational sensors).
• Other mechanisms are possible

COMMUNICATION BY SHARED MEMORY: beyond locks

• Framework: Herlihy, Maurice. “Impossibility and Universality Results for
• Wait-Free Synchronization,” ACM SIGACT-SIGOPS Symposium
• on Principles of Distributed Computed (PODC), 1988.
• In a system that uses mutual exclusion, it is possible that one process may stop while holding a critical resources and hang the entire system.
• It is of interest to find “wait-free” primitives, in which no process ever waits for another one.
• The primitive operations include test-and-set, fetch-and-add, and fetch-and-cons.
• Herlihy shows that certain operations are strictly more powerfully wait-free than others.

CAN MAKE ANYTHING WAIT-FREE (at a time price)

• Don’t maintain the data structure at all. Instead, just keep a history of the operations.
• enq(x)
• put enq(x) on end of history list (fetch-and-cons)
• end enq(x)
• deq
• put deq on end of history list (fetch-and-cons)
• “replay the array” and figure out what to return
• end deq
• Not extremely practical: the deq takes O(number of deq’s + number of enq’s) time.
• Suggestion is to have certain operations reconstruct the state in an efficient manner.

GENERAL METHOD: COMPARE-AND-SWAP

• Compare-and-swap takes two values: v and v’. If the register’s current value is v, it is replaced by v’, otherwise it is left unchanged. The register’s old value is returned.
• temp := compare-and-swap (register, 0, i)
• if register = 0 then register := i
• else register is unchanged
• Use this primitive to perform atomic updates to a data structure.
• In the following figure, what should the compare-and-swap do?