What exactly makes a computational system distributed, and what should a distributed system achieve to be worth its cost?
Computation is now pervasive and physical, so systems spread in space and time: events are no longer totally ordered, and there is no system time or location. A computational process runs in a context (machine, resources, time, space); a system is parallel when all its processes share one temporal context, concurrent when at least two do not, distributed when at least two have different spatial contexts. The classic definitions see it from outside (users see one coherent system) or inside (a designer conceives one). Distributed systems are easy to misbuild (Deutsch's fallacies), so distribution must pay through its goals: resource availability, transparency, openness, scalability and situatedness. Three classes of systems emerged (computing, information, pervasive); today's systems borrow from all three.
Computational systems are pervasive: everywhere, and at the core of almost every artificial system, so how we engineer them shapes the engineering of nearly everything artificial. We live in an “ever-expanding computational bubble” of distributed, concurrent computations, triggered or autonomous, at home, in cars, hospitals, stations and public spaces. Devices continuously interact with humans, with each other, and with the physical environment and its resources.
The physical nature of artificial systems adds complexity: distribution, spatial and temporal, and the unpredictability of the environment.
What is spatially distributed [M0]
What is temporally distributed is, basically, events: they no longer happen in a clearly ordered sequence, and before/after cannot be applied to many pairs of them. The spatio-temporal unity of the system is lost: there is no system time and no system location, and components are only partially correlated. So events no longer form a totally ordered set: in general, partial ordering is all we get (Ch. 2). And admissible interactions no longer depend on compresence in space and time, within the same physical or virtual topology.
Why pay that price? We need distributed systems for [Ghosh, 2014]:
The trade-offs, in Puder et al.'s [2005] comparison:
| Criterion | Centralised | Distributed | Favours |
|---|---|---|---|
| Economics | low | high | distributed (price / performance) |
| Availability | low | high | distributed |
| Complexity | low | high | centralised |
| Consistency | simple | difficult | centralised |
| Scalability | poor | good | distributed |
| Technology | homogeneous | heterogeneous | centralised |
| Security | high | low | centralised |
The more components, the greater the risk that one failing hurts the rest, unless special measures are taken.
Building artificial systems today means building distributed systems with a computational core. Modelling them raises new theoretical problems (computer science); building them, new practical ones (computer engineering). The course mixes both from the start.
Impossibility results are theorems: they define the field by delimiting its admissible “moves”, and theorems need a shared ontology, notation and notion of proof. Brewer's theorem [Brewer, 2000] was stated without a proper proof; a first proof, with some limitations, came later [Gilbert & Lynch, 2002] (Ch. 5). The “hundreds of impossibility results” [Fich & Ruppert, 2003] use heterogeneous notations, ontologies and notions of proof: nothing like mathematics. So, do we know what computer science is?
The foundational questions: what is science, engineering, a machine, a computer, a system, a computational system, computer science, computer or software engineering, computation? Science is “the pursuit and application of knowledge and understanding of the natural and social world following a systematic methodology based on evidence” (Science Council). It observes phenomena and seeks the noumena (Kant's thing-in-itself) that explain them, preferring models with fewer assumptions that explain more, and that predict (the Higgs boson, predicted in 1964, observed in 2012). “There are computers. Ergo, computer science is the study of computers” [Newell et al., 1967], though “computer” keeps changing meaning. Whatever a computer is, it computes: computation is the noumenon at the core of the field, whose definition moved with it [Denning, 2008]:
Asking “what is computation?” too rigidly may be harmful [Freeman, 2011], yet it is the question to ground distributed systems on. Computation is symbol manipulation: simple, well-defined steps, each transforming symbols into symbols [Conery, 2010]. Computation is process, and every process is a computation [Frailey, 2010]. When defining it [Denning, 2011]:
Turing's and von Neumann's machines are artificial, discrete and single-device: do they fit natural, continuous computations, and systems? A machine's state at t is whatever is needed to understand its evolution after t, given input or, more generally, its context. A computing machine is cognitive, with information as input and output, and its context is an open question. So the slides abstract from machinery to the 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.
What context is, when computation is concerned [M2]
Context must be represented whenever any of these matters to understanding the process's dynamics. Hence three sorts of computation:
In a computational system, two or more computational processes behave (by computing) and work together (by interacting).
How do we represent the context of a whole system?
The choice of the sort of context defines the sort of system: parallel, concurrent, distributed.
The literature is loose. Parallel computing: more than one computation performed at the same time [Shonkwiler & Lefton, 2006], typically on multi-core architectures, for computationally intensive problems. Concurrency has two meanings [Degano & Montanari, 1987]: interleaving (events of separate processes may occur in any relative order; temporal and causal relations are not relevant) and true concurrency (partial orders capture those relations). The point is ordering: in parallel systems events are totally ordered, in concurrent ones at most partially ordered. The temporal context sets the difference.
Distributed computing: asynchronous processes on different devices, communicating by message passing, no shared memory [Kshemkalyani & Singhal, 2011]; “an activity that is performed on a spatially distributed system” [Lamport & Lynch, 1990]. Distributed systems: devices working together through a network (§3). One focuses on the spatial distribution of processes, the other of devices: the spatial context defines both.
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.
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.
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.
Distributed parallel computing: S ≠ S′, same T.
Distributed concurrent computing: S ≠ S′, T ≠ T′.
Read them literally. Parallel and concurrent are told apart by T alone: “one T for all” and “at least two different Ts” exclude each other. Distributed is about S, so it combines with either. One differing pair suffices. Distributed concurrent computing is the general case, the one Ch. 2 starts from. These reference definitions exist “to navigate literature fruitfully, against all odds”.
Give each process a spatial and a temporal context, or load one of the four combinations. The classifier applies the M2 definitions and names the pair that decides.
M4 presents the classic definitions: different, but converging.
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.
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.
Both describe a multiplicity of independent or autonomous entities (computers, microprocessors, …), with no focus on processes or devices and no assumption on their nature, structure or behaviour, hence heterogeneity, seen as one coherent system by users, engineer, or both.
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.
Two issues follow. Collaboration: for coherence, autonomous entities must work as a single system. Amalgamation: for uniformity, heterogeneous entities must look like one. Is there a general solution?
The architectural answer is middleware, a layer extending over multiple machines and offering each application the same interface [Tanenbaum & van Steen, 2017]. The slides' old vs new caution: this extends the old interpretation of non-distributed systems, good for preserving good habits, bad when looking for new ideas and new problems. Through separation, middleware addresses both issues:
Why build a distributed system? It is easy: components are easy to find and put together somehow. But at first sight distribution introduces problems rather than solving them, and making the system actually work is hard. The classic pitfalls, due to L. Peter Deutsch, as reported by Tanenbaum & van Steen [2017]:
False assumptions made by first-time developers (L. P. Deutsch)
These assumptions typically produce all the mistakes in engineering distributed systems. They concern properties unique to distribution (network reliability, security, heterogeneity, topology, latency, bandwidth, transport costs, administrative domains) that rarely show up in non-distributed systems.
Each scenario is a design that breaks in production. Pick the false assumption behind it.
M4's four classic goals, plus a fifth:
The deck's conclusion adds a caveat: “even though nowadays it is much about robustness, reliability, fault tolerance” (Ch. 4).
Resource availability. Physically distributed resources should be available as if they belonged to one system. A resource is anything that could be connected to a computational system and that anyone could legitimately use: printers, scanners, storage, distributed sensors. Distributed systems thus enable sharing, information exchange and collaboration, as grid systems do [Foster et al., 2001] (§9).
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.
Types of transparency in a distributed system
Access hides heterogeneity in data representation, component structure and resource interfaces or protocols, giving uniform access. Location: where a resource sits (a storage facility, one printer among a lab's printers) often does not matter to its users, nor where users are to the resource. Naming is essential: logical identifiers not bound to physical location, such as URLs.
Migration and relocation. Resources move, and so do users (once secondary, user mobility is now a core issue); coherence and functionality must survive. Relocation transparency is a specialised, online version of migration transparency: access continues while the resource moves. Replication gives local copies (less bandwidth, faster access) and redundancy against failures; replicas should share one name and essentially one state, so as to look like one thing.
Concurrency. Autonomous users may use the same resource at once, and nobody needs to know that “another user is accessing the same database you are accessing just now”. Shared access can be cooperative, but often it must be competitive: the system defines access policies for concurrent sharing, transparently, and keeps the resource consistent (Ch. 5).
Failure. “You know you have [a distributed system] when the crash of a computer you've never heard of stops you from getting any work done” (L. Lamport). A failure can occur anywhere, but part of the system probably keeps working: partial failure is much better than the total failure of a centralised system. Failure transparency means masking failures under realistic assumptions. It is hard because of latency: is a silent resource dead or just very slow? Is silence slowness, deliberate choice, resource failure or network failure? (Ch. 4)
Hiding is not always best. Hide time zones from travelling users and a download may end before it started. You may want to know whether the server holding the new Ultra HD Pokémon movie is in the US, Japan or Europe, unless replication makes it irrelevant. The trade-off usually concerns performance, but not only: location-awareness is often a feature. Engineers must choose the degree of transparency, weighing performance, understandability and more.
Which transparency is at work in each scenario? One of them is a case where hiding would be the mistake.
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. Open systems are designed to be open, and are fundamentally unpredictable. Designing over unpredictability requires predictable items shared a priori, such as standard rules for service syntax and semantics and for message interchange. Interfaces specify how to access services, and IDLs how interfaces are specified; but they capture syntax rather than semantics, often not even the protocol. Three non-functional issues:
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
Scalability is an issue whenever any dimension of a distributed system changes its order of magnitude. Size is limited by centralisation [Tanenbaum & van Steen, 2017]:
Centralisation is sometimes necessary: security or normative requirements may impose a single server, insecure replication a single data collection, and the most efficient algorithm may be centralised. Still, it hinders scalability. Raynal [2013]: a centralised algorithm makes data flow from the whole network to one place and back, overloading the network, and any transmission problem harms the whole algorithm, so “only decentralised algorithms should be used in distributed systems”. Their features [Kshemkalyani & Singhal, 2011]:
Geographical scalability has three basic techniques [Neuman, 1994]:
apice.unibo.it): naming without centralisation.Both create consistency problems. Copying in a distributed setting makes inconsistency technically unavoidable; the question is how much can be tolerated and hidden (Ch. 5).
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.
Not a classic goal: mobile, adaptive and pervasive computing made it key [Zambonelli et al., 2015]. Systems are increasingly affected by their physical nature, not through a lack of abstraction (hardware and software layers are cleanly separated) but through increasingly complex requirements that mandate ever-increasing context-awareness [Baldauf et al., 2007]. Context is hard to define [Omicini, 2002], and its boundaries blur with environment, as multi-agent systems show [Weyns et al., 2007].
Mobile computing showed that systems need at least awareness of the spatio-temporal fabric: where and when they work. Any environment is first of all space and time, “what we call temporal and spatial context”: the T and S of §2. More generally, a system must understand its environment: its nature, structure, available resources, and the issues that may harm it. 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.
When requirements mandate situated computations in a distributed physical environment, situated distributed systems are the only way out: disaster recovery, environmental monitoring, crowd steering, live events. Openness copes with the unpredictability of complex environments, scalability with their growing complexity (Ch. 3). M4's open questions: what is middleware? Are we ready for the general notion of resource, and for situatedness? Where does IoT fit?
Distributed systems are not new, and today they are so diverse that classifying them all is neither easy nor useful. But over the first decades, changing needs and resources produced three recognisable classes:
| Class | Main characteristic | Kinds in the slides |
|---|---|---|
| Distributed computing systems | many distributed computers performing high-performance tasks | cluster, grid |
| Distributed information systems | integrating separate networked applications | transaction processing, EAI |
| Distributed pervasive systems | instability as the default condition | home, health care, sensor networks |
A cluster is a collection of similar workstations or PCs, running the same OS, in the same area, on a high-speed LAN. Building a supercomputer from many simple computers is cheaper than buying a high-performance one, more robust, and easier to maintain and grow. Clusters serve parallel computing: typically one computationally intensive program runs in parallel on many machines. Beowulf clusters are Linux-based, with compute nodes controlled and accessed by a single master node. Clusters are homogeneous; grids are typically heterogeneous.
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. Grids span different administrative domains by nature.
Grid layers [Foster et al., 2001]
These arose from separate networked applications that had to be integrated despite structural interoperability problems. Non-interoperating servers shared by many clients, with distributed queries and transactions, give transaction processing systems. Sophisticated applications (processing components, not only databases) that must communicate directly give Enterprise Application Integration (EAI).
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.END_TRANSACTION: terminate the transaction and try to commit.ABORT_TRANSACTION: kill the transaction and restore the old values.READ: read data from a file, a table, or otherwise.WRITE: write data to a file, a table, or otherwise.ACID properties
A nested transaction is made of subtransactions, arbitrarily deep. The whole must be ACID: if a subtransaction fails, all those so far are undone, even if committed, so durability refers to the top-level transaction. The solution is a private copy of the world: subtransactions stay ACID on a copy, and only when the whole succeeds does the transformed copy become the world. Distributed transactions are nested transactions whose “leaves” are ordinary single-server transactions. An early solution was the TP monitor, letting an application access multiple database servers with transactional semantics.
EAI integrates at the application level too: process integration beyond data integration, with middleware as a communication facilitator between applications.
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.
Requirements for pervasive systems [Grimm et al., 2004]
Home systems cannot expect competent administrators, so they must be self-configuring and self-maintaining, and they manage heterogeneous personal information from inside and outside the home. Health care systems are built around a Body Area Network, minimising impact on the person (not preventing free motion). Their questions:
Sensor networks are an enabling technology: tens to thousands of spatially distributed sensing nodes acquiring, processing and transmitting environmental information, viewable as a distributed database queried over time. Both extremes, sensors sending everything in without cooperating or computing everything themselves, cost too much network or node power. The solution is in-network data processing: a tree among sensors, queries passed through it, results aggregated at each level. Open questions:
Today's complexity calls for community efforts, especially for critical infrastructure, and open software is the default: follow community projects, take part, and select components wisely. Sources include the Apache Software Foundation, the Cloud Native Computing Foundation (CNCF), the Free Software Foundation and the Python Software Foundation.
The CNCF, part of the Linux Foundation, promotes projects as the foundation of cloud native computing (graduated, incubating, sandbox or archived by stage), including Kubernetes (Ch. 9), etcd and Prometheus. Its charter:
Cloud native technologies empower organizations to build and run scalable applications in modern, dynamic environments such as public, private, and hybrid clouds. Containers, service meshes, microservices, immutable infrastructure, and declarative APIs exemplify this approach.
These techniques enable loosely coupled systems that are resilient, manageable, and observable. Combined with robust automation, they allow engineers to make high-impact changes frequently and predictably with minimal toil.
The Cloud Native Computing Foundation seeks to drive adoption of this paradigm by fostering and sustaining an ecosystem of open source, vendor-neutral projects. We democratize state-of-the-art patterns to make these innovations accessible for everyone.
The three classes roughly tell the story of distributed systems' evolution, shaped by environment, goals and technology, each calling for different models, methodologies and technologies. Today's systems typically borrow features from all three.
Practise each out loud in two minutes, about your own system.
Each worker is a BEAM node in its own container, reachable only by messages: different spatial contexts (S ≠ S′), and the design must not rely on Compose placing them on one host. Events on different workers are ordered only through messages, a partial order: different temporal contexts (T ≠ T′). So: distributed concurrent computing. Work split across machines is not M2's “parallel”, which needs one T for all.
Tanenbaum's is observational: the system appears as one (a posteriori). The engineer's is constructive: entities conceived as one (a priori). Coulouris' stresses physical distribution, messages only, uncoupled control. Thunk fits all three.
Reliability (lost steal requests or results, hence re-execution), latency (a steal costs a round trip, so small tasks are not split further), topology (dynamic membership). Name the ones you deliberately ignore, e.g. one administrator in a Compose cluster.
A dead resource and a very slow one look the same from outside. Transparency can only mask failures under realistic assumptions, e.g. a timeout after which work is re-executed, accepting that it may occasionally run twice.
No: security, normative requirements, insecure replication or efficiency can justify it. But it hinders scalability, and Raynal says only decentralised algorithms belong in distributed systems. Test your design against the four features of decentralised algorithms.
| Slides | Content | Here |
|---|---|---|
| M0 · Pervasive I–III, Physical vs comp. | Pervasiveness; distribution | §1 |
| M0 · Distribution I–III | Spatial, temporal; lost assumptions | §1 |
| M0 · Why DS I–II; Artificial I–IV | Puder; Ghosh; science + engineering | §1 |
| M2 · Prologue | Impossibility results | §2 |
| M2 · On CS; On computation | Science; Newell; Denning; computation; machines | §2 |
| M2 · Basic ontology | Process; context; sorts; computational system | §2 |
| M2 · Par./conc./distr.; Conclusion | Literature; definitions I–VI; combined cases | §2 |
| M4 · Definitions & issues | User's, engineer's, Coulouris' views; middleware; old vs new | §3 |
| M4 · Pitfalls | Deutsch's fallacies; remarks | §4 |
| M4 · Goals; resources; conclusion | Five goals; resources; lessons | §5 |
| M4 · Transparency | Seven types; failure; degree | §6 |
| M4 · Openness, Scalability | IDLs; issues; dimensions; decentralisation; techniques | §7 |
| M4 · Situatedness I–V, Sit. & DS | Context-awareness; KIE; open questions | §8 |
| M5 · Prologue; computing systems | Classes; cluster, Beowulf; grid layers | §9 |
| M5 · Information systems | Transactions; ACID; nesting; TP monitor; EAI | §9 |
| M5 · Pervasive; Nowadays; Conclusion | Grimm; home; health; sensors; CNCF | §9 |