#1 posted on Jan 20 2011, 18:03 in collection CMU 15-712: Advanced OS & Distributed Systems (Spring 2011)
Let's say a process is a sequence of instructions. Processes impact themselves through execution and impact one another through messages. In this setting, we'd like to use time to (1) coordinate the processes (e.g. "only one process can use this resource at a time") and (2) interact with the external world (e.g. "deliver this package by 11:00 GMT"). Unfortunately, applying the causal definition of time (the future can't impact the past) to processes yields a relation which imposes total order among the instructions in a single process (cool), but doesn't impose total order among the instructions in multiple processes (not cool). In light of this challenge, we'll use COUNTERS to get (1) and CLOCKS to get (2).

COUNTERS: with some internal bookkeeping and metadata in the messages, processes can reconstitute a total order, and system architects can thereby reconstitute their sanity.
1. Equip each process with a counter which increments after each instruction.
2. Include a timestamp with each outgoing message.
3. Advance the counter ahead of the timestamp of each incoming message (if the clock is behind the timestamp).
Now use the counter values as a total ordering, breaking ties arbitrarily.

CLOCKS: a total order can't prevent anomalous behavior with respect to the external world. For that, the processes need to synchronize. After obtaining/assuming a lower bound $u$ on the shortest communication time between processes:
1. Equip the processes with clocks which smoothly tick at similar rates.
2. Follow the counter protocol, except the clock should be advanced $u$ ahead of the timestamp.
Lamport shows how well the clocks are synchronized in terms of $u$, the independent drift rates, and the diameter of the message graph.

This paper is a classic.