2 System models, order, and time

Thinking about distributed systems requires thinking about system models, such as synchronous and asynchronous system models, and also the concepts of order, physical time, and logical time. Consider this contrast: in a synchronous system with timing guarantees, if a message does not arrive within a known bound, we know that a failure has occurred. In an asynchronous system with no timing guarantees, if a message does not arrive, we know nothing. A failure may have occurred, or the message may be delayed. 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 set of assumptions, known as the system model, is about the system’s components, its network, and its timing behavior (see table 2.1).

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 clocks vs. logical clocks