As developers, we frequently use the terms asynchronous, concurrent, or parallel. Yet we grapple to find an accurate and concise definition. We are stuck in loop of defining each term by referencing another, explaining asynchronous by leaning on concurrent and concurrent by leaning on non-blocking until our mental model is nothing but a blur.

In this blog post, we will aim to think above the code and use a minimal model of computation to accurately and concisely define and delineate

• synchronous vs asynchronous execution
• sequential vs concurrent execution
• serial vs parallel execution

Computational Model

In this blog post, we will use a minimal computational model to build a foundational understanding of asynchronous, concurrent, and parallel executions.

Our computational model consists of two elements: executions and events. An event can be one of four types:

• !iₙ Invocation event at the caller This event type represents the invocation of the callee at the caller
• ?iₙ Invocation event at the callee This event type represents the invocation of the callee at the callee
• !cₙ Completion event at the callee This event type represents the completion of the callee at the callee
• ?cₙ Completion Event at the caller This event type represents the completion of the callee at the caller

Synchronous vs Asynchronous

Synchronous and asynchronous executions represent fundamental paradigms of control flow management. These paradigms dictate how executions coordinate with each other.

Synchronous executions are characterized by a linear control flow: A synchronous execution is an execution where every invocation at the caller is immediately followed by the corresponding completion event at the caller. In effect, an invocation event blocks the caller until a completion event unblocks the caller.

λ1: (!i1) • (?c1) • (!i2) • (?c2)

Asynchronous executions are characterized by a non-linear control flow: An asynchronous execution is an execution where an invocation at the caller does not need to be immediately followed by the corresponding completion event at the caller. In effect, an invocation event does not block the caller.

λ1: (!i1) • (!i2) • (?c1) • (?c2)

The most significant consequence of asynchronous executions is that they enable concurrent executions.

Sequential vs Concurrent

Leslie Lamport’s seminal paper, Time, Clocks, and the Ordering of Events in a Distributed System introduces the happens-before relationship.

Adapted to our computational model, we define that an event ‘a’ happens before an event ‘b’ if either:

• a and b occur in the context of the same execution and a occurs before b
• a is the cause and b is the effect i.e.
  • a is an invocation event at the caller and b is the corresponding invocation event at the callee
  • a is a completion event at the callee and b is the corresponding completion event at the caller
• a happens-before b and b happens-before c then a happens-before c

If neither a happens before b nor b happens before a, a and b are concurrent

The happens-before relationship allows us to define synchronous and asynchronous executions:

In a sequential execution, invocation and completion events are totally ordered, that is, for every event pair a and b, either a happens-before b or b happens before a. This is also called linear control flow.

In a concurrent execution, events are partially ordered, that is, for some event pairs and a and b, a and b are concurrent. This is also called non-linear control flow.

Intuitively, concurrency corresponds to independence, if a and b are concurrent, a could not have had any influence on b and vice versa.

Concurrency does not equal parallelism. Two concurrent executions may still be executed in series but they can be executed in parallel.

Serial vs Parallel

Concurrency is a statement about logical time while parallelism is a statement about physical time.

Two execution are serial if they do not overlap in terms of physical time.

Two execution are parallel if they do (partially) overlap in terms of physical time.

Bonus • Blocking vs Non-Blocking

The Terms asynchronous and non-blocking are often used synonymously, however, they are not the same. Understanding blocking vs non-blocking requires us to extend our computational model and reason across two levels: execution and runtime.

Execution Level

Asynchronous executions block when they await: The caller blocks until the callee completes. However, that is not the type of “blocking” we have in mind when talking about blocking vs non-blocking.

Runtime Level

The question is whether, when an asynchronous execution blocks while awaiting, will the thread running the execution block?

• A runtime is considered blocking if the thread that is running an execution will block (will not run other executions) when the execution blocks
• A runtime is considered non-blocking if the thread that is running an execution will not block (may run other executions) when the execution blocks

Non-blocking implementations, where n execution are run by m threads or by 1 thread are arguably more popular in practice

About this post

Concise and accurate definitions are essential to communicate complex concepts, both to technical and non-technical stakeholders. If we do not share a common vocabulary, we cannot share a common understanding!