Distributed computing

CONDITIONS FOR PHYSICAL CLOCKS

• Suppose u is the smallest time through internal or external means that one process can be informed of an event occurring at another process. That is, u is the smallest transmission time.
• (Distance/speed of light?)
• Suppose we have a global time t (all processes are in same frame of reference) that is unknown to any process.
• Goal for physical clocks: Ci(t + u) > Cj(t) for any i, j.
• This ensures that if A happens before B, then the clock time for B will be after the clock time for A.

ASSUMPTIONS ABOUT CLOCKS AND MESSAGES

• Clock drift. In one unit of global time, Ci will advance between 1-k and 1+k time units. (k << 1)
• A message can be sent in some minimum time v with a possible additional delay of at most e.

HOW DO WE ACHIEVE PHYSICAL CLOCK GOAL?

• Can’t always do so, e.g., can’t synchronize quartz watches using the U.S. post office.
• Basic algorithm: Periodically (to be determined), each process sends out timestamped messages.
• Upon receiving a message from Pi timestamped Ti, process Pj sets its own timestamp to max(Ti + v, Tj).

WHAT ALGORITHM ACCOMPLISHES

• Simplifying to the essence of the idea, suppose there are two processes i and j and i sends a message that arrives at global time t.
• After possibly resetting its timestamp, process j ensures that
• Cj(t) ≥ Ci(t) + v – (e+v)x(1+k)
• That is, since i sent its message at local time Ti, i’s clock may have advanced (e+v)x(1+k) time units to Ti+(e+v)x(1+k) time. At the least Cj(t) ≥ Ti+v.
• How good can synchronization be, given e, v, k?

ROAD MAP: SOME FUNDAMENTAL PROTOCOLS

• Languages & Constructs for Synchronization

• Time in distributed systems

• Protocols built on asynchronous networks (achieve global state)

PROTOCOLS

• Asynchrony and distributed centers of processing give rise to various problems:
• Find a spanning tree n a network.
• When does a collection of processes terminate?
• Find a consistent state of a distributed system, i.e., some analogue to a photographic “snapshot”.
• Establish a synchronization point. This will allow us to implement parallel algorithms that work in rounds on a distributed asynchronous system.
• Find the shortest path from a given node s to every other node in the network.