A Tale of Two Dimensions
In this blog post, we will explore distributed systems through the lens of two fundamental dimensions: synchronous versus asynchronous and sequential versus concurrent.
Different authors think differently about terminology. I do not want to claim that my thoughts are correct and others’ are not correct. Instead, I want to share my mental model, which is designed to be minimal and self consistent.
This mental model helps me to reason about distributed systems with confidence. May this mental model help you as well.
Keywords: Distributed Systems, Synchronous, Asynchronous, Sequential, Concurrent, Deterministic, Non-Deterministic, Parallel.
Introduction
A distributed system is a collection of communicating processes; processes communicate by exchanging messages via a network.
We may reason about a distributed system as if the system proceeds in discrete steps, with either a process or the network taking a step.
We will think about the system as exactly one process or the network taking exactly one step at a time.
A step can be either an external step, such as receiving a message or sending a message, or an internal step, such as performing a local computation, including accessing local state.
More than one process may be enabled, that is, more than one process may be able to take the next step.
System Level vs Process Level
In this blog post, we will differentiate between the system level and the process level. At the system level, we will reason about the collection of processes, while at the process level, we will reason about an individual process.
System Level • Synchronous vs Asynchronous
On a system level, the concepts of synchrony and asynchrony refer to statements about physical time.
Different authors think differently about synchronous distributed systems but each author assumes a strong notion of physical time.
In this theoretical system model, each process is equipped with a clock that is either perfectly synchronized with other clocks or has a known upper-bound deviation. Furthermore, internal and external steps unfold in strict time or occur with a bounded delay.
So some authors prefer to think about a synchronous system as a system without any uncertainty about its timing and some authors prefer to think about a synchronous system as a system with some bounded uncertainty about its timing.
As with synchronous systems, different authors think differently about asynchronous distributed systems, but here the difference is significant:
- Some authors assume no notion of time at all
- Some authors assume a weak notion of time
Some problems do not have a solution assuming no notion of time yet do have a solution assuming a weak notion of time (see FLP Impossibility).
No notion of time
In this theoretical system model, no process has access to any kind of clock and steps occur in arbitrary time or internal and external steps occur with arbitrary delay. In this model, the notion of time does not exist, the most significant consequence being that a process cannot use timeouts.
Weak notion of time
In this theoretical system model, a process has access to a clock that is not synchronized to other clocks and has an unknown deviation and steps occur in arbitrary time or internal and external events occur with arbitrary delay. In this model, the notion of time does exist, the most significant consequence being that a component can use timeouts.
Both, synchronous and asynchronous system models are theoretical system models. In reality, no distributed system behaves as entirely synchronous or entirely asynchronous. Instead, the system’s behavior lies somewhere in between.
The partially synchronous system model acknowledges this reality and postulates that a distributed system is synchronous most of the time and asynchronous sometimes. This model matches both our experience as well as our expectations: processes and networks are generally well behaved but sometimes they do act up.
System Level • Sequential vs Concurrent
On a system level, the concepts of sequentiality and concurrency refer to statements about logical time.
A sequential system is a system where only (up to) one process is enabled at one point in time while a concurrent system is a system where any number of processes are enabled at one point in time.
The sequential system model is a theoretical system model. In fact, we may argue that the sequential system model runs afoul the very reason to deploy distributed systems in the first place.
In reality, no distributed system is sequential. Nevertheless, sometimes the illusion of sequentiality is desirable. For example, a correctness criteria for database transactions is serializability, the guarantee that a concurrent execution of multiple transactions is equivalent to some sequential execution.
Serializability provides the illusion of sequentiality in a concurrent environment
Process Level • Synchronous vs Asynchronous
On a process level, the concepts of synchrony and asynchrony refer to statements about logical time.
A synchronous process is a process where every send step is immediately followed by a corresponding receive step — or in a system with timeouts, a timeout.
Process = send!req . recv!res ...An asynchronous process is a process that does not impose any restrictions on the sequence of steps.
Process = send!req ...Not imposing any restrictions allows us to reason about processes that send a request, do some work, then wait for a response as well as processes that fire-and-forget.
In practice, this notion of synchrony and asynchrony can be extended to other I/O actions like accessing the file system.
Sequential vs Concurrent
On a process level, the concepts of sequentiality and concurrency refer to statements about logical time.
A sequential process is a process that does not present a choice in the order of execution to obtain a correct result.
Process = a . bA concurrent process is a process that present a choice in the order of execution to obtain a correct result.
Process = (a . b) | (b . a)We need to include the modifier “to obtain a correct result” otherwise we allow race conditions into the definition.
Since the order of execution is arbitrary, that is, step a must not depend on step b and step b must not depend on step a, a and b can also execute in parallel (see below).
Bonus Round • Concurrency & Determinism
Concurrency is not the same as non-determinism. Although more than one process is enabled at the same time or more than one execution order is correct, a deterministic scheduler may still choose the next step or the execution order deterministically.
Bonus Round • Concurrency & Parallelism
Concurrency is not the same as parallelism. Nevertheless, concurrency is a prerequisite for parallelism. Concurrency is a statement about logical time, parallelism is a statement about physical time.
Two operations are parallel if the operations overlap in time.
Conclusion
Synchronous versus asynchronous and sequential versus concurrent are two fundamental dimensions in the world of distributed systems.
However, no real world distributed system exists on the extremes. Instead, real world distributed systems are synchronous and in effect sequential some times and asynchronous and concurrent other times.
Thank you
Thank you to Joran Dirk Greef, Founder & CEO of @TigerBeetleDB for his suggestion of “A Tale of Two Spectrums” as the title for this blog post 🚀
