What exactly is a distributed system?
- A distributed system consists of a collection of distinct processes which are spatially separated, and which communicate with one another by exchanging messages.
- A system is distributed if the message transmission delay is not negligible compared to the time between events in a single process.
In a distributed system, it is sometimes impossible to say that one of two events occurred first. The relation “happened before” is therefore only a partial ordering of the events in the system.
The algorithm of Lamport Timestamps can be captured in a few rules:
- All the process counters start with value 0.
- A process increments its counter for each event (internal event, message sending, message receiving) in that process.
- When a process sends a message, it includes its (incremented) counter value with the message.
- On receiving a message, the counter of the recipient is updated to the greater of its current counter and the timestamp in the received message, and then incremented by one.
One of the shortcomings of Lamport Timestamps is rooted in the fact that they only partially order events (as opposed to total order). Partial order indicates that not every pair of events need be comparable. If two events can’t be compared, we call these events concurrent. The problem with Lamport Timestamps is that they can’t tell if events are concurrent or not. This problem is solved by Vector Clocks.
Difference between partial and total order
Total Order
Let’s start by explaining a total order. A total order can be thought of intuitively as an order (in the non-technical sense) on the set of things we’re considering – this one comes first, then this one, and so on. This intuition breaks down a bit when we consider infinite collections of things, but it’ll do. For example, the letters have a total order on them: A comes first, then B, then C…
The key properties this order must have are:
Transitivity – if x comes before y, and y comes before z, then x comes before z.
Totality – either x comes before y, or y comes before x.
Asymmetry – if x comes before y, then y doesn’t come before x.
(note: whether ‘asymmetry’ or ‘antisymmetry’ is correct here depends on whether we’re working with strict or weak orders, but it doesn’t really matter and would only complicate things to go into the detail).
The total order you’re probably most familiar with is ‘less than’ on the natural numbers: 1 is less than 2, which is less than 3, and so on. If we draw a total order, it looks just like a long line of objects (again, in the finite case at least).
Partial Order
Now, partial orders are similar, but are a bit more relaxed about things. They don’t want to line things up in a fixed, rigid order – they just want certain things to come before certain other things. They might not mind which comes first out of x and y, so long as x comes before z.
A partial order must still be transitive and asymmetric, but we no longer require totality. An example of a partial order is “is an ancestor of” on the set of all humans that have ever lived. My grandfather is an ancestor of my father, and my father is an ancestor of me, so my grandfather is an ancestor of me (by transitivity). Also, because my father is an ancestor of me, I’m not an ancestor of my father (by asymmetry). There might be people who are not ancestors of each other at all – such as my father and my mother.
