(Interacting) computational system [Goldin et al., 2006]
In a computational system , two or more computational processes behave (by computing) and work together (by interacting). Ch. 1
A
Acceptor
Acceptor : decides the candidate values for the final decision. Ch. 6
Access
Access : hide differences in data representation and in the access to resources. Ch. 1
actions
Following Baquero & Preguiça [2016]: any computational system can be modelled as a sequence of executed actions , each defined by a change of state in the system or, more generally, in the world (reading memory, writing a file, switching on a lamp). Ch. 2
address
Users are identified by f(K pub ) (a hash or a CA certificate), their address . Ch. 7
Agreement
For Paxos the slides use today's names. Agreement : no two processes decide differently. Validity : the decided value was proposed. Termination : every non-faulty process eventually decides. The first two are safety , the third liveness . Ch. 6
Agreement problem [Fischer, 1983]
Agreement problems involve a system of processes, some of which may be faulty. A fundamental problem of fault-tolerant distributed computing is for the reliable processes to reach a consensus. Ch. 6
AR
AR integrates virtual and physical space, merging real-world information with context-sensitive digital content in a meaningful way [Furht, 2011]. The point is that the two layers mutually affect each other , dynamically. Ch. 3
architectural constraints
Properties are induced by constraints , and architectural constraints are often motivated by applying a software engineering principle to an aspect of the architectural elements. Ch. 8
architectural properties
The architectural properties of a software architecture derive from the selection and arrangement of components, connectors and data. Ch. 8
Architectural style [Fielding, 2000]
An architectural style is a coordinated set of architectural constraints that restricts the roles/features of architectural elements and the allowed relationships among those elements within any architecture that conforms to that style. Ch. 8
Asynchronous
Asynchronous : otherwise. This models unpredictable load on network and CPUs, where it is never possible to know whether a process has crashed or not . Ch. 6
atomic actions
Start from a set of atomic actions ( a , b , …), each representing indivisible behaviour. Ch. 8
Attributes of dependable systems [Zhao, 2014]
Availability : readiness at any point in time, the probability that the system is there when a client needs the service. Reliability : providing correct services continuously for a period of time. Integrity : protecting the system's state from being compromised under various threats. In dependable computing research it typically translates into the consistency of server replicas , if redundancy … Ch. 4
Availability
Availability : the system is ready for immediate use, i.e. the probability that it operates correctly at any given moment. Ch. 4
B
BASE [Fox et al., 1997]
BASE : B asically A vailable, S oft state, E ventual consistency. Ch. 5
Basic (single-bit) consensus [Fischer, 1983]
There is a fixed number n of possibly faulty processors, and each has an initial bit x i . The non-faulty processes must agree on a bit y , the consensus value . The problem is solvable if some protocol makes all non-faulty processors terminate with the same y . Ch. 6
BFT consensus algorithm C4, Consensus II
A distributed protocol aimed at making an SMR system resistant (i.e. ensuring eventual consistency) to Byzantine failures. Ch. 7
bivalent
A configuration (all process states plus the messages in transit) is univalent (0- or 1-valent) if only one decision is still reachable from it, and bivalent if both are. Ch. 6
A clever implementation of an SMR system keeping track of which users own some assets (representations), by means of a replicated ledger, updated through consensus. Users : identified through public keys, sign their transactions. Assets : anything with value, an owner, possibly mutable state (money, documents, property acts, contracts). Ledger : a replicated notary service holding the assets' … Ch. 7
boundary
How do we capture the state of a distributed system at time t ? First, fix the boundary , the line between the system's components (inside) and its environment: every other system that affects it in any way. Ch. 4
branch
That is a branch : several versions of the ledger, an inconsistency. Ch. 7
Byzantine faults
Manifestation. Content : wrong values passed on to other components, always the same ones, or different values to different components, the case modelled as Byzantine faults . Timing : replying too early or too late; at the extreme never, as when a component crashes or hangs (infinite loop, deadlock). Ch. 4
C
Caching
Replication : copies near (potential) users increase availability and cut latency. Caching is a special form, decided by the client of a resource; replication is decided by its owner . Ch. 1
CAP (Brewer's conjecture) [Brewer, 2000]
A distributed database potentially features three desirable properties: C onsistency, A vailability, and tolerance towards network P artition. According to the CAP theorem , any shared-data distributed system can have at most two of these three. Ch. 5
CAP theorem
A distributed database potentially features three desirable properties: C onsistency, A vailability, and tolerance towards network P artition. According to the CAP theorem , any shared-data distributed system can have at most two of these three. Ch. 5
Causal
Causal . Events not yet on stable storage are piggybacked on every message sent, so a process can access all nondeterministic events that may causally affect its state, enabling consistent recovery. Ch. 4
Causal consistency [M3, after Tanenbaum & van Steen, 2017]
A data store is causally consistent when all processes see write operations that are in a cause/effect relation in the same order. Ch. 5
causal history
e plus everything with a path to it is its causal history : the events that could have influenced it. Ch. 2
causal path
c is a possible cause of e iff there is at least one causal path , a directed path through process lines and messages, from c to e . Ch. 2
causally consistent
A data store is causally consistent when all processes see write operations that are in a cause/effect relation in the same order. Ch. 5
chain of threats
This is the chain of threats , and why “fault” and “failure” are often, somewhat improperly, used interchangeably. Ch. 4
channel state
The channel state is the set of messages in transit along the channel, not yet received by the target process. Ch. 4
checkpoint
A checkpoint of a distributed system is a copy of the system state. Ch. 4
Checkpoint, checkpointing [Zhao, 2014]
A checkpoint of a distributed system is a copy of the system state. If it is available after the system fails, it can be used to recover the system to the state it had when the checkpoint was taken. Checkpointing is (periodically) taking a copy of the system state and saving it to a stable storage that can survive the faults tolerated. Ch. 4
Checkpointing
Checkpointing is (periodically) taking a copy of the system state and saving it to a stable storage that can survive the faults tolerated. Ch. 4
Client-centric consistency [M3]
Client-centric consistency models ensure that whenever a client connects to a new replica, that replica is up to date according to the client's previous accesses to the same data at other replicas. Consistency no longer refers to the resource itself (its nature, its dynamics) but to the view each client has of it . Ch. 5
Client-centric consistency models
Client-centric consistency models ensure that whenever a client connects to a new replica, that replica is up to date according to the client's previous accesses to the same data at other replicas. Consistency no longer refers to the resource itself (its nature, its dynamics) but to the view each client has of it . Ch. 5
closure operator
The modal operators are reinterpreted: □ (necessarily) as the interior operator , ◇ (possibly) as the closure operator of a topological space. The modal logic S4 [Bull & Segerberg, 1984] is sound and complete with respect to this topological semantics, and S4 is the modal logic of any Euclidean space. Ch. 3
cluster
A cluster is a collection of similar workstations or PCs, running the same OS, in the same area, on a high-speed LAN. Ch. 1
Code segment
Code segment : the set of executable instructions of the process. Ch. 3
common infrastructure
A common infrastructure , aiming at actual interoperability, so it handles finer details. Until CORBA 2.0, two vendors' CORBAs did not interoperate. Ch. 7
common mode failures
Relationship. Independent (no causal relationship) or correlated (one causes the other). Multiple components failing for a common reason are common mode failures . Ch. 4
common model
A common model : CORBA, Java RMI, DCOM and OSGi all model a system as network-reachable objects (with differences even there). Ch. 7
communication function
Parallel composition either interleaves (one side moves; if it terminates, the other remains) or lets both sides act together through a communication function γ that turns a pair of actions into one. Ch. 8
component
A component is a modular unit with well-defined interfaces, replaceable within its environment. Interfaces go both ways: they are both required and provided . Ch. 8
A component is a modular unit with well-defined interfaces, replaceable within its environment. Interfaces go both ways: they are both required and provided . A connector is an abstraction mediating communication, coordination and cooperation among components: anything providing a mechanism for interaction among them. Ch. 8
Computational geometry
Computational geometry [de Berg et al., 2000] uses space to represent problems, spatial or not, geometry to make them computable, and algorithms to solve them. Ch. 3
computational process
The elementary computational process is sequential . As the phenomenal expression of a computing machine's dynamics, it has input/output and a context. A computing machine is then the place where a computational process occurs . Ch. 1
computational system
In a computational system , two or more computational processes behave (by computing) and work together (by interacting). Ch. 1
Conceptual integrity C4, Middleware and Models II
The property of a system of being understandable and explainable through a coherent, limited set of concepts. Ch. 7
Concurrency
Concurrency : hide the sharing of a resource by multiple users. Ch. 1
concurrent
Happens-before is a partial order . When neither a → b nor b → a , nothing can be said about their order. They are concurrent : a ∥ b . Ch. 2
concurrent computation
We talk of concurrent computation whenever at least two computational processes have a different temporal context : T ≠ T′ . A concurrent system is a computational system performing concurrent computations. Ch. 1
Concurrent computation & system M2 · course definition
We talk of concurrent computation whenever at least two computational processes have a different temporal context : T ≠ T′ . A concurrent system is a computational system performing concurrent computations. Ch. 1
conit
Deviation is measured on a unit of consistency, the conit . Ch. 5
connector
A connector is an abstraction mediating communication, coordination and cooperation among components: anything providing a mechanism for interaction among them. Ch. 8
Consensus [C3]
Consensus is the process by which we reach agreement over system state between unreliable machines connected by (possibly) asynchronous networks. Ch. 6
Consistency (atomic) [Gilbert & Lynch, 2002]
A consistent service is modelled as an atomic data object : operations are totally ordered, and each operation occurs in a single instant of time. Among the consequences, all read operations occurring after a write operation completes must return the value of that write or of a later one. If the system is consistent, we get correct responses. This C is unlike ACID's: it encompasses both the A … Ch. 5
Consistency model [M3, after Tanenbaum & van Steen, 2017]
A consistency model is essentially a contract among the processes and the data store, ensuring the correctness of data given a set of rules that processes have to follow. Ch. 5
Consistent global state [Zhao, 2014]
A global state from a set of checkpoints is a consistent global state if it is reachable from the initial state of the system. Otherwise it is inconsistent : its checkpoints are incompatible, not admissible, and cannot be used for recovery. Ch. 4
container
A container is a process sharing the host kernel, with an image that carries the application and its dependencies. Kernel namespaces restrict what it sees (PIDs, network, hostname, mounts); cgroups limit what it consumes. (Details: Giovanni Ciatto's lecture.) Ch. 9
container orchestration
Many containers on many hosts raise this course's questions: where each runs, who restarts it, how clients find it after it moves, how to replace it while it serves. Answering them automatically is container orchestration . Ch. 9
A plugin interface that lets Kubernetes use a wide variety of container runtimes; one must be working on each node. Kubernetes is not tied to Docker: other supported runtimes are containerd, CRI-O and Mirantis Container Runtime. Ch. 9
Containerisation [Matteini, 2025; Docker]
A lightweight form of virtualisation. It provides process and filesystem isolation by exploiting the Linux kernel, and it has replaced traditional virtual machines in many deployment scenarios. The most popular platform is Docker. Ch. 9
continuous consistency
These bounds define continuous consistency . Ch. 5
control plane
A Kubernetes cluster consists of a control plane plus a set of worker machines, called nodes . Ch. 9
controller
That last sentence is the whole machine. A controller runs a loop that never ends: observe spec and actual state, compute the difference , take an action that shrinks it (create a Pod, delete one, bind one to a node), repeat . This is the reconciliation loop . Ch. 9
coordinated checkpointing
Tamir & Sequin [1984] is a coordinated checkpointing protocol. Ch. 4
cyber-physical systems
The result is cyber-physical systems (CPS): the integration of physical processes with networked computing, “to create new science, techniques, and products”. Ch. 2
D
data store
The setting is a data store : logically one store, physically distributed and replicated across processes, each working on a local or nearby copy. Ch. 5
Dependability [Zhao, 2014]
In distributed computing, dependability is the ability of a distributed system to provide correct services to its users despite the many different threats: undetected software defects, hardware failures, malicious attacks, … Ch. 4
dependency requirements
As stated, “always output 0” would work. So dependency requirements say how y must depend on the inputs, and each choice defines a different problem: Ch. 6
Deployment [Matteini, 2025]
A Deployment manages a set of Pods running an application workload. It provides declarative updates for Pods and ReplicaSets, rollout (current state → desired state, e.g. a new image version, avoiding downtime) and rollback , and is used to release new versions. Ch. 9
deterministic
A machine is deterministic if its state depends only on the initial state and the input sequence. Ch. 7
distributed computation
We talk of distributed computation whenever at least two computational processes have a different spatial context : S ≠ S′ . A distributed system is a computational system performing distributed computations. Ch. 1
Distributed computation & system M2 · course definition
We talk of distributed computation whenever at least two computational processes have a different spatial context : S ≠ S′ . A distributed system is a computational system performing distributed computations. Ch. 1
Distributed concurrent computing
Distributed concurrent computing : S ≠ S′ , T ≠ T′ . Ch. 1
Distributed ledger technology [Focus Group on Application of DLT, 2017]
Distributed ledger technology (DLT) refers to the processes and related technologies that enable nodes in a network to securely propose, validate, and record state changes (or updates) to a synchronised ledger that is distributed across the network's nodes. Ch. 7
Distributed parallel computing
Distributed parallel computing : S ≠ S′ , same T . Ch. 1
distributed pervasive system
Here instability is the default: battery-powered mobile devices, sporadic connections. A distributed pervasive system is part of our surroundings and generally lacks human administrative control. Ch. 1
distributed system
A distributed system is “a collection of independent computers that appears to its users as a single coherent system”. Ch. 1
domino effect
Rolling a process back undoes its sends, so their receipts become orphans; each receiver rolls back before its receipt, undoing its sends, and so on. With an unlucky pattern, this domino effect pushes every process back to its initial state. Ch. 4
dormant
A fault may be dormant : a bug harmless until its code runs, an unlocked shared variable harmless until two threads update it concurrently. Ch. 4
E
Engineer's view M4
A distributed system is “a collection of autonomous computational entities conceived as a single coherent system by its designer”. Constructive and design-oriented: the computer engineer's definition, an a priori one. Ch. 1
Enterprise Application Integration
But middleware systems are many and incompatible, and making A-applications work with B-applications is the Enterprise Application Integration (EAI) task, with the emphasis on horizontal communication (application-to-application, middleware-to-middleware). Ch. 7
error
A system fails when it does not behave as promised. An error is a part of a system's state that might have caused a failure. The cause of an error is a fault . Ch. 4
events
In a distributed system actions execute in many places and are represented as events : sending or receiving a message, updating a database record. Ch. 2
eventual consistency
If no update takes place for a while, all replicas gradually become consistent: eventual consistency . Ch. 5
Execution segment
Execution segment : the store for the execution state of the process, with private data, stack and program counter. Ch. 3
Extensibility
Extensibility : how easy it is to add new components and functionality to an existing system. Ch. 1
external
At each moment the system is in a state, determined collectively by its processes and threads: registers, stack, heap, file descriptors, kernel state… The part visible through user interaction is the external (observable) state, basically the abstract state of the specification. Ch. 4
F
Fail fast
Fail fast . The practice of halting immediately on an error state or unexpected condition. It enables early detection and diagnosis: a fault propagated to many components is much harder to pinpoint. Ch. 4
Fail-safe
Fail-safe . Failure causes no great harm to human life or the environment: the system defines safe states and moves to one when it can no longer meet its specification. Nuclear plant control must be fail-safe. Ch. 4
Fail-stop
Fail-stop . Dependability mechanisms make the system stop responding to requests when it fails, avoiding catastrophic consequences. Ch. 4
fails
A system fails when it does not behave as promised. An error is a part of a system's state that might have caused a failure. The cause of an error is a fault . Ch. 4
Failure
Failure : hide the failure and subsequent recovery of a resource. Ch. 1
Failure, error, fault [Tanenbaum & van Steen, 2017]
A system fails when it does not behave as promised. An error is a part of a system's state that might have caused a failure. The cause of an error is a fault . Ch. 4
fault
A system fails when it does not behave as promised. An error is a part of a system's state that might have caused a failure. The cause of an error is a fault . Ch. 4
Fault tolerance
Fault tolerance . Hardware fails, so robust software is not enough; and unless a system is fully stateless, restarting it does not restore its state. Ch. 4
Features of dependable systems [Tanenbaum & van Steen, 2017]
Availability : the system is ready for immediate use, i.e. the probability that it operates correctly at any given moment. Reliability : the system can run continuously without failure. It is defined over a time interval , not an instant. Safety : when the system temporarily fails, nothing catastrophic happens. Hard to define and to ensure; catastrophic basically means there is no established … Ch. 4
In a fully asynchronous system, no consensus protocol can tolerate even a single crash failure , under the mere requirement of non-triviality. Ch. 6
G
General Purpose Technology
A General Purpose Technology : as a middleware instance it brings gains to other sectors; mass adoption may be slow, but then yields productivity gains across industries. Ch. 7
Generals problem
Two relatives change what is agreed on: Problem [Fischer, 1983] Agree on Strong Weak Interactive consistency a vector y : what each processor's initial value was y i = x i for each non-faulty i the same, if no failures occur during the run Generals problem (reliable broadcast) the bit x that the general (transmitter) sends to all y = x if the general is not faulty y = x if no failures occur The concrete case is transaction commit [Dolev & Strong, 1982]: the data managers of a transaction agree whether to install its results or discard them (say, because one could not do its part). Ch. 6
genesis block
The first, genesis block is assumed shared by all replicas. Ch. 7
Geographic information system [Huisman & de By, 2009]
A computer-based system that supports the study of natural and man-made phenomena with an explicit location in space. To this end, the GIS allows data entry, data manipulation, and production of interpretable output that may provide new insights about the phenomena. Ch. 3
GIS
GIS capture, store, check and display data on positions on the Earth (maybe other planets soon), so in GIS the notion of space is clearly defined. Ch. 3
global absolute time
Sometimes applications need a time related to physical time: global absolute time . Ch. 2
global relative time
Sometimes a time server is not stably available, or not available at all, and all the processes need is a common time , whatever its relation to UTC: global relative time . Ch. 2
global state
The state of a distributed system, its global state , includes the state of every process. Aggregating them is not enough: messages move information between processes and change their states, so processes causally depend on each other, and dependencies cannot be lost in the global state . Ch. 4
grid
In a grid , resources from different organisations are brought together for collaboration across organisational boundaries, as a virtual organisation : people from existing organisations accessing resources (servers, databases, disks, …) made available by the participants. Ch. 1
H
Happens-before (a → b) [Lamport, 1978]
“ a happens before b ”: all processes agree that a occurs first, then b . It is observed directly in two situations, and closed under transitivity: Same process. If a and b are events of the same process and a comes first, then a → b : local events are ordered by local time. Message. If a is the sending of a message and b its receipt, then a → b : a message takes a finite, positive, non-zero time … Ch. 2
hash chain
A hash chain keeps track of a sequence of events: event i goes in block b i , and b i+1 records H(b i ) , so the sequence cannot be altered unnoticed. Ch. 7
height
Event counting. With δ = 1 , an event with timestamp h has h − 1 events before it on the longest causal path leading to it, whichever processes produced them. This is its height , the minimum logical duration needed to produce it. Ch. 2
Heisenbugs
Reproducibility. Reproducible (deterministic), like a null-pointer access, easily identified and repaired; or nondeterministic , like a bad thread interleaving, hard to reproduce: Heisenbugs . Ch. 4
highly available
A system hiding (most of) its failures is highly available ( Ch. Ch. 5
HorizontalPodAutoscaler
The HorizontalPodAutoscaler is one more control loop whose output is another object's spec: it rewrites the Deployment's replicas . Ch. 9
I
Integrity
Integrity : protecting the system's state from being compromised under various threats. Ch. 4
Interactive consistency
Two relatives change what is agreed on: Problem [Fischer, 1983] Agree on Strong Weak Interactive consistency a vector y : what each processor's initial value was y i = x i for each non-faulty i the same, if no failures occur during the run Generals problem (reliable broadcast) the bit x that the general (transmitter) sends to all y = x if the general is not faulty y = x if no failures occur The concrete case is transaction commit [Dolev & Strong, 1982]: the data managers of a transaction agree whether to install its results or discard them (say, because one could not do its part). Ch. 6
interior operator
The modal operators are reinterpreted: □ (necessarily) as the interior operator , ◇ (possibly) as the closure operator of a topological space. The modal logic S4 [Bull & Segerberg, 1984] is sound and complete with respect to this topological semantics, and S4 is the modal logic of any Euclidean space. Ch. 3
Interoperability : how easy it is to make one component or system work with different ones, based on standard specifications. Ch. 1
K
knowledge-intensive environments
In knowledge-intensive environments (KIE), large amounts of knowledge distributed in the environment are essential, and systems must access, understand and inject it while interacting locally. Ch. 1
Kubernetes [Kubernetes docs]
A portable, extensible, open source platform for managing containerised workloads and services. Ch. 9
Kubernetes object [Matteini, 2025]
Objects are persistent entities that Kubernetes uses to represent the state of the cluster: what containerised applications are running, and on which nodes; the resources available to those applications; the policies for application behaviour, such as restarts and upgrades. An object is a record of intent . Once it is created, the system constantly works to ensure that it exists. Creating it … Ch. 9
L
labelled transition systems
Operational semantics: typically structural operational semantics (SOS) [Plotkin, 1981]. It describes the single-step execution capabilities of systems, so that terms of the algebra translate into labelled transition systems (LTS): states linked by transitions labelled with actions. Ch. 8
Lamport's observation [Lamport, 1978]
If two processes do not interact, they need no synchronisation, because lack of synchronisation would not be observable. What usually matters is not the exact time at which events occur but the order in which they occur. Synchronising non-physical, logical clocks is therefore both admissible and useful. Ch. 2
Laws as axioms [Baeten, 2005]
Any mathematical structure with three binary operations satisfying the above laws is a process algebra. Most typically such structures are expressed as automata, mostly called transition systems . Ch. 8
LBS
LBS add a virtual layer to physical space: they use the position of a user or device to provide information, entertainment or security. Examples: Around Me, Mobike; BotFighters, GeoZombie [Prandi et al., 2016], Ingress, Pokémon Go, Harry Potter: Wizards Unite, Minecraft Earth. Ch. 3
leader
The remedy is a distinguished proposer, a leader , plus timers and backoffs. Ch. 6
Learner
Learner : collects this from the acceptors and reports the final decision back to the clients. Ch. 6
Ledger : information store that keeps records of transactions that are intended to be final, definitive, and immutable. Distributed ledger : ledger shared across a set of DLT nodes and synchronised between them using a consensus mechanism. DLT : technology that enables the operation and use of distributed ledgers. Ch. 7
limits
A container spec gives image , command , exposed port and protocol . The resources field manages hardware: requests is the CPU/memory Kubernetes guarantees to the container (the scheduler places Pods by it), limits the maximum it can use. CPU is in millicpu (0.1 CPU = 10% = 100m ), memory in bytes. Ch. 9
Local validity of a block C4, Blocks & Block Chains III
With b i−1 the replica's last known block, b i is locally valid if ph i ≡ H(b i−1 ) h i ≡ h i−1 + 1 ≡ i ts i − ts i−1 ∈ [Δt − ε ; Δt + ε] ( Δt , ε chain-specific) r i 1 = γ(r i−1 n i−1 , tx i 1 ) r i j = γ(r i j−1 , tx i j ) ∀ j ∈ 2…n i Then Γ executes it, applying its transactions in order through γ : Γ(s i−1 , b i ) = r i n i ≡ s i . Ch. 7
locally valid
With b i−1 the replica's last known block, b i is locally valid if ph i ≡ H(b i−1 ) h i ≡ h i−1 + 1 ≡ i ts i − ts i−1 ∈ [Δt − ε ; Δt + ε] ( Δt , ε chain-specific) r i 1 = γ(r i−1 n i−1 , tx i 1 ) r i j = γ(r i j−1 , tx i j ) ∀ j ∈ 2…n i Ch. 7
With H the domain of events and T the domain of logical time, a logical clock is a function C : H → T satisfying the monotonicity property called the clock consistency condition : ∀ a, b ∈ H : a → b ⇒ C(a) < C(b) If the implication also holds backwards, the system of clocks is strongly consistent : ∀ a, b ∈ H : a → b ⇔ C(a) < C(b) Ch. 2
M
Maintainability
Maintainability : how easily a failed system can be repaired. Closely related to availability: a highly maintainable system may also be highly available. Ch. 4
manifest
(the slides' first one is a single-container nginx:1.14.2 Pod on port 80). Required fields: apiVersion : the version of the Kubernetes API to use. kind : the type of object. metadata : data that uniquely identifies it (name, UID); labels too. spec : the desired state, with a format specific to each kind. Ch. 9
Marker
Initiation. Any process can initiate: it takes a local checkpoint, sends a Marker on all its outgoing channels, and moves to Checkpointing. Ch. 4
Mathematical morphology
Mathematical morphology (MM) analyses shape and spatial information, as in image processing; any mathematical theory of shapes can contribute to it. Ch. 3
maximum skew rate
Manufacturers specify a maximum skew rate ρ . A clock works within its specification when Ch. 2
Message-passing view [Coulouris et al., 2012]
A distributed system is “one in which components located at networked computers communicate and coordinate their actions only by passing messages”. It stresses physical distribution , interaction (network-based communication and coordination), and uncoupling in terms of control . Ch. 1
middleware
The architectural answer is middleware , a layer extending over multiple machines and offering each application the same interface [Tanenbaum & van Steen, 2017]. Ch. 1
Middleware (traditional definition) [Tanenbaum & van Steen, 2017]
Middleware lies in the middle between the operating system and the applications: vertical layers , with top (middleware-to-application) and bottom (middleware-to-OS) interfaces. Ch. 7
Migration
Migration : hide the change of location of a resource. Ch. 1
Monotonic reads
Monotonic reads . If a process reads the value of a data item x , any successive read operation on x by the process will always return that same value or a more recent value. Example: a distributed e-mail database; mail you have seen does not vanish when you reconnect elsewhere. Ch. 5
Monotonic writes
Monotonic writes . A write operation by a process on a data item x is completed before any successive operation on x by the same process. Idea: the order of updates is maintained over distributed replicas. Example: a software library under development, where each new version builds on the previous one. Ch. 5
MTBF
MTBF , Mean Time Between Failures: just MTTF + MTTR. Ch. 4
MTTF
MTTF , Mean Time To Failure: the average time until the system fails. Ch. 4
MTTR
MTTR , Mean Time To Repair: the average time needed to repair it. Ch. 4
Multi-Paxos
Multi-Paxos runs one separate, indexed Paxos instance per array entry, Ch. 6
N
nested transaction
A nested transaction is made of subtransactions, arbitrarily deep. Ch. 1
network effect
For infrastructure the key issue is the network effect : the value of a technology grows with the number of its adopters . Ch. 7
network is partitioned
“When a network is partitioned , all messages sent from nodes in one component of the partition to nodes in another component are lost.” “And, any pattern of message loss can be modelled as a temporary partition separating the communicating nodes at the exact instant the message is lost.” Ch. 5
Network partition [Gilbert & Lynch, 2002]
“When a network is partitioned , all messages sent from nodes in one component of the partition to nodes in another component are lost.” “And, any pattern of message loss can be modelled as a temporary partition separating the communicating nodes at the exact instant the message is lost.” Ch. 5
nodes
A Kubernetes cluster consists of a control plane plus a set of worker machines, called nodes . Ch. 9
notary service
Accept only correctly signed events and you get a notary service : who did what and when , with non-repudiation. Ch. 7
NTP
The standard example is NTP (Network Time Protocol, v4 in RFC 5905): a time server holds global absolute time and other machines synchronise to it. Ch. 2
O
Observability [Matteini, 2025]
An observable system allows understanding what happened, or what is happening, inside it. Ch. 9
observable
An observable system allows understanding what happened, or what is happening, inside it. Ch. 9
Openness
Openness is the property of a system to work with a number and sort of components not set once and for all at design time. Ch. 1
Operational vs axiomatic M9 · roughly speaking
Structural laws are the axioms that allow system properties to be proven . Transition rules give an operational representation suitable as a reference for implementation . When transitions are defined so as to abide by the structural laws , in principle we have an implementation with formal properties . Ch. 8
Optimistic
Optimistic . To reduce latency, nondeterministic events go first to volatile memory, then asynchronously to stable storage. A failure may lose some messages permanently, forcing a rollback to a state earlier than the one at failure. Ch. 4
Order-Execute
Storage is like an object's fields, code like its methods. γ now creates an SC on deploy , updates its state on invoke , updates both balances on transfer ; Γ still executes a block's transactions sequentially. This is the Order-Execute architecture [Androulaki et al., 2018]. Ch. 7
orphan message
A message received inside but sent outside is an orphan message , an effect without its cause: scenario (a). Ch. 4
orphans
Branches never grow at the same speed, so one gets longer and the other is abandoned, its blocks becoming orphans . Ch. 7
Output commit problem C2 · Models
Once the system emits an output to the outside world (e.g. its clients), part of its state becomes observable: a sort of commitment. Recovery must keep the outside view consistent, yet the outside world cannot be relied upon for recovery. This is the output commit problem : enough recovery information must be logged before the system commits to an output message. Ch. 4
P
parallel computation
Given a computational system, we talk of parallel computation whenever the temporal context is the same for all computational processes: one T for all. A parallel system is a computational system performing parallel computations. Ch. 1
Parallel computation & system M2 · course definition
Given a computational system, we talk of parallel computation whenever the temporal context is the same for all computational processes: one T for all. A parallel system is a computational system performing parallel computations. Ch. 1
Paxos
Paxos implements fault-tolerant consensus on a single value. Ch. 6
Pessimistic
Pessimistic . A received message is logged synchronously, before it is executed. Ch. 4
The process of ensuring that physically distributed processors have a common notion of time. Ch. 2
Piecewise deterministic assumption [Zhao, 2014]
Each state evolves deterministically until a nondeterministic event happens, such as the reception of a message. All nondeterministic events can be identified. Enough information is logged for each event. Ch. 4
Pod [Matteini, 2025]
Pods are the smallest deployable units: a group of one or more containers with shared storage and network resources. The shared context is a set of Linux namespaces, cgroups and potentially other facets of isolation, as for a container. Ch. 9
Pods
Pods are the smallest deployable units: a group of one or more containers with shared storage and network resources. The shared context is a set of Linux namespaces, cgroups and potentially other facets of isolation, as for a container. Ch. 9
Portability
Portability : how far an application, or a portion of it, can be moved to a different distributed system and keep working. Ch. 1
process algebra
A process algebra is a formal description technique for complex computer systems, especially those with communicating concurrently-executing components. Ch. 8
Process algebra, historically [Baeten, 2005]
Process algebra can be seen as the study of the behaviour of concurrent/distributed systems by algebraic means. Ch. 8
Process model for code migration [Fuggetta et al., 1998]
A process can be thought of as three segments: Code segment : the set of executable instructions of the process. Execution segment : the store for the execution state of the process, with private data, stack and program counter. Resource segment : the set of references to the external resources the process needs, like files, printers, devices, other processes. Depending on which portion of a … Ch. 3
Process replication
Process replication replicates processes in a mobile setting, which may require cloning or higher-level mechanisms such as goal-passing ( Ch. Ch. 5
Process, algebra, calculus · process algebra [Bergstra et al., 2001]
A process is a series of actions or events. An algebra is a calculus of symbols that combine according to certain defined laws. A calculus is a system or method of calculation. A process algebra is a formal description technique for complex computer systems, especially those with communicating concurrently-executing components. Ch. 8
Proof-of-Work
Proof-of-Work (PoW), or mining, was conceived against email spam [Back, 2002]; nowadays it endows cryptocurrencies with their value. PoW = computational puzzle + branch resolution strategy. Ch. 7
Proposer
Proposer : submits proposed values on behalf of clients. Ch. 6
publish/subscribe
Main example: publish/subscribe , where publishers publish events through the middleware and subscribers receive the events they subscribed to. Ch. 8
Q
quasi-Turing-complete
Computation's economics enter SC design, and SCs are not really Turing-complete: quasi-Turing-complete [Wood, 2014]. Ch. 7
quiescent point
Phase one creates a quiescent point of the system state; phase two atomically moves from the old checkpoint to the new one. Ch. 4
Quorum
Quorum : once a bare majority of acceptors accepts a value, it is chosen. Ch. 6
R
Read your writes
Read your writes . The effect of a write operation by a process on data item x will always be seen by a successive read operation on x by the same process. Idea: avoid the “web page failed update” effect. Example: updating a password. Ch. 5
Receiver-initiated migration
Receiver-initiated migration (the slide also says client-initiated ) starts at the target machine, which wants a new behaviour added: Java applets, JavaScript chunks. Few client resources need securing and clients may be anonymous: a less complex scheme. Ch. 3
reconciliation loop
That last sentence is the whole machine. A controller runs a loop that never ends: observe spec and actual state, compute the difference , take an action that shrinks it (create a Pod, delete one, bind one to a node), repeat . This is the reconciliation loop . Ch. 9
record of intent
An object is a record of intent . Once it is created, the system constantly works to ensure that it exists. Creating it tells Kubernetes what the cluster should look like: its desired state . Ch. 9
referentially uncoupled
Processes are referentially uncoupled when they communicate without referencing or knowing each other; the slides pair this with being uncoupled in space. Ch. 8
Reliability
Reliability : the system can run continuously without failure. It is defined over a time interval , not an instant. Ch. 4
Strong mobility can also be supported by remote cloning : an exact copy of the process runs on the target machine in parallel with the original, as when a UNIX process forks a child that executes on a remote machine. Ch. 3
Replica management
Replica management has two subproblems, and they are not the same problem: Placing replica servers : where the machines that host replicas go. Ch. 5
ReplicaSet [Matteini, 2025]
A ReplicaSet manages the number of replicas of a Pod, scaling them up and down to guarantee the availability of a specified number of identical Pods. It creates new Pods from its Pod template , and is usually managed through a Deployment. Ch. 9
Replication
Replication : hide that a resource is replicated. Ch. 1
requests
A container spec gives image , command , exposed port and protocol . The resources field manages hardware: requests is the CPU/memory Kubernetes guarantees to the container (the scheduler places Pods by it), limits the maximum it can use. CPU is in millicpu (0.1 CPU = 10% = 100m ), memory in bytes. Ch. 9
resource
Physically distributed resources should be available as if they belonged to one system. Ch. 1
Resource segment
Resource segment : the set of references to the external resources the process needs, like files, printers, devices, other processes. Ch. 3
rollback recovery
Both rely on rollback recovery : going back to the most recent recorded correct state. Ch. 4
rollout
Changing the image in the template ( kubectl set image , or re-applying an edited manifest) starts a rollout : the Deployment creates a new ReplicaSet and scales it up while scaling the old one down. Ch. 9
S
Safety
Safety : when the system temporarily fails, nothing catastrophic happens. Hard to define and to ensure; catastrophic basically means there is no established path from fault back to normal operation . Ch. 4
scalability
World-wide scale changes everything: few realistic assumptions can be made at design time about a system's “size”, in number of components or in geographical spread. The scalability dimensions [Neuman, 1994]: a system scales up when Ch. 1
Sender-initiated migration
Sender-initiated migration starts where the code resides or runs: search-bots, mobile agents. Servers should know clients and secure their resources: a more complex interaction scheme. Ch. 3
Sequential consistency [M3, after Tanenbaum & van Steen, 2017]
Main idea: all update operations are seen by all processes in the same order. A data store is sequentially consistent when the result of any execution is the same as if the (read and write) operations by all processes on the data store were executed in some sequential order , and the operations of each individual process appear in this sequence in the order specified by its program . Ch. 5
sequentially consistent
A data store is sequentially consistent when the result of any execution is the same as if the (read and write) operations by all processes on the data store were executed in some sequential order , and the operations of each individual process appear in this sequence in the order specified by its p Ch. 5
Service [Matteini, 2025]
A Service is an abstraction defining a logical set of Pods and a policy to access them: the entry point of the application. Pods are ephemeral, move between nodes and change IP; a Service gives a stable endpoint (IP address and DNS name) for the Pods matching its label selector. Ch. 9
Service replication
Service replication replicates functions, for the same reasons, which may or may not rely on the same data store: two layers, each with its own consistency and replication model. Ch. 5
single point of trust
Run as one logically centralised server (validating events, keeping the chain, storing data), even a redundant one, the notary has a single point of trust : its owner may alter the ordering or timing of events, or exclude someone, with no defence. Ch. 7
Situated computation
Situated computation [Suchman, 1987]: the environment is relevant or essential, the environment being any meaningful combination of temporal and spatial features with the resources required. Ch. 1
situated distributed systems
Situated computation : computation occurring locally where either perception or action is taking place, elaborating on perception, driving action, or both. When system requirements mandate situated computations within a distributed physical environment, situated distributed systems are the only way out. Ch. 3
Situatedness [Suchman, 2007]
Situatedness is the property of systems of being immersed in their environment: of being capable of (timely) perceiving and producing environment change, by suitably dealing with environment events. Ch. 1
Smart contract [Szabo, 1997]
Smart contracts (SC) are stateful, user-defined, reactive, immutable (therefore trustable), deterministic processes executing replicated and expressive computations on the blockchain. Stateful : encapsulate their own state, like objects. Reactive : only triggered by some off-chain client. User-defined : users deploy their own, with any business logic. Immutable : code cannot change after … Ch. 7
Smart contracts
Smart contracts (SC) are stateful, user-defined, reactive, immutable (therefore trustable), deterministic processes executing replicated and expressive computations on the blockchain. Ch. 7
Software architecture [Fielding, 2000]
A software architecture is an abstraction of the run-time elements of a software system during some phase of its operation. A system may be composed of many levels of abstraction and many phases of operation, each with its own software architecture. A software architecture is defined by a configuration of architectural elements (components, connectors, and data) constrained in their relationships … Ch. 8
Spatial computation
Spatial computation : the spatial features of the machine are relevant or essential. Ch. 1
spatial computer
A spatial computer (or spatial computing system) is a computational system where (the logic of) space is essential in representing the problem, defining the computation, and expressing the result. Ch. 3
Spatial computer · spatial computing [Beal et al., 2011]
A spatial computer (or spatial computing system) is a computational system where (the logic of) space is essential in representing the problem, defining the computation, and expressing the result. Spatial computing is any form of computation where (the logic of) space is relevant to express and perform computation. Ch. 3
Spatial computing
Spatial computing is any form of computation where (the logic of) space is relevant to express and perform computation. Ch. 3
Spatial computing languages
Spatial computing languages (SCL) bring space into programming languages, letting programmers deal explicitly with space-related aspects at the language level. Ch. 3
Spatial vs temporal contexts combined M2
Distributed parallel computing : S ≠ S′ , same T . Distributed concurrent computing : S ≠ S′ , T ≠ T′ . Ch. 1
spec
Almost every object has two nested fields. spec describes the characteristics you want: the desired state . status describes the current state, supplied and updated by Kubernetes. The control plane continually manages every object's actual state to match the desired state. Ch. 9
Spec and status [Matteini, 2025]
Almost every object has two nested fields. spec describes the characteristics you want: the desired state . status describes the current state, supplied and updated by Kubernetes. The control plane continually manages every object's actual state to match the desired state. Ch. 9
Stable storage
Stable storage is essential: it survives process failures, so its contents are available to the recovering process, and all checkpoints and logged messages must go there. Ch. 4
State M1 · System Models III
The state of a system at time t is the (minimum amount of) information that, together with knowledge of the dynamics of a (deterministic) system, allows an observer to completely describe the system's future behaviour from t on. Ch. 4
state intervals
Execution is modelled as consecutive state intervals , each started by a nondeterministic event (such as a message receipt) or by the process's initialisation, and followed by deterministic state changes. If the starting event is logged, the entire interval can be replayed . Ch. 4
state machine approach
Replication relates to consensus because all replicas of a resource must agree on the same state over time. The state machine approach is a general method for implementing fault-tolerant services in distributed systems. Ch. 6
State machine replication [Schneider, 1990]
Replication relates to consensus because all replicas of a resource must agree on the same state over time. The state machine approach is a general method for implementing fault-tolerant services in distributed systems. Ch. 6
State machine replication (SMR) [Schneider, 1990; Charron-Bost et al., 2010]
State machine replication : executing the same (not necessarily finite) state machine over multiple independent (possibly distributed) processors, in parallel, to achieve fault tolerance (to stops, crashes, lies, bugs), availability and reactivity, and data/software replication and untamperability. The replicas form a P2P network with the same observable behaviour and no assumed topology. Ch. 7
stateful
Computation is stateless when output depends on input only (functions), stateful when (Input, State) → (Output, State′) (objects). Ch. 7
stateless
Computation is stateless when output depends on input only (functions), stateful when (Input, State) → (Output, State′) (objects). Ch. 7
status
Almost every object has two nested fields. spec describes the characteristics you want: the desired state . status describes the current state, supplied and updated by Kubernetes. The control plane continually manages every object's actual state to match the desired state. Ch. 9
Strong mobility
Strong mobility transfers the execution segment along with the code segment: a process can be stopped, moved, and restarted on another machine. It is very demanding: the technological environment, typically the middleware, must allow for it. Ch. 3
structural operational semantics
Operational semantics: typically structural operational semantics (SOS) [Plotkin, 1981]. It describes the single-step execution capabilities of systems, so that terms of the algebra translate into labelled transition systems (LTS): states linked by transitions labelled with actions. Ch. 8
successful termination
Laws say which processes are equal; transition rules say what a process can do . Each rule reads “if the premises above the line hold, so does the conclusion below”. x a x′ means that x can execute a and then behave as x′ . The symbol ✓ means successful termination . Ch. 8
Sybil attack [Douceur, 2002]
In a Sybil attack , an attacker subverts the P2P system by creating a large number of pseudonymous identities, using them to gain a disproportionately large influence. Exposed: systems deciding by majority vote among entities with cheap-to-create IDs. Ch. 7
Synchronous
Synchronous : there is a bound Δ on message transmission delay and a bound Φ on the relative speed of processes, which allows accurate failure detection. Ch. 6
synchronous replication
Then an update must reach all copies before any subsequent operation: synchronous replication , whose result is informally called tight consistency . Ch. 5
System model refined · channel state [Zhao, 2014]
A set of N processes, each with a set of states (one of them initial) and a set of events that trigger its changes of state. A set of channels , each a uni-directional reliable communication channel between two processes (a TCP connection is two channels). The channel state is the set of messages in transit along the channel, not yet received by the target process. Ch. 4
T
Termination
For Paxos the slides use today's names. Agreement : no two processes decide differently. Validity : the decided value was proposed. Termination : every non-faulty process eventually decides. The first two are safety , the third liveness . Ch. 6
The blockchain at a glance C4, Background
A shared, transparent, distributed, append-only ledger tracking the order and timing of transactions: secured by cryptography (hashes, signatures, certificates, encryption); replicated on a P2P network, with no trusted intermediary, making it immutable; updated through consensus, robust to Byzantine failures. Ideal use: a secure hub for mutually-untrusted parties. Ch. 7
The problem of coordination [Omicini et al., 2001]
Governing interaction based both on time and on the nature of actions, aimed at achieving some global objective of the distributed system. Ch. 2
Theorem [Gilbert & Lynch, 2002]
“It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties: availability; atomic consistency — in all fair executions (including those in which messages are lost).” Ch. 5
tight consistency
Then an update must reach all copies before any subsequent operation: synchronous replication , whose result is informally called tight consistency . Ch. 5
Time model C3 · basic ontology
Synchronous : there is a bound Δ on message transmission delay and a bound Φ on the relative speed of processes, which allows accurate failure detection. Asynchronous : otherwise. This models unpredictable load on network and CPUs, where it is never possible to know whether a process has crashed or not . Ch. 6
Timed computation
Timed computation : the time of the machine is relevant or essential. Ch. 1
timer
A computer clock is really a timer : an oscillating quartz crystal with a counter and a holding register. When the counter reaches zero it raises an interrupt and reloads from the register. Each interrupt is a clock tick . Two quartz crystals never oscillate at exactly the same rate, which is why clocks drift. Ch. 2
timestamping service
Add timestamps and you get a timestamping service : blocks appended (almost) periodically, possibly several events per block, recording what happened and when . Ch. 7
Topological reading of modal operators [McKinsey & Tarski, 1944]
The modal operators are reinterpreted: □ (necessarily) as the interior operator , ◇ (possibly) as the closure operator of a topological space. The modal logic S4 [Bull & Segerberg, 1984] is sound and complete with respect to this topological semantics, and S4 is the modal logic of any Euclidean space. Ch. 3
They lack situatedness: data and computation are totally disembodied [Mariani & Omicini, 2013], like the cloud with no single point of trust. Ch. 7
TP monitor
An early solution was the TP monitor , letting an application access multiple database servers with transactional semantics. Ch. 1
transaction
A transaction is a proposed state change. Operations are application-specific, but must at least create and update assets; a cryptocurrency has deposit, Value and transfer, UserID, Value . Ch. 7
Transaction validity and execution C4, Transactions III–V
A transaction is valid if (i) it is well formed, (ii) the signature matches the issuer address, (iii) the signature certifies its integrity. A valid tx is applied by γ , giving its resulting state: γ(s, tx) = s′ Possibly s ≡ s′ (e.g. insufficient funds). γ(·,·) is the state machine (the program) being replicated . Ch. 7
transactions
Database operations are performed as transactions ; distributed databases need distributed transactions, with special primitives from the distributed or runtime system [Tanenbaum & van Steen, 2017]: BEGIN_TRANSACTION : mark the start of a transaction. Ch. 1
transition rules
Laws say which processes are equal; transition rules say what a process can do . Each rule reads “if the premises above the line hold, so does the conclusion below”. x a x′ means that x can execute a and then behave as x′ . The symbol ✓ means successful termination . Ch. 8
Transparency M4
Sometimes physical distribution is not a feature. Hiding non-relevant properties of the system's components and structure is called transparency . It gives users a higher level of abstraction. Its sorts are named by the property hidden. Ch. 1
U
uncoordinated checkpointing
In uncoordinated checkpointing , each process autonomously decides when to checkpoint. Ch. 4
uncoupled in time
They are uncoupled in time when they communicate without being active at the same time. Ch. 8
univalent
A configuration (all process states plus the messages in transit) is univalent (0- or 1-valent) if only one decision is still reachable from it, and bivalent if both are. Ch. 6
Universal State Machine Replication
Instead of a deterministic program with one business logic (say a bank ledger), replicate an interpreter , a program that executes other programs: Universal State Machine Replication (USMR), whose operations let users deploy, undeploy or invoke programs. Ch. 7
User's view [Tanenbaum & van Steen, 2017]
A distributed system is “a collection of independent computers that appears to its users as a single coherent system”. Observational and user-oriented: the computer scientist's definition. From an engineering viewpoint it is an a posteriori definition. Ch. 1
UTC
That standard is UTC , officially Coordinated Universal Time (the slides write “Universal Coordinated Time”). Ch. 2
V
Validity
For Paxos the slides use today's names. Agreement : no two processes decide differently. Validity : the decided value was proposed. Termination : every non-faulty process eventually decides. The first two are safety , the third liveness . Ch. 6
Vector clock [Kshemkalyani & Singhal, 2011]
For a system of n processes, a vector clock is an array of n logical clocks, one per process. It assumes n is known ; smaller vectors are possible, but the properties are proven for n . Process p i keeps a vector vc i in which: vc i [i] is the number of events that have occurred so far at p i : its own scalar clock; vc i [j] = k means that p i knows at least k events have occurred at p j : p j 's … Ch. 2
Vector order & strong consistency
vc(a) < vc(b) ⇔ ∀i vc(a)[i] ≤ vc(b)[i] ∧ ∃i′ vc(a)[i′] < vc(b)[i′] This relation is antisymmetric and transitive, subsumes simple logical clocks, and captures causality: vc(a) < vc(b) ⇔ a → b So vector clocks are strongly consistent , even though the order on vectors is not total. When neither vector is below the other, the events are concurrent. Ch. 2
virtual organisation
In a grid , resources from different organisations are brought together for collaboration across organisational boundaries, as a virtual organisation : people from existing organisations accessing resources (servers, databases, disks, …) made available by the participants. Ch. 1
Virtual reality [Fuchs et al., 2011]
Virtual reality is a scientific and technical domain that uses computer science (1) and behavioural interfaces (2) to simulate in a virtual world (3) the behaviour of 3D entities, which interact in real time (4) with each other and with one or more users in pseudo-natural immersion (5) via sensorimotor channels. Ch. 3
W
Weak mobility
Weak mobility is the bare minimum: only the code segment is transferred, possibly with initialisation data. The code runs ex novo every time: no computational context matters, or the one needed is the target's. The only requirement is that the target can execute the code, so it is very simple. Ch. 3
world state
The world state is a set of assets with owners; AssetState is application-specific (a balance, custom data). Implementations: account-based (Ethereum), UTXO (Bitcoin), versioned key-value store (Fabric). Ch. 7
Writes follow reads
Writes follow reads . A write operation by a process on data item x following a previous read operation on x by the same process is guaranteed to take place on the same or a more recent value of x that was read. Idea: writes affect only up-to-date data items. Example: comments to posts on Facebook. Ch. 5