2 System models and order and time

 

This chapter covers

  • Synchronous and asynchronous systems
  • Component and network behavior
  • Order, physical time, and logical time

Thinking in distributed systems requires thinking in system models, such as synchronous and asynchronous system models, and also the concepts of order, physical time, and logical time. Our goal in this chapter is to understand the state of affairs or forces at play that determine and constrain the behavior of distributed systems.

2.1 System models

We can’t reasonably talk about a distributed algorithm or protocol without talking about the assumptions we made about the underlying distributed system. This is a set of assumptions, known as the system model, about the system's set of components, its network, and its timing behavior (see Table 2.1).

Table 2.1 Examples of assumptions about the system
One System Model
Another System Model
Components may not fail
Components may fail
Messages may not get lost
Messages may get lost
Clocks are perfectly synchronized
Clocks are not perfectly synchronized

Why are system models crucial for our discussions? Algorithms and protocols that are correct under one system model may not be correct under another system model—any deviation may render an algorithm or a protocol incorrect.

2.1.1 Theory and practice

2.1.2 Synchronous distributed systems

2.1.3 Asynchronous distributed systems

2.1.4 Partially synchronous systems

2.1.5 Component and network behavior

2.1.6 Realistic system models

2.2 Order and time

2.2.1 The happened-before relationship

2.2.2 Time and clocks

2.2.3 Physical time and physical clocks

2.2.4 Logical time and logical clocks

2.2.5 Physical time versus logical time

2.3 Summary