About Concurrency

Simple, Simon and Sage wonder
whose fish is the last to go into the bucket?

What is this about concurrency

by: burt rosenberg
at: university of miami
date: september 2026

Special reading for Monday, 21 September 2026

Concurrent and Synchronized

When multiple threads run they are concurrent. Although this evokes the idea that they are running at the same time, for the purposes of analysis we only consider that they run without coordination between them.

The notion of coordination is conceptualized by identifying particular events in each thread. An event can be the first time a particular line of code is executed in that thread, or a unique write to a variable.

Suppose with have two events in two different threads. They are concurrent when there is no proof of an ordering between those events. If, by some mechanism, one event is constrained to occur before the other, the events are synchronized.

Concurrent events : (any time order of X and Y is strictly coincidental)

 T1:  ~~~~~~~~~~~ X ~~~~~~~~   

 T2:  ~~~~~~~ Y ~~~~~~~~~~~~ 

Synchronized events : (Y must follow X)

 T1:  ~~~~~ X ~~~~~~~~~~~~~~ 
             \
 T2:  ~~~~~~~ Y ~~~~~~~~~~~~

Interacting threads

Threads can interact through the sharing of variables, data, or data structures. How exactly they interact depends crucially on whether the threads are in the same or different processes. If they are in different processes, the types of interaction depend on whether the processes are on the same or different computers.

If threads interact, the outcome of a sequence of operations can depend on the global ordering of events. Consider inserting and removing an element from a linked list. The result can depend on the global ordering of the events. Suppose we take the events of inserting and removing to be atomic, so that one fully occurs before the other.

There are two possible outcomes, both of which can claim to be correct. If the events are concurrent, we cannot control which of the two outcomes occurs. If we wish to control which result occurs, we have to synchronize the events.


         T1:  ~~~~ INSERT ~~~~~~~~~~~~~~~~   

         T2:  ~~~~~~~~~~~~~~~ REMOVE ~~~~~ 

         +---+--+      +---+--+      +---+---+
head --->| 1 | *------>| 2 | *------>| 3 | / |
         +---+--+      +---+--+      +---+---+

INSERT
         +---+--+      +---+--+      +---+--+      +---+---+
head --->| 1 | *------>| 2 | *------>| 4 | *------>| 3 | / |
         +---+--+      +---+--+      +---+--+      +---+---+
REMOVE
         +---+--+      +---+--+      +---+---+
head --->| 1 | *------>| 4 | *------>| 3 | / |
         +---+--+      +---+--+      +---+---+


         T1:  ~~~~~~~~~~~~~~~ INSERT ~~~~~

         T2:  ~~~~ REMOVE ~~~~~~~~~~~~~~~~ 

         +---+--+      +---+--+      +---+---+
head --->| 1 | *------>| 2 | *------>| 3 | / |
         +---+--+      +---+--+      +---+---+
REMOVE
         +---+--+      +---+--+
head --->| 1 | *------>| 3 | / |
         +---+--+      +---+--+ 
INSERT
         +---+--+      +---+--+      +---+---+
head --->| 1 | *------>| 3 | *------>| 4 | / |
         +---+--+      +---+--+      +---+---+

We have assumed that insert and remove are atomic, so that one occurs before the other, even though we do not control which occurs first. In reality, data structure updates consist of many steps. They are not one event, but a sequence of many events. Taking this into account, our concurrent threads can produce entirely incorrect results.

For example, if the insert finds the place to insert while the remove finds the place to remove, and they then continue their operations in some interleaved order, we can obtain a result that does not correspond to any ordering in which one operation occurs entirely before the other.


         T1:  ~~~~ INSERT ~~~~~~~~~~~~

         T2:  ~~~~ REMOVE ~~~~~~~~~~~~ 


         +---+--+      +---+--+      +---+---+
head --->| 1 | *------>| 2 | *------>| 3 | / |
         +---+--+      +---+--+      +---+---+

                   +------------------+ (remove in progress)
                   |                  |
         +---+--+  |   +---+--+       +---------->+---+---+
head --->| 1 | *---+-->| 2 | *---+--------------->| 3 | / |
         +---+--+      +---+--+  |             +->+---+---+
                                 |   +---+--+  |
                                 +-->| 4 |  *--+  (insert in progress)
                                     +---+--+
Result:
         +---+--+      +---+---+
head --->| 1 | *------>| 3 | / |
         +---+--+      +---+---+
         
         +---+--+      +---+--+
         | 2 | *------>| 4 | *----->  (this is a lost list fragment)
         +---+--+      +---+--+

Thread Counting Project

Suppose we have multiple threads concurrently running this routine,

int counter(int * count, int n) {
    int i, j ;
    for (i=0; i<n; i++) {
        j = count ;      // event A
        j += 1 ;         // event B
        count = j ;      // event C
    }
    return 0 ;
}

If the threads are concurrent, but not synchronized, what is the final value of the variable count? It will depend on the order of the events (A), (B) and (C) between threads.

We can denote by A^t_r as the r-th occurrence of event (A) in thread t. Then letting,

A^t_r < A^t'_r'

mean the r-th occurrence of event (A) in thread t came before the r'-th occurrence of event (A) in thread t', we have the necessary ordering within each thread,

... < A^t_i < B^t_i < C^t_i < A^t_i+1 < B^t_i+1 < C^t_i+1 < ...

However we have no such necessary synchronization between threads.

We can consider the event ordering,

C^t_i < A^t'_j [MAX]

for all i and j and all t<t'. This does not mean that the threads are synchronized. Synchronous means the ordering is necessary. Synchronization means that an ordering is required. This ordering is simply what happened in this particular run.

We call this ordering MAX because it results in the maximum possible final value of the counter over all possible orderings of the events.

Other final values are possible. For instance,

A^t_i < C^t'_i [N]

for all t and t' and all i, constrains the threads to work together in rounds of iteration. In each round, every thread reads the same value, increments it, and writes the same resulting value. The final value of the counter will then be the number of iterations, N.

See csc421-271/thread-count on GitHub.

Consistent serializable correctness

The world is made up of events that occur in time. These events are atomic events in the sense that they occur at some time: before that time they have not occurred, and after that time they have occurred. Events may occur on separate timelines, as in different threads. The state of the world at any instant can depend on how these events are arranged on a global timeline.

In coordinating actions, there is a discrepancy between when an event occurs in physical time and when it is recognized in logical time. A packet announcing a new value, for example, travels through a route involving physical transmission and software processing on many devices. We therefore need a point on a logical timeline representing the actualization of the event.

All events are themselves implemented by sub-events. Even writing a memory location involves multiple physical steps: a value may first enter an L1 cache and later reach shared memory, while cache-coherence protocols coordinate writes from different processors. We would nevertheless like to represent the entire operation as a single logical event.

A real event a_i which may consist of many implementation steps and which is ordered along its own thread timeline, is therefore represented by a logical event A_i at a point T_i on a global logical timeline. The logical representation has three requirements:

Consistent serializable correctness: There is a single placement of the logical events on the timeline — that is, a setting of all T_i — such that the resulting state of the world follows from and is fully explained by this ordering.
Transactional atomicity: An action designated as atomic is represented by a single logical event at a single logical time. Its implementation may consist of many physical steps, but those steps are compressed into one logical event.
Non-clairvoyance: No logical realization precedes the physical occurrence of the event

In this context, synchronization is any set of constraints on the serializations that are allowed. The word serialized refers to the linear ordering of events. The word consistent is used to eliminate the case where different serializations are proposed each to explain some world facts. And correctness is that the world facts then follow from the events operating on the world in the order of the unique serialization.

In the example of list insert and deletes, concurrent programs can generate these insert and delete actions, and correctness is that we can organize the insert and the delete to produce a reason for the list at each moment in time.

In the case of the counter, we have divided the increment into two atomic events, read and write. Within the thread they are ordered but between threads need need to put them on a time line. We can explain different final values by various placements on the timeline. If the read-write events are considered atomic transactions, those that occur in one iteration of one thread are mapped to the same point in logical time. The final value will always be the same, whatever the mapping.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 18 sep 2026
update: 23 sep 2026