Goals

Understand how there is no global reliable time in distributed systems and therefore other mechanisms are needed to determine the order of events. Learn about the happened-before relation and how Lamport Clocks can be used to ensure a partial ordering of events between multiple processes or nodes. Get to know and practice the algorithm to exchange Lamport timestamps with messages and implement a versioned key-value store.

Examples

• Follow a sequential trading process at a stock exchange
• Follow a concurrent trading process at a stock exchange

Exercises

• Practice the algorithm and draw a graph with happened-before relations
• Implement a versioned key-value store based on an example

Introduction

Context

Time

We often need the concept of time to synchronize and coordinate actions between multiple processes. In the following examples, the events have a dedicated sequence:

• Send ticket only if the payment was successful → Process Synchronization
• Confirm payment only if data was stored on three servers → Data Synchronization
• Write to a file only if no other process is using it → Coordination

Order of Events

The order of events is often very important for the outcome. Let’s assume we have a system where admins concurrently update the role of a user. With the following order, alice ends up having the role viewer:

{ "updater": "bob", "user": "alice", "role": "editor" }
{ "updater": "eve", "user": "alice", "role": "admin" }
{ "updater": "bob", "user": "alice", "role": "viewer" }

Now, let’s change the update order. With this order, alice ends up having the role admin:

{ "updater": "bob", "user": "alice", "role": "editor" }
{ "updater": "bob", "user": "alice", "role": "viewer" }
{ "updater": "eve", "user": "alice", "role": "admin" }

We can try to generate a deterministic order by adding a timestamp when the events are created (starting at 0):

{ "timestamp": 0, "updater": "bob", "user": "alice", "role": "editor" }
{ "timestamp": 1, "updater": "eve", "user": "alice", "role": "admin" }
{ "timestamp": 2, "updater": "bob", "user": "alice", "role": "viewer" }

Unfortunately, this method only works reliably if all clocks in all computers around the world are guaranteed to have the exact same time, which is not the case. Further, if all events arrive at the same timestamp, their order cannot be reliably determined.

Total and Partial Ordering