Distributed computing

ROAD MAP: TIME ACCORDING TO LAMPORT

• How to model time
• in distributed systems

• Languages & Constructs for Synchronization

TIME

• Assuming there are no failures, the most important difference between distributed systems and centralized ones is that distributed systems have no natural notion of global time.
• Lamport was the first who built a theory around accepting this fact.
• That theory has proven to be surprisingly useful, since the partial order that Lamport proposed is enough for many applications.

WHAT LAMPORT DOES

• Paper (reference on next slide) describes a message-based criterion for obtaining a time partial order.
• 2. It converts this time partial order to a total order.
• 3. It uses the total order to solve the mutual exclusion problem.
• 4. It describes a stronger notion of physical time and gives an algorithm that sometimes achieves it (depending on quality of local clocks and message delivery).

NOTIONS OF TIME IN DISTRIBUTED SYSTEMS

• Distributed system consists of a collection of distinct processes, which are spatially separated. (Each process has a unique identifier.)
• Communicate by exchanging messages.
• Messages arrive in the order they are sent. (Could be achieved by hand-shaking protocol.)
• Consequence: Time is partial order in distributed systems. Some events may not be ordered.

• Lamport, L. “Times, Clocks, and the Ordering of Events in a Distributed System,” Communications of the ACM, vol. 21, no. 7 (July 1978).

THE ARROW (partial order) RELATION

• We say A happens before B or A  B, if:
• 1. A and B are in the same process and A happens before B in that process (Assume processes are sequential.)
• 2. A is the sending of a message at one process and B is the receiving of that message at another process, then A  B.
• 3. There is a C such that A  C and C  B.
• In the jargon,  is an irreflexive partial ordering.