Engineering Architecture

The ideas in the reading list, section by section: 59 references, 14 sections, 1914–2024

Six modern architectures: the Internet, platform-based chip design, layered control, facilitated variation in biology, ROS, three-layer robots. Eight historical foundations: cybernetics, general systems theory and hierarchy, software modularity, decomposition in optimization, complexity and organization, the org chart, business history, management consulting.

Each section opens with its references. Each content slide: figure first, then text; every symbol defined where it first appears.

What the list means by "architecture": the agreed, long-lasting modularity of a system

Clark's definition (Designing an Internet, 2018)

• architecture = the issues "on which we must all agree for the system to function", "the basic modularity of the system", the "long-lasting" aspects — a framework within which many designs are possible, not a specification

Matni, Ames & Doyle (2024)

• layers = a functional decomposition (decision, planning, control); levels = physical substrates (hardware, software); architecture is the arrangement of layers and the protocols between them

Recurring questions across the 59 references

• how to split a system into parts that can be changed independently

• what must stay fixed (protocols, interfaces, design rules) so that the rest can vary
• how one global problem decomposes into layers running at different rates

• how the organization that builds a system shapes the system's structure

Clark (2018) ch. 1–2; Matni, Ames & Doyle (2024) Part 3; section headings from the syllabus.

The 59 references by year and section

Figure: publication year of every reference (x axis) by section (rows, in deck order). Dot colour = section. Leader lines connect displaced labels to their dots. The modern sections cluster after 1984; the foundations run from 1914 (Brinton) to 2006 (DeLanda), with the densest decade 1960–1975.

Years from the reading list; one dot per reference.

Clark 1988: the Internet's goals were ranked, and the ranking fixed the architecture

Order is the design

• "these goals are in order of importance, and an entirely different network architecture would result if the order were changed"

Datagram

• "a building block, and not … a service in itself": no connection state in the switches, so any service can be built on top and any member network can carry it

Why TCP and IP are two layers

• goal 2 "caused TCP and IP, which originally had been a single protocol in the architecture, to be separated into two layers"; first drivers were XNET (a cross- Internet debugger) and "real time delivery of digitized speech"; UDP was created "to provide a application-level interface to the basic datagram service"

Costs of the ordering

• accountability and cost-effectiveness (goals 5, 7) were "perhaps less effectively met": headers are long, retransmission wastes bandwidth, host software is hard to write well

Clark, D. D. (1988). The design philosophy of the DARPA Internet protocols. SIGCOMM CCR 18(4), 106–114 (goal list abridged from §3).

Fate-sharing: keep the state of a conversation only where losing it would not matter

The rule

• "it is acceptable to lose the state information associated with an entity if, at the same time, the entity itself is lost"

Why it beats replication

• fate-sharing "protects against any number of intermediate failures, whereas replication can only protect against a certain number"
• it is "much easier to engineer"

Architectural consequence

• gateways keep no per-connection state → packets must carry enough to be routed alone → the datagram; the transport layer (TCP) at the hosts recovers from loss
• the two design results reinforce each other: goal 1 (survivability) and goal 3 (variety of networks) both point to a stateless network core

Clark (1988), §4 "Survivability in the face of failure".

The end-to-end argument: if a function needs the endpoints, the network cannot complete it

The argument (verbatim)

• "The function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the end points of the communication system. Therefore, providing that questioned function as a feature of the communication system itself is not possible."

The caveat

• "Sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement" — the argument is "a guideline", not "an absolute rule"; identifying the end points takes care

Other functions the paper works through

• delivery guarantees (an ARPANET RFNM says the message arrived, not that the target host acted on it), secure transmission, duplicate suppression, FIFO delivery, transaction management
• observed failure rate motivating the example: a gateway bug swapped bytes about once per million

Saltzer, J. H., Reed, D. P., & Clark, D. D. (1984). End-to-end arguments in system design. ACM TOCS 2(4), 277–288, §2 "careful file transfer".

Clark 2018: architecture is what all parties must agree on; the Internet's is an hourglass

Definition

• architecture = the issues "on which we must all agree for the system to function", "the basic modularity of the system", the "long-lasting" aspects; "a framework within which it is possible to design a system that meets these requirements", kept minimal

Requirements a design is judged by (ch. 2)

• fitness for purpose; generality; longevity; security; availability and resilience; management; economic viability; meeting the needs of society

Tussle (with Wroclawski, Sollins, Braden)

• stakeholders "have interests that may be adverse to each other, and these parties each vie to favor their particular interests"; design rules: "design for variation in outcome", "modularize the design along tussle boundaries", "design for choice"
• the book compares proposed alternatives (XIA, MobilityFirst, NDN, Nebula, ChoiceNet) against these requirements

Clark, D. D. (2018). Designing an Internet. MIT Press, ch. 1–2, 4; tussle: Clark, Wroclawski, Sollins & Braden (2002/2005).

Orthogonalization of concerns: function vs architecture, communication vs computation

Two separations

• orthogonalization of concerns = "the separation of the various aspects of design to allow more effective exploration of alternative solutions"; one pillar is the separation between "function (what the system is supposed to do) and architecture (how it does it)"
• the second: communication and computation — "Separating communication and behavior is essential to dominate system design complexity"

Platforms in this paper

• hardware platform = "a family of micro-architectures that allow substantial re- use of SW"; application software sees it through "a high-level interface … that we call Application Program Interface (API)"
• software platform (RTOS, drivers, network stack) wraps the hardware; "the combination of the HW and the SW platforms is called the system platform"
• the paper's Fig. 4 draws the platform as an hourglass whose waist is "API or Programmers' Model" — the same shape as the Internet's narrow waist

Keutzer, K., Malik, S., Newton, A. R., Rabaey, J. M., & Sangiovanni-Vincentelli, A. (2000). IEEE TCAD 19(12), 1523–1543, Fig. 1 and §II–III.

A platform is a library of components plus composition rules; design meets in the middle

Definitions (verbatim)

• "A platform is a library of components together with their composition rules. A design at each level of abstraction is a platform instance, i.e., a legal composition of a set of library elements."
• "A platform is simply an abstraction layer that hides the details of the several possible implementation refinements of the underlying layer."
• the tenet: "design as a meeting-in-the-middle process, where successive refinements of specifications meet with abstractions of potential implementations"

Benefits listed (§2)

• bounded design-space exploration; formal hand-off points between system and IC companies; reuse at every level; one framework for the whole process

Challenges listed

• "lack of precise definitions and characterization of platforms and of the associated design flow"; extending the method to network (§4) and analog (§5) platforms

Sangiovanni-Vincentelli, A., Carloni, L., De Bernardinis, F., & Sgroi, M. (2004). Benefits and challenges for platform-based design. DAC 2004, 409–414, Fig. 1 and §1–2.

Quo vadis, SLD? The meet-in-the-middle step repeats at every level of abstraction

What SLD is

• system-level design "means many things to different people since there is no wide agreement on a definition"; the 2004 ITRS roadmap places it above register-transfer level

Three challenges (§II.A)

• heterogeneity and complexity of the hardware platform; complexity of embedded software; integration complexity

The method

• "The PBD design process is not a fully top-down nor a fully bottom-up approach; rather, it is a meet-in-the-middle process"; function and architecture are "peers"
• "Hardware/software partitioning is not the essence of system design; rather it is a consequence of higher-level architectural decisions"
• platform = "a library of components that can be assembled to generate a design at that level of abstraction"; platform instance = "a set of components selected from the library whose parameters are set"

Sangiovanni-Vincentelli, A. (2007). Quo vadis, SLD? Proc. IEEE 95(3), 467–506, §II and Figs. 2–3.

The layered control architecture (LCA): three layers, three rates, one plant

• layers = functional decomposition (the three boxes); levels = physical substrates (hardware, software) — the paper keeps the two words distinct
• goal of the paper: "describe the universals of architecture and sketch tentative paths towards a useful design theory"
• the same pattern recurs outside control; Table 1 of the paper:

clothing

sensorimotor

power grid

garment, fabric, fibres, thread

nerve, muscle, axon, muscle fibre

grid, local distribution, lines, substations

Levels (physical)

inner (comfort), middle (insulation), outer (windproof)

economic dispatch, secondary and primary frequency control

Layers (functional)

goals, planning, reflex

warm vs waterproof vs soft

sustainable vs resilient vs efficient

Laws (tradeoffs)

speed vs accuracy

vision + reflex = fast, accurate motion

traditional + renewable + active control

Sweet spot

inner + middle + outer

Matni, N., Ames, A. D., & Doyle, J. C. (2024). IEEE Control Systems 44(3), 52–94 (arXiv 2401.15185), Fig. 2, Part 1, Table 1.

Layers are derived, not assumed: one synthesis problem, rewritten with redundant variables

Global synthesis problem (3): one controller for the full plant and the full task

introduce a coarse abstraction of the dynamics (an MDP over regions of the state space) and keep only the specification

Decision layer (8): plan on the abstraction

• the rewrite adds redundant variables (the abstract plan duplicates information already in the state) and then relaxes the consistency constraint that ties them together; the errors this introduces are what the lower layers must absorb
• "standard algorithms emerge naturally in an attempt to minimize the errors induced by these relaxations and decompositions" — the layers are the paper's result, not its starting point

Matni, Ames & Doyle (2024), Part 1: equations (3) and (8) of the arXiv version; symbol names as in the paper.

The planning and feedback layers absorb the errors the abstraction introduced

Planning layer (12): a finite-horizon optimal control problem on a reduced-order model, re-solved every τ steps

Feedback layer (15): track the reference on the true dynamics, at the fastest rate

• the abstraction error of the decision layer is paid for by the planning layer, the model error of the planner by the feedback layer; each layer solves a smaller problem at a higher rate than the one above it
• Part 2 of the paper then asks how the layers should be chosen: architecture design as multi-criterion optimization (next slide)

Matni, Ames & Doyle (2024), Part 1: equations (12) and (15) of the arXiv version.

Diversity-enabled sweet spots: the tradeoff between objectives shrinks when the layers share less

Definitions (§6.1–6.2), for a vector of d objectives

"if there exists an optimal point x* then σ = 0, and … σ increases as the tradeoff between objectives becomes more severe"

Theorem 2 (bi-criterion least squares)

• "the more diverse the matrices A₁ and A₂, i.e., the smaller the number of shared rows k, the less severe the tradeoff"
• diversity alone is not enough: the sub-tasks b₁, b₂ must be compatible with it — if b₁ = b₂ then even A₁ = A₂ gives σ = 0

Matni, Ames & Doyle (2024), §6: definition (43), problem (44), Theorem 2. Chart recomputed: m = 4, random palette of 8 rows, |b₁−b₂|ᵢ = 1.

Speed–accuracy tradeoff of one control loop: delay error plus rate error

Model [1]

• the loop sees the disturbance only after the net delay and through a channel of limited rate; a nerve with a fixed cross-section budget can be built from few large fast axons or many small slow ones, so rate and delay are tied (spike-based tradeoff, eq. [2])

Bound [4] (bottom left, tight)

• worst-case error ≥ delay error + rate error: the first term is what accumulates before the loop can react, the second is the quantization of the correction

Experiment

• steering-wheel trail-following game with added delay (−0.8 to 0.4 s; negative = extra look-ahead) and quantized control (1–7 bits); the additive form of the two errors was confirmed (four participants)

Nakahira, Y., Liu, Q., Sejnowski, T. J., & Doyle, J. C. (2021). PNAS 118(22), e1916367118, eqs. [1]–[4]. Chart recomputed with λ = 0.3 bit per time step and no internal delay.

Diversity-enabled sweet spot: two different layers beat any single component

Two loops, additive errors (eq. [6], bottom left)

• "errors from two control loops—one fast but inaccurate reflexive layer that corrects for bumps, and a planning layer that is slow but accurate—are additive"

The claim

• "diversity in the properties of neurons across layers helps to create 'diversity- enabled sweet spots,' so that both fast and accurate control is achieved using slow or inaccurate components"

Physiology cited

• vestibulo-ocular reflex ≈ 10 ms versus visual loop ≈ 100 ms; the fast layer uses few large axons, the accurate layer many small ones — the same hardware tradeoff realized twice with different budgets λ
• Matni–Ames–Doyle (2024) generalize the bound to an unstable plant x(k+1) = a x(k) + … (their Theorem 3), which reduces to [4] at a = 1

Nakahira et al. (2021), eq. [6] and Figs. 2B, 7. Chart recomputed with λ = 0.3, ε = 0.2, no internal delay; each layer picks its delay and rate on the line R = λ · delay.

Bowties and hourglasses: a few conserved protocols at the waist deconstrain everything else

Three universal constraint types

• "(i) component (garment) constraints, (ii) system (outfit) constraints, and (iii) protocol constraints"; layered architectures are "large/thin/nonconvex": many functional designs, a vanishing fraction of all configurations

Constraints that deconstrain

• "A robust architecture is constrained by protocols, but the resulting plug and play modularity that these shared constraints enable deconstrain … systems designed using this architecture"
• TCP/IP shows "how architectures that are well-designed for extreme robustness can create evolvability as a side benefit"

Where it fails

• "complexity is driven by robustness and not by minimal functionality"; robust mechanisms are "cryptic"
• "Because they are the fixed points in robust architecture, when protocols are subject to attack, the system can fail catastrophically": viruses hijack translation, addiction hijacks dopamine signalling
• counting argument (bottom left): n garments in g categories give nᵍ wearable outfits versus 2ⁿᵍ arbitrary heaps

Doyle, J. C., & Csete, M. (2011). Architecture, constraints, and behavior. PNAS 108(Suppl. 3), 15624–15630 (no figures in the paper; bowtie drawn from its text).

Csete & Doyle 2002: protocols over modules; feedback robustness is paid for elsewhere

Thesis (abstract)

• engineering and biology converge on "modular architectures that are composed of elaborate hierarchies of protocols and layers of feedback regulation, are driven by demand for robustness to uncertain environments, and use often imprecise components"

• "We claim that protocols are far more important to biologic complexity than are modules"; "If modules are ingredients, parts, components, subsystems, and players, then protocols describe the corresponding recipes, architectures, rules, interfaces, etiquettes, and codes of conduct"

Module, defined (five properties)

• identifiable interfaces (usually protocols); can be modified and evolved somewhat independently; facilitate simplified or abstract modelling; keep some identity when isolated or rearranged; derive additional identity from the rest of the system

Conservation of fragility (eq. 4, bottom left)

• "Robustness (log S < 0) is paid for by an equal fragility (log S > 0)"

• scale of the analogy: a Boeing 777 has "150,000 different subsystem modules" and "roughly 1000 computers"; E. coli ≈ 4000 genes, fewer than 300 essential

Csete, M. E., & Doyle, J. C. (2002). Science 295(5560), 1664–1669, Figs. 2–3 and eqs. 2, 4. Chart recomputed with k₁ = 0.01, k₂ = 0.1.

Layering as optimization decomposition: TCP and queue prices are one dual algorithm

Network utility maximization (NUM)

Dual function (multipliers on the capacity constraints), minimized over λ

• the dual separates by source: the rate update (bottom left) is TCP's window control and the price is the congestion signal (queueing delay for Vegas/FAST, loss probability for Reno)

Thesis (verbatim)

• protocol stacks "may instead be holistically analyzed and systematically designed as distributed solutions to some global optimization problems"; "Each decomposed subproblem in a given decomposition corresponds to a layer, and certain functions of primal or Lagrange dual variables (coordinating the subproblems) correspond to the interfaces among the layers"

• one generalized NUM (adding physical-layer resources, error probabilities, scheduling and routing) admits several decompositions — each a different allocation of functions to layers

Chiang, M., Low, S. H., Calderbank, A. R., & Doyle, J. C. (2007). Proc. IEEE 95(1), 255–312, §I–II. Chart: 3 sources on 2 unit-capacity links, logarithmic utilities, α = 0.1.

Evolvability: the properties that make random mutation less lethal and more productive

Definition (verbatim)

• "Evolvability is an organism's capacity to generate heritable phenotypic variation." It "may have two components: (i) to reduce the potential lethality of mutations and (ii) to reduce the number of mutations needed to produce phenotypically novel traits."

Conservation and deconstraint

• "Some processes have been highly conserved, not so much because they cannot change, but because they are flexible and robust mechanisms that support change and variability in other processes."

Can evolvability be selected for?

• the paper's answer: partly as a by-product of selection for robustness in individuals; buffered populations carry more hidden variation; possibly a clade- level advantage during radiations

Where it sits in the reading list

• the biological version of "constraints that deconstrain": a fixed, conserved core that makes everything built on it easy to vary

Kirschner, M. W., & Gerhart, J. C. (1998). Evolvability. PNAS 95(15), 8420–8427 (abstract and section headings).

Facilitated variation: regulatory change re-uses conserved core processes to make new traits

The claim (verbatim)

• "Most anatomical and physiological traits that have evolved since the Cambrian are … the result of regulatory changes in the usage of various members of a large set of conserved core components"

Why core processes facilitate variation

• they "(i) reduce the number of necessary genetic changes, (ii) increase the variety of regulatory targets for change, (iii) reduce the amount of lethality due to genetic change, and (iv) increase the amount of genetic variation carried in the population"

• "Although the core processes are constrained in their own change of function, they deconstrain regulatory change"

Mechanisms

• weak regulatory linkage: signal and response "interact indirectly through an intermediate agency" and "the output can be much more complex than the regulatory input"

• exploratory processes search large spaces by variation and selection (microtubules, axon guidance, immunity); compartmentation: ≈100 selector-gene compartments in an insect, ≈200 in a vertebrate — the conserved map between diversified processes "has been called the 'bowtie effect' by Csete and Doyle"

• The Plausibility of Life (2005) is the book-length statement; the 2007 paper is the authors' condensation

Gerhart, J., & Kirschner, M. (2007). PNAS 104(Suppl. 1), 8582–8589 (four steps, core-process properties, Table 1); Kirschner & Gerhart (2005). The Plausibility of Life. Yale UP.

Kashtan & Alon: modular networks evolve when the goals switch between shared sub-goals

Setup

• circuits of NAND gates on four inputs X, Y, Z, W; fitness = fraction of the 16 input combinations answered correctly; genetic algorithm with elitism, mutation probability 0.7 per genome, a penalty of 0.2 per gate above 11
• fixed goal: G₁ throughout; modularly varying goals (MVG): "we repeatedly switch between several goals, each made of a different combination of subgoals" — here G₁ ⇄ G₂ every E = 20 generations
• populations of 1,000 (Fig. 2) and 2,000 (six-input version), 300–500 elite carried over

What is being tested

• whether modular structure appears "spontaneously" from the evolutionary process itself, without any explicit reward for modularity; the only difference between the two conditions is whether the environment (goal) changes
• control: goals that switch between random functions with no shared sub-goals produce no modularity

Kashtan, N., & Alon, U. (2005). PNAS 102(39), 13773–13778, eqs. 1–4, Fig. 2, Methods.

Results: varying goals give modular networks, network motifs, and six-fold faster evolution

Modularity

• normalized modularity of logic circuits: 0.12 ± 0.02 (fixed) vs 0.54 ± 0.02 (MVG); neural networks 0.15 vs 0.35; biological reference values: E. coli transcription 0.54, C. elegans neurons 0.54, human signalling 0.58
• an initially modular circuit placed under a fixed goal loses its modularity "within a few tens of generations" (Fig. 3)

Speed

• generations to a perfect solution: 9,000 (fixed) vs 1,400 (MVG) for circuits — about six-fold; 21,000 vs 2,800 for neural networks
• after each switch the MVG population re-adapts "within about five generations"; solutions for G₁ and G₂ differ by two connections (one threshold in the neural case)

Motifs

• MVG networks contain the feed-forward loop and diamond motifs (bifan, diamond in neural nets); fixed-goal networks contain fewer

Reading it as architecture

• the environment that changes along module boundaries selects for interfaces that make each module replaceable — the simulation counterpart of weak linkage and compartmentation in the previous two slides

Kashtan, N., & Alon, U. (2005). PNAS 102(39), 13773–13778, Results, Figs. 1–5. Bars: values reported in the paper (medians over runs).

ROS (2009): a peer-to-peer graph of nodes exchanging typed messages, not an operating system

What it is

• "ROS is not an operating system in the traditional sense of process management and scheduling"; it is "a structured communications layer above the host operating systems"

Design goals (§II, headings verbatim)

• Peer-to-peer (lookup via "the name service, or master"); Multi-lingual (C++, Python, Octave, LISP); Tools-based ("microkernel design"); Thin ("standalone libraries that have no dependencies on ROS"); Free and Open-Source

Nomenclature (§III)

• nodes = "processes that perform computation"; a message is "a strictly typed data structure"; a topic is "simply a string such as 'odometry' or 'map'", many-to-many; a service is "a string name and a pair of strictly typed messages: one for the request and one for the response"

Scale in 2009

• more than 400 message types, "several hundred" packages; used on Stanford and Willow Garage robots (PR2)

Quigley, M., et al. (2009). ROS: An open-source Robot Operating System. ICRA Workshop on Open Source Software, §II–IV.

ROS 2 (2022): the same graph model rebuilt as a layered stack over an industrial middleware

Requirements that ROS 1 did not meet (§III.B)

• Security ("authentication, encryption, and access control"); embedded systems (Micro-ROS "allows ROS 2 to be reused on embedded systems"); diverse networks (quality-of-service settings "adapting to the constraints of a network"); real-time computing (APIs "to enforce application-specific constraints"); product readiness
• principles named in the paper: "Distribution, Abstraction, Asynchrony, and Modularity"

Why DDS

• an existing standard with security, embedded/real-time support and multi-robot communication; peer-to-peer discovery replaces the ROS 1 master, which "has a single point of failure"

Quality of service

• per-connection policies: reliability, durability, history, deadline, lifespan, liveliness — the network behaviour becomes a declared contract rather than a fixed property of the middleware

Numbers in the paper

• ≈ 32–33 thousand tests in the core; intra-process 95th-percentile latency below 1 ms

Macenski, S., Foote, T., Gerkey, B., Lalancette, C., & Woodall, W. (2022). Science Robotics 7(66), eabm6074, §III and Fig. 2.

Uses in the wild: the five deployments the paper reports, one per environment

Reading the table

• each environment maps to one of the requirements on the previous slide: real- time, diverse networks, embedded, product readiness, multi-robot
• the same graph-of-nodes model from 2009 is unchanged; what changed is the layer underneath it and the contracts (QoS, security) attached to each connection

Architectural point

• ROS is an example of an architecture defined by its interfaces (message types, the node graph, the rmw layer) rather than by any implementation — the implementations were replaced wholesale between the two papers while the model survived

Macenski et al. (2022), §IV "Uses in the wild".

Subsumption: build the robot as layers of competence; higher layers suppress lower ones

Requirements the design answers (§II)

• multiple goals; multiple sensors; robustness; extensibility — vertical slices by function (Fig. 1: sense → model → plan → act) are replaced by horizontal behaviour layers (Fig. 2)

Level of competence

• "an informal specification of a desired class of behaviors for a robot over all environments it will encounter"; the eight levels listed in the paper: 0 avoid contact; 1 wander; 2 explore; 3 build a map and plan routes; 4 notice changes in the "static" environment; 5 reason about identifiable objects; 6 formulate and execute plans that change the world; 7 reason about the behaviour of objects and modify plans

How layers combine

• "Higher-level layers can subsume the roles of lower levels by suppressing their outputs"; level 0 is built and "debugged thoroughly. We never alter that system."
• levels 0 and 1 ran on the physical robot (12 sonar sensors); levels 2–3 were designed

Brooks, R. A. (1986). A robust layered control system for a mobile robot. IEEE J. Robotics and Automation 2(1), 14–23, Figs. 1–3 and §II–III.

Inside two layers: augmented finite-state machines, suppression and inhibition

The unit

• "Each module is a finite state machine, augmented with some instance variables, which can actually hold Lisp data structures" — an augmented finite-state machine (AFSM) with input and output wires

Two ways to interfere with a wire (verbatim)

• inhibition (a wire attached to an output): "If any signal travels along this wire it inhibits any output message from the module along that line for some predetermined time."
• suppression (a wire attached to an input): the signal inhibits the usual input and "actually gets fed through as the input to the module"

Why this counts as an architecture

• the interface between layers is only the set of wires that may be suppressed or inhibited; a new layer can be added without editing the old ones, and removing it leaves a working robot
• what it lacks (Gat's critique, next slide): no place for algorithms that keep state about the past or search over the future

Brooks (1986), Figs. 5–7 (level 0 and level 1 module graphs) and §III mechanism definitions.

Gat's three layers: sorted by the state an algorithm keeps — none, the past, or the future

The organizing rule (verbatim)

• "Three-layer architectures organize algorithms according to whether they contain no state, contain state reflecting memories about the past, or contain state reflecting predictions about the future." "In ATLANTIS these layers are called the controller, the sequencer, and the deliberator."

History the chapter gives (§1)

• sense–plan–act (Shakey): "unidirectional and linear"; subsumption "lacks mechanisms for managing complexity"; early 1990s: Connell's SSS, Bonasso's 3T, Gat's ATLANTIS; "Firby's thesis contains the earliest description of the three-layer architecture that has now become the de facto standard"

Per-layer rules (§3)

• controller: "implement one or more feedback control loops"; no search; "should fail cognizantly, that is, they should be designed to detect (as opposed to avoid) any failure"
• sequencer: "select which primitive Behavior the controller should use at a given time, and to supply parameters"; no slow computations
• deliberator: "the locus of time-consuming computations"; "It can produce plans for the sequencer to execute, or it can respond to specific queries" (3T vs ATLANTIS)

Gat, E. (1998). On three-layer architectures. In Kortenkamp, Bonasso & Murphy (Eds.), AI and Mobile Robots, pp. 195–210, §1–3.

Wiener 1948: control and communication, in animal and machine, rest on feedback

The name and the claim

• "We have decided to call the entire field of control and communication theory, whether in the machine or in the animal, by the name Cybernetics, which we form from the Greek κυβερνήτης, or steersman"; Maxwell's 1868 paper on governors is cited as "the first significant paper on feed-back mechanisms", and "governor is derived from a Latin corruption of κυβερνήτης"

Feedback (verbatim)

• "When we desire a motion to follow a given pattern, the difference between this pattern and the actually performed motion is used as a new input to cause the part regulated to move in such a direction as to bring its motion closer to that given by the pattern"
• with Bigelow: "an extremely important factor in voluntary activity is what the control engineers call feed-back"; too much feedback produces oscillation — the neurological analogue is cerebellar "purpose tremor" (confirmed with Rosenblueth)

Contents (1948)

• Newtonian and Bergsonian time; groups and statistical mechanics; time series, information and communication; feedback and oscillation; computing machines and the nervous system; Gestalt and universals; cybernetics and psychopathology; information, language and society

Wiener, N. (1948). Cybernetics. MIT Press / Wiley, Introduction and ch. IV "Feedback and Oscillation".

Ashby 1952: keep the essential variables within limits, by random re-wiring if needed

Essential variables (§3/14)

• "Every species has a number of variables which are closely related to survival and which are closely linked dynamically so that marked changes in any one leads sooner or later to marked changes in the others"

Adaptation (§5/1, 5/8)

• "A form of behaviour is adaptive if it maintains the essential variables within physiological limits"; adaptive behaviour "is equivalent to the behaviour of a stable system, the region of stability being the region of the phase-space in which all the essential variables lie within their normal limits"

Ultrastability (§8/4)

• a system "that is absolute and contains step-functions in a sufficiently large number"; "If the field leads the point to a critical state, a step-function will change value" and "the field will be changed" — the system "acts selectively towards the fields of the main variables, rejecting those that lead the representative point to a critical state but retaining those that do not"
• two time scales, two layers: a fast dynamics among the main variables and a slow, discrete search over the parameters that shape it

Ashby, W. R. (1952). Design for a Brain. Chapman & Hall, §3/14, 5/1, 5/8, 8/4, 8/8 (first edition).

The law of requisite variety: only variety in the regulator can force down the variety of outcomes

Variety (§7/7)

• "the number of distinct elements, or … the logarithm to the base 2 of the number", in bits

The law (§11/5–11/7)

• for tables in which no outcome repeats within a column, "the variety in the selected set of outcomes cannot be fewer than r/c" (r rows, c columns); in bits, the first equation at left: with the disturbance variety fixed, the outcome variety can be lessened only by a corresponding increase in the regulator's variety

• "This is the law of Requisite Variety. To put it more picturesquely: only variety in R can force down the variety due to D; only variety can destroy variety."

Entropy form (§11/8–11/9)

• with D, R, E treated as Shannon sources, the second equation at left; the minimum is reached when R is a determinate function of D

Two consequences the book draws

• an error-controlled regulator (ch. 12: R fed from E, "with its well-known feedback from E to R") "cannot be perfect", because "The information available to R is only such as survives the transmission through T and E"

• amplification (ch. 14): the law "absolutely prohibits any direct and simple magnification but it does not prohibit supplementation"

Ashby, W. R. (1956). An Introduction to Cybernetics. Chapman & Hall, §7/7 (variety), §11/3–11/11 (the game, the law, the entropy form).

Ashby 1958: the regulator as a channel; control without understanding

Regulator = channel

• "R's capacity as a regulator cannot exceed its capacity as a channel for variety"; "the 'goal' is a message of zero entropy, and … the 'disturbances' correspond to noise"
• pay-off matrix form: "A set D of disturbances d_i can be met by a set R of responses r_j … each cell shows an element z_ij from the set Z of possible outcomes"

Implications for complex systems (Part II)

• "when the complexity of the system exceeds the finite capacity of the scientist, the scientist can no longer understand the system"; the limit "does not impose a limitation on a team of n men" (capacity "possibly n times as high")
• "If a system is too complex to be understood, it may nevertheless still be controllable"; operational research's "ultimate aim is not understanding but the purely practical one of control"

Reading it as architecture

• the variety a regulator must supply is a design quantity; layering, in later sections of the deck, is one way to get requisite variety from components that individually lack it

Ashby, W. R. (1958). Requisite variety and its implications for the control of complex systems. Cybernetica 1(2), 83–99.

Every good regulator of a system must be a model of that system

Theorem (verbatim)

• "The simplest optimal regulator R of a reguland S produces events R which are related to the events S by a mapping h: S → R."

Setting

• regulation = keeping the outcome in the goal set; "optimal" = the entropy of the outcome is minimal; "simplest" = the regulator's conditional distribution given the system's state "consisting entirely of ones and zeroes … in fact a mapping h from S into R"

Proof idea (Lemma)

• for every system state, the set of outcomes the regulator produces with positive probability has one element; if two regulator moves gave different outcomes for the same system state, shifting probability to one of them would lower the outcome entropy, contradicting optimality

Two remarks in the paper

• error-controlled regulation (R fed from the outcome) "is in fact a primitive and demonstrably inferior method"; with cause control "the regulation may, in principle, be made perfect"

• for designers: "A model will be needed; let's build one"; for brains: a successful regulator for survival "must proceed, in learning, by the formation of a model (or models) of its environment"

Conant, R. C., & Ashby, W. R. (1970). Int. J. Systems Science 1(2), 89–97, Fig. 1, Lemma, Theorem, eq. 8.

General system theory: the same laws recur across disciplines

The claim (1950, verbatim)

• "there exist general system laws which apply to any system of a certain type, irrespective of the particular properties of the system or the elements involved"; hence "formally identical or isomorphic laws in completely different fields"

Definitions (1968, ch. 3)

• "A system can be defined as a set of elements standing in interrelations" — the coupled equations at left, in which each rate depends on all the quantities

• closed system: "no materials enter or leave it"; open system: "inflow and outflow, and therefore change of the component materials"; its steady state is maintained "in a continuous change" and "not defined by maximum entropy but … by minimum entropy production" (citing Prigogine)

• equifinality: "the same final state may be reached from different initial conditions and in different ways" — the sea-urchin embryo example

Hierarchy

• "A general theory of hierarchic order obviously will be a mainstay of general systems theory"; systems "structured in a way so that their individual members again are systems of the next lower level"

• fields the 1968 book lists as parts of the programme: cybernetics, information theory, game theory, decision theory, automata, queuing, graph theory, compartment theory, simulation

von Bertalanffy, L. (1950). BJPS 1(2), 134–165, §2, §8–9; (1968). General System Theory. Braziller, ch. 1–3. Chart: the three isomorphic laws with a = 0.5, b = 0.005.

The architecture of complexity: hierarchies evolve faster (Hora and Tempus)

Definitions (verbatim)

• complex system: "one made up of a large number of parts that interact in a nonsimple way"; "In the face of complexity, an in-principle reductionist may be at the same time a pragmatic holist"

• hierarchy: "a system that is composed of interrelated subsystems, each of the latter being, in turn, hierarchic in structure until we reach some lowest level of elementary subsystem"

• span: "the number of subsystems into which it is partitioned"; a system is "flat at a given level if it has a wide span at that level"

The parable's conclusion

• "The time required for the evolution of a complex form from simple elements depends critically on the numbers and distribution of potential intermediate stable forms"

Four sections of the paper

• the frequency of hierarchy in nature and society; evolution of complex systems (Hora and Tempus); nearly decomposable systems (next slide); the description of complexity: "state description" (what a thing is: "A circle is the locus of all points equidistant from a given point") versus "process description" (how to make it: rotate a compass), with problem solving as "continual translation between the state and process descriptions"

Simon, H. A. (1962). The architecture of complexity. Proc. APS 106(6), 467–482, §I–II (definitions, the Hora–Tempus parable and its footnote). Chart: exact expectation for the restart model.

Nearly decomposable systems: strong interactions inside blocks, weak interactions between them

Definition

• a matrix whose intra-block elements are large and whose extra-block elements are "either zero or small" (bounded by ε): a nearly decomposable system

Two propositions (verbatim)

• "(a) in a nearly decomposable system, the short-run behavior of each of the component subsystems is approximately independent of the short-run behavior of the other components"
• "(b) in the long run, the behavior of any one of the components depends in only an aggregate way on the behavior of the other components"

Why it matters for architecture

• a designer can treat each block as a unit (its internal dynamics settle first) and describe the whole by block-level aggregates — the justification for modules with narrow interfaces
• the "empty world hypothesis": "most things are only weakly connected with most other things; for a tolerable description of reality only a tiny fraction of all possible interactions needs to be taken into account"
• the proof of (a) and (b) is Simon & Ando (1961), next slide

Simon (1962), §III "Nearly decomposable systems", Fig. 1 "A hypothetical nearly decomposable system" (heat diffusion coefficients between cubicles), pp. 474–476.

Simon & Ando: fast within-block equilibrium, slow between-block dynamics

Abstract (verbatim)

• systems "nearly decomposable — systems with matrices whose elements, except within certain submatrices along the main diagonal, approach zero in the limit. Such a system can be represented as a superposition of (1) a set of independent subsystems (one for each submatrix on the diagonal) and (2) an aggregate system having one variable for each subsystem. This superposition separates short-run from long-run dynamics and justifies the ignoring of 'weak' linkages in partial equilibrium studies."

Results

• as ε → 0 the eigenvalues and eigenvectors of P converge to those of the block-diagonal P*; the N eigenvalues nearest the blocks' dominant ones are within O(ε) of them and separated from the rest

• time phases: within-block transients; each block near its own equilibrium as if isolated; cross-block flows move the aggregates while within-block proportions stay fixed; global equilibrium

• aggregation (second equation at left): the aggregates obey a small system of their own with O(ε) error

Use in the deck

• the mathematical content behind "layers run at different rates": the slow variables are the aggregates, the fast ones the within-block details

Simon & Ando (1961). Econometrica 29(2), 111–138 (abstract; theorems as restated by Shpak et al. 2004). Chart: diffusion on Simon's Fig. 1 matrix.

Simon 1969: the artifact is an interface between an inner and an outer environment

What makes a science of design

• artificial things are synthesized by humans, may imitate natural appearances, "are characterized by functions, goals, adaptation", and are discussed "in imperatives as well as descriptives"; the science is about "how things ought to be … in order to attain goals, and to function"

• "Everyone designs who devises courses of action aimed at changing existing situations into preferred ones"

Bounded rationality and satisficing (ch. 2)

• "the business firm turns to procedures that find good enough answers to questions whose best answers are unknowable"; "An alternative satisfices if it meets aspirations along all dimensions"

The design curriculum (ch. 5)

• evaluation of designs (utility theory, statistical decision theory; algorithms for optimal and for satisfactory alternatives; the logic of design); the search for alternatives (heuristic search: factorization and means–ends analysis; allocation of resources for search; "theory of structure and design organization: hierarchic systems"; representation of design problems)

• ch. 8 reprints "The architecture of complexity" — the two previous slides are part of this book

Simon, H. A. (1969/1996). The Sciences of the Artificial. MIT Press, ch. 1 (p. 6), ch. 2 (pp. 28–38), ch. 3 (pp. 52–53), ch. 5, ch. 8.

Newell 1982: the knowledge level, a description level above the symbol level

What a level is (verbatim)

• "A level consists of a medium that is to be processed, components that provide primitive processing, laws of composition that permit components to be assembled into systems, and laws of behavior that determine how system behavior depends on the component behavior and the structure of the system"; "Each level can be defined autonomously, without reference to any other level"

The hypothesis

• "There exists a distinct computer systems level, lying immediately above the symbol level, which is characterized by knowledge as the medium and the principle of rationality as the law of behavior"; "The system at the knowledge level is the agent"

• "Representations exist at the symbol level, being systems (data structures and processes) that realize a body of knowledge at the knowledge level"; slogan: "Representation = Knowledge + Access"

Its limits

• the level "permits predicting and understanding behavior without having an operational model of the processing that is actually being done by the agent", but it is "only an approximation, and a relatively poor one on many occasions — we called it radically incomplete"

• for this reading list: a level is defined by its own medium and laws, not by the hardware below it — the same move as Clark's architecture-as-agreement (Part 1)

Newell, A. (1982). The knowledge level. Artificial Intelligence 18(1), 87–127, §3 (Fig. 2, Table 1), §4–5.

THE multiprogramming system: six levels, each tested assuming the ones below it are correct

Why levels: testability

• "Starting at level 0 the system was tested, each time adding (a portion of) the next level only after the previous level had been thoroughly tested"
• the goal was to structure the system "so effectively … that at each stage of the testing procedure the number of relevant test cases will be so small that he can try them all"; otherwise "exhaustive testing would have been an illusion"

The synchronization primitive

• semaphores: "special purpose integer variables … initialized (with the value 0 or 1)"; P(sem) "decreases the value … by 1" and if the result is negative the process "is stopped and booked on a waiting list"; V(sem) "increases the value … by 1" and releases a waiting process

Outcome claimed

• "its logical soundness can be proved a priori and its implementation can admit exhaustive testing"; "trivial coding errors (occurring with a density of one error per 500 instructions), each of them located within 10 minutes"

The idea reused later

• a level is defined by what it hides from the levels above — the same criterion Parnas will state for modules

Dijkstra, E. W. (1968). The structure of the "THE"-multiprogramming system. CACM 11(5), 341–346 (levels, testing argument, semaphores; quotes verbatim).

The Humble Programmer: intellectual manageability as the design criterion

The two sentences everyone quotes

• "The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague."
• "program testing can be a very effective way to show the presence of bugs, but is hopelessly inadequate for showing their absence."

The closing condition

• "We shall do a much better programming job, provided that we approach the task with a full appreciation of its tremendous difficulty, provided that we stick to modest and elegant programming languages, provided that we respect the intrinsic limitations of the human mind and approach the task as Very Humble Programmers."

Connection to the rest of the section

• the limit being designed around is the designer's own capacity (Ashby's 1958 limit on the scientist, in a programmer's words); levels and modules are the means of keeping each piece within that capacity

Dijkstra, E. W. (1972). The humble programmer. CACM 15(10), 859–866 (EWD340); quotes verbatim.

Parnas 1972: decompose by the design decisions likely to change, not by flowchart steps

The problem

• lines of words; "any line can be 'circularly shifted' by repeatedly removing the first word and adding it to the end"; output all shifts, alphabetized — small enough to show two complete decompositions

The criterion (verbatim)

• "it is almost always incorrect to begin the decomposition of a system into modules on the basis of a flowchart. We propose instead that one begins with a list of difficult design decisions or design decisions which are likely to change. Each module is then designed to hide such a decision from the others."

• a module's "interface or definition was chosen to reveal as little as possible about its inner workings"

Benefits claimed

• "(1) managerial—development time should be shortened because separate groups can work on each module with little need for communication; (2) product flexibility—… drastic changes … in one module without changing others; (3) comprehensibility—… studied a module at a time"

• "hierarchical structure and 'clean' decomposition are two desirable but independent properties" — hierarchy is the subject of the next slide

Parnas, D. L. (1972). On the criteria to be used in decomposing systems into modules. CACM 15(12), 1053–1058 (KWIC example; criterion verbatim).

"Hierarchical structure" means nothing until you say which relation; the useful one is "uses"

The point of the 1974 paper (abstract, verbatim)

• the term "hierarchically structured" has "a number of quite different meanings … An understanding of the different meanings of the term is essential, if a designer wishes to apply recent work in software engineering and design methodology"

The "uses" relation (1979 restatement)

• "A uses B if correct execution of B may be necessary for A to complete the task described in its specification"; "uses differs from invokes"

• levels: "Level 0 is the set of all programs that use no other program; Level i … use at least one program on level i−1, and no program at a higher level than i−1"

• the graph must be loop-free because "each level offers a testable and usable subset of the system"

When A may use B (four conditions)

• A is simpler because it uses B; B is not substantially more complex because it may not use A; there is a useful subset containing B and not A; there is no useful subset containing A but not B

• module structure (what hides what) and "uses" structure (what needs what) are different hierarchies of the same system

Parnas, D. L. (1974). On a "buzzword": Hierarchical structure. IFIP Congress, 336–339 (abstract); the "uses" definition and sandwiching from Parnas (1979), IEEE TSE, which restates it.

Program families: decide what the whole family shares before what separates its members

Definition (verbatim)

• "We consider a set of programs to constitute a family, whenever it is worthwhile to study programs from the set by first studying the common properties of the set and then determining the special properties of the individual family members."

Two methods for the tree

• stepwise refinement (Dijkstra, Wirth): the intermediate stages "are programs, which are complete except for the implementation of certain operators and operand types"; "decisions which are made in the earlier steps are those least likely to change"

• module specification (information hiding): the stages "are 'specifications' of the externally visible collective behavior of program groups called modules", each hiding a decision not shared by all members

The ordering rule

• "allow the decisions, which can be shared by a whole family, to be made before those decisions, which differentiate family members"; a development is good "if the early decisions exclude only uninteresting, undesired, or unnecessary programs"

• the methods "are neither equivalent nor contradictory. Rather they are complementary"; module specification pays "only when one expects the eventual implementation of a wide selection of possible family members"

Parnas, D. L. (1976). On the design and development of program families. IEEE TSE SE-2(1), 1–9, Figs. 1–2 and §II–IV.

Structured design: grade a split by coupling between modules and cohesion within them

Definitions (verbatim)

• coupling "may be operationalized as the probability that in coding, debugging, or modifying one module, a programmer will have to take into account something about another module"

• "The greater the cohesion of individual modules in the system, the lower the coupling between modules will be"

• four aspects of coupling "in order of estimated magnitude of their effect": type of connection, interface complexity, type of information flow, binding time

Heuristics (ch. 9)

• "Fan-out, or span of control, is the number of immediate subordinates of a module … very high or very low spans are possible indicators of poor design"; "Fan-in is the raison d'être of modularity"; "the scope of effect should be a subset of the scope of control"

• 7 ± 2 items in short-term memory; modules over about 100 statements are "outside the optimal range"; modular systems cost 5–10% more memory and CPU

Transform analysis (p. 188)

• "1. restating the problem as a data flow graph 2. identifying the afferent and efferent data elements 3. first-level factoring 4. factoring of afferent, efferent, and transform branches"

Yourdon, E., & Constantine, L. L. (1979). Structured Design. Prentice-Hall, ch. 6 (coupling, pp. 85–107), ch. 7 (cohesion), ch. 9 (heuristics, pp. 166–178), App. B (structure charts).

Design Rules: a modular design is a design structure matrix with visible rules and hidden modules

Module (p. 63, verbatim)

• "a unit whose structural elements are powerfully connected among themselves and relatively weakly connected to elements in other units … there are gradations of modularity"; modularization serves "to make complexity manageable; to enable parallel work; to accommodate future uncertainty"

Design rules

• the visible information: rules "that govern the architecture, the interfaces, and the standardized tests of the system", which "hidden module designers must obey if the modules are to work together"; hidden parameters "do not affect, and hence do not need to be known to those working on other modules"

Six modular operators (ch. 5)

• splitting a system into modules; substituting one module for another; augmenting (adding a module); excluding (removing one); inverting (collecting common elements into new design rules); porting (making a module fit two or more systems)

The historical case

• IBM System/360 (1964): one instruction set and standard interfaces across six models; disk-drive designers "left IBM … to design and manufacture drives that would 'plug into' System/360" — the modular structure created an industry

Baldwin, C. Y., & Clark, K. B. (2000). Design Rules, Vol. 1. MIT Press, ch. 2–3 (DSM, design rules), ch. 5 (six operators), p. 63 (module definition).

The option value of modularity: each module is an option, and splitting multiplies options

The argument

• a redesign is an uncertain draw; because a worse design is simply not adopted, the payoff is an option — its value is the expectation of the positive part

• splitting the design into modules with parameter shares αᵢ multiplies the option value:

• "the value of a system … is the sum of the option values of its modules, minus the cost of the design rules that make them possible"

Net option value of a module

• the second equation: the best number of parallel experiments balances the rising value Q(k) against experiment cost and against the cost of visibility Z — the redesign forced on every module that can see this one; hidden information keeps Z small

Where it leads

• IBM held 71% of the computer industry's market value in 1969; after the modular System/360 no firm held more than 15% by 1996 — the options were exercised by other firms

• the economic counterpart of Parnas: information hiding is what makes each module a separately exercisable option

Baldwin & Clark (2000), ch. 9–10; formulas as restated in Baldwin & Clark (2002, 2006) and Sullivan et al. (2001). Chart: Q(k) by numerical integration.

Dantzig–Wolfe: a block-angular program becomes a master over each part's proposals

The principle (abstract, verbatim)

• "The coordinating program generates at each cycle new objective forms for each part, and each part generates in turn from its optimal basic feasible solutions new activities (columns) for the interconnecting program"

How the master is built

• any point of part j's own polyhedron P_j is a convex combination of its extreme points; so the master (second equation at left) chooses weights λ over proposals, subject only to the coupling rows and one convexity row per part
• the master has few rows (the coupling rows plus J convexity rows) but potentially very many columns — one per extreme point — which is why they are generated on demand (next slide)

Economic reading (the paper's)

• "the principle yields a certain rationale for the 'decentralized decision process' in the theory of the firm": a central agency posts prices on the shared resources; divisions respond with proposals; the centre blends them and revises the prices

Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research 8(1), 101–111 (abstract verbatim; equations in modern notation).

Column generation: prices go down to the parts, proposals come back, bounds close

prices

Symbols

columns

The cycle (equation at bottom left)

• the master's duals price the shared resources; each part minimizes its own cost minus the value of the shared resources it uses; if the best proposal has negative reduced cost it is added as a column; otherwise the current master solution is optimal for the whole program
• the value of the restricted master is an upper bound; adding the (negative) reduced costs gives a lower bound — the two meet at the optimum

Why it counts as an architecture

• the parts never see each other's constraints, only the prices; the coordinator never sees the parts' internals, only their proposals — the interface between layers is a price vector, as in the network decomposition of Part 3

Dantzig & Wolfe (1960); pricing step and bounds in modern notation. Chart: two 2-variable parts, two coupling rows, deck's own toy instance solved with column generation.

Benders: fix the complicating variables, solve the rest, send back a cut

Symbols (equations bottom left: problem, subproblem, master)

The cycle

• fix the complicating variables; the remaining LP's dual polyhedron does not depend on them, so the LP's value is the maximum of finitely many linear functions of y — one per extreme point — and infeasibility is signalled by an extreme ray
• the master keeps only the linear pieces (cuts) found so far and adds one per cycle: row generation, finite because there are finitely many extreme points and rays
• Benders' own use: y integer ("mixed-variables"), so the master is a small integer program and the subproblem a plain LP

Duality to Dantzig–Wolfe

• solving a linear program by Dantzig–Wolfe decomposition is the same as applying Benders to its dual: complicating constraints there, complicating variables here; columns there, rows here

Benders, J. F. (1962). Numerische Mathematik 4(1), 238–252 (min form and modern notation; duality to Dantzig–Wolfe per Rahmaniani et al. 2017). Chart: deck's own 2-facility, 3-customer instance.

Weaver: problems of simplicity, of disorganized complexity, and of organized complexity

The argument

• science mastered few-variable problems, then jumped "to the other extreme" with statistics for very many variables, and "left untouched a great middle region" — the problems of organized complexity
• "Science must, over the next 50 years, learn to deal with these problems of organized complexity"

Two instruments he proposes

• "the wartime development of new types of electronic computing devices"

• "the 'mixed-team' approach of operations analysis": mathematicians, physicists and engineers working with physiologists, biochemists and psychologists

Why the list starts here

• architecture is the response to organized complexity: a moderate number of strongly interrelated parts, where neither closed-form analysis nor averaging applies; every later reference proposes a structure (levels, modules, protocols, hierarchy) for exactly this middle region

Weaver, W. (1948). Science and complexity. American Scientist 36(4), 536–544 (section headings; quotes verbatim).

Shannon: a communication system has five parts; semantics is not the engineering problem

Entropy, capacity, and the Gaussian-channel capacity (Theorems 2, 17)

Claims (verbatim)

• "These semantic aspects of communication are irrelevant to the engineering problem."
• Theorem 11: "If H ≤ C there exists a coding system such that the output of the source can be transmitted over the channel with an arbitrarily small frequency of errors … There is no method of encoding which gives an equivocation less than H − C."

Two results that make an architecture

• source coding (Theorem 9) and channel coding (Theorem 11) are separate theorems: the source can be compressed without knowing the channel and the channel protected without knowing the source — the separation the Internet's layers rely on
• "The redundancy of ordinary English … is roughly 50%"; the word "bit" is credited to J. W. Tukey

Shannon, C. E. (1948). A mathematical theory of communication. BSTJ 27(3), 379–423 and 27(4), 623–656; Fig. 1, Theorems 2, 9, 11, 17.

Alexander: decompose the requirements graph into nearly independent subsets

Fit, form, context (verbatim)

• "The form is the solution to the problem; the context defines the problem"; the object of design is "the ensemble comprising the form and its context"; "Fitness is a relation of mutual acceptability between these two"

• fit is defined negatively: design is "a negative process of neutralizing the incongruities"; "Any state of affairs in the ensemble which derives from the interaction between form and context, and causes stress in the ensemble, is a misfit"; a misfit variable "takes the value 1" when the misfit occurs, "0" otherwise

• "A design problem is not an optimization problem … only to satisfy them at a level which suffices to prevent misfit"

Why decompose

• "The intuitive resolution of contemporary design problems simply lies beyond a single individual's integrative grasp"; a good tree lets each subset be solved almost on its own — Simon's near-decomposability applied to requirements

Unselfconscious vs selfconscious

• cultures whose form-making "is learned informally, through imitation and correction" are homeostatic and keep producing well-fitting forms; academically taught form- making lost that and needs the method; the 1971 preface rejects "design methods as a subject of study" but keeps the independent diagrams

Alexander, C. (1964). Notes on the Synthesis of Form. Harvard UP, ch. 2–7 and Appendix 1 (Bavra village); decomposition tree per the book's appendix as reported by Gabriel (2023).

Organizations in Action: match the kind of interdependence to the kind of coordination

Framing

• "the organization as an open system, indeterminate and faced with uncertainty, but subject to criteria of rationality and hence needing certainty"; "Uncertainty appears as the fundamental problem for complex organizations, and coping with uncertainty, as the essence of the administrative process"

Protecting the technical core (propositions, verbatim)

• 2.1 "Under norms of rationality, organizations seek to seal off their core technologies from environmental influences"; 2.2 "…seek to buffer environmental influences by surrounding their technical cores with input and output components"; 2.3 "…seek to smooth out input and output transactions"; 2.4 "…seek to anticipate and adapt to environmental changes which cannot be buffered or leveled"; 2.5 when these fail, "… resort to rationing"

Grouping rule (5.1)

• "Under norms of rationality, organizations group positions to minimize coordination costs": place reciprocally interdependent positions together first, "in a common group which is (a) local and (b) conditionally autonomous"; then sequentially interdependent ones; then group homogeneously "to facilitate coordination by standardization"; residual interdependence is handled by committees (sequential) and "task-force or project groupings" (reciprocal)

Thompson, J. D. (1967). Organizations in Action. McGraw-Hill, ch. 2 (propositions 2.1–2.5) and ch. 5 (interdependence, coordination, propositions 5.1–5.4; wording of the type definitions paraphrased).

Conway 1968: a system copies the communication structure of the organization that built it

Thesis (verbatim, from the Conclusion)

• "Any organization that designs a system (defined more broadly here than just information systems) will inevitably produce a design whose structure is a copy of the organization's communication structure."

The argument

• "The very act of organizing a design team means that certain design decisions have already been made, explicitly or otherwise"; where each subsystem has its own group the two graphs coincide: "This kind of a structure-preserving relationship between two sets of things is called a homomorphism"

• "Given any design team organization, there is a class of design alternatives which cannot be effectively pursued by such an organization because the necessary communication paths do not exist"

Large teams

• "The structures of large systems tend to disintegrate during development, qualitatively more so than with small systems": the temptation "to assign too many people", the disintegration of a large organization's communication structure, and the homomorphism that copies it into the system; "The number of possible communication paths in an organization is approximately half the square of the number of people"

• "Two men and one hundred men cannot work in the same organizational structure"; managers should be rewarded "for keeping their organizations lean and flexible"

Conway, M. E. (1968). How do committees invent? Datamation 14(4), 28–31 (thesis and homomorphism argument verbatim; Figs. 1–3 redrawn).

Hierarchy Theory: a control hierarchy is an upper level that constrains the rates of events below it

Pattee's definitions (verbatim)

• control: "An effective control event cannot be simply a passive, spatial constraint, but must actively change the rate of one particular event, reaction, or trajectory"

• constraint: "A hierarchical constraint is established by a particular kind of new rule that represents not merely a structure but a classification of microscopic degrees of freedom"; "A constraint requires an alternative description" — "alternative modes of description are an absolute necessity"

• interface: "hierarchical control operates between levels and is therefore a problem of the nature of the interface between levels"

• loss of detail: "Function or control can only arise through some selective loss of detail"; control appears where there is "some optimum loss of the effects of detail"; the enzyme is the simplest structure meeting the conditions, and a control molecule "functions as a message"

Simon's chapter

• "loose horizontal coupling … has great importance for evolutionary processes"; "loose vertical coupling permits the stable subassemblies to be treated as simple givens, whose dynamic behavior is irrelevant"; "Hierarchies will evolve much more rapidly from elementary constituents than will non-hierarchic systems"

Pattee, H. H. (Ed.). (1973). Hierarchy Theory. Braziller; Pattee's chapter "The physical basis and origin of hierarchical control" (pp. 73–108) and Simon's "The organization of complex systems".

Brooks 1975: communication grows with pairs, so adding people can make a project later

The law and its reason (verbatim)

• "Men and months are interchangeable commodities only when a task can be partitioned among many workers with no communication among them"

• "If each part of the task must be separately coordinated with each other part, the effort increases as n(n−1)/2. Three workers require three times as much pairwise intercommunication as two; four require six times as much as two."

• "Oversimplifying outrageously, we state Brooks's Law: Adding manpower to a late software project makes it later."

Rules of thumb

• schedule: "1/3 planning, 1/6 coding, 1/4 component test and early system test, 1/4 system test, all components in hand"

• the regenerative disaster: a 12 man-month, 3-person, 4-month project that misses its first milestone; adding people costs a month of training each and repartitioning, "so the project is no earlier"

Organization as architecture

• the surgical team (ch. 3, after Harlan Mills): ten people with one "surgeon" writing the code; a 200-person project becomes 20 teams — a hierarchy chosen to cut the number of communicating pairs

• "conceptual integrity is the most important consideration in system design" (ch. 4); "This second is the most dangerous system a man ever designs" (ch. 5)

Brooks, F. P., Jr. (1975). The Mythical Man-Month. Addison-Wesley, ch. 2 (Figs. 2.1–2.4, Brooks's law), ch. 3–5. Chart: reconstruction with W = 12 man-months.

McCallum's 1855 Erie diagram: authority down the tree, hourly/daily/monthly reports up

Why a 500-mile road needed it

up

• McCallum (general superintendent 1854–57): a superintendent of a 50-mile road "may be almost constantly upon the line engaged in the direction of its details"; a road ten times longer cannot be run that way

Six "general principles" (1855 report, verbatim)

• "First. A proper division of responsibilities. Second. Sufficient power conferred to enable the same to be fully carried out … Third. The means of knowing whether such responsibilities are faithfully executed. Fourth. Great promptness in the report of all derelictions of duty … Fifth. Such information to be obtained through a system of daily reports and checks that will not embarrass principal officers nor lessen their influence with their subordinates. Sixth. The adoption of a system, as a whole, which will not only enable the general superintendent to detect errors immediately, but will also point out the delinquent."

The data system behind the picture

• hourly train positions by telegraph, conductors' and agents' daily reports, monthly comparisons by division (cost per ton-mile, load per car)

Chandler 1988

• the two-page HBR note; Chandler had described the chart from Henry Varnum Poor's 1856 advertisement in the American Railroad Journal without having seen it — two copies are known today (Library of Congress; St. Lawrence University)

Wrege & Sorbo (2005); McCallum's 1855 Report of the Superintendent (six principles verbatim); Chandler (1988), HBR 66(2), 156–157; Library of Congress copy of the diagram.

Brinton 1914: organization charts "not nearly so widely used as they should be"

The book

• preface (June 1914): "As far as the author is aware, there is no book published in any language covering the field which it has been attempted to cover here"; it reports the ASME-convened Joint Committee on Standards for Graphic Presentation (about fifteen societies invited)

On organization charts (verbatim)

• "Organization charts are not nearly so widely used as they should be."

• "A complete organization chart should always include the stockholders and the Board of Directors as shown here."
• "If such a chart is made there will be fewer cases of conflict or of short-circuiting of orders. Every command from the general that is given directly to the private over the head of the captain weakens the authority of the captain over the private."

Why it is in the list

• the same narrow-waist shape as the Internet hourglass and the metabolic bowtie, drawn for an organization sixty years earlier; and evidence that in 1914 the explicit chart was still the exception — the 1920s surveys found it uncommon in ordinary firms
• Brinton also argues for horizontal bars over pie charts, so that figures can be read and added

Brinton, W. C. (1914). Graphic Methods for Presenting Facts. Engineering Magazine Co., Fig. 13 and accompanying text (quotes verbatim).

Strategy and Structure: diversification produced the multidivisional (M-form) enterprise

Definitions (verbatim)

• strategy: "the determination of the basic long-term goals and objectives of an enterprise, and the adoption of courses of action and the allocation of resources necessary for carrying out these goals"

• structure: "the design of organization through which the enterprise is administered" — the lines of authority and communication, and the information that flows through them

The thesis

• "structure follows strategy and … the most complex type of structure is the result of the concatenation of several basic strategies": volume expansion → an administrative office; geographic dispersion → departmental headquarters; vertical integration → multidepartmental structure with a central office; diversification → multidivisional structure with a general office

fin.

• by 1960 "the multidivisional type of administrative structure, which hardly existed in 1920, had become the accepted form of management for the most complex and diverse of American industrial enterprises"

Four phases of enterprise history (p. 385)

• "initial expansion and accumulation of resources; rationalization of use of resources; expansion into new markets and lines; finally development of new structure for continuing effective mobilization of resources"

Chandler, A. D., Jr. (1962). Strategy and Structure. MIT Press, pp. 2, 13–14, 49, 385 and the four case chapters (quotes verbatim; dates from the case chapters and annual reports).

The Visible Hand: managerial hierarchies replaced markets where coordination paid

Thesis (verbatim)

• "Modern business enterprise took the place of market mechanisms in coordinating the activities of the economy and allocating its resources"; "The visible hand of management replaced what Adam Smith referred to as the invisible hand of market forces"

The eight general propositions (compressed; 1–3 verbatim)

• 1 "Modern multiunit business enterprise replaced small traditional enterprise when administrative coordination permitted greater productivity, lower costs, and higher profits than coordination by market mechanisms"

• 2 "The advantages of internalizing the activities of many business units within a single enterprise could not be realized until a managerial hierarchy had been created"

• 3 "Modern business enterprise appeared for the first time in history when the volume of economic activities reached a level that made administrative coordination more efficient and more profitable than market coordination"

• 4–8: the hierarchy became "a source of permanence, power, and continued growth"; managers' careers became technical and professional; management separated from ownership; managers preferred long-term stability and growth to current profits; large enterprises altered the structure of their sectors and of the economy

• McCallum's Erie diagram (Part 12) is this book's picture of the first such hierarchy

Chandler, A. D., Jr. (1977). The Visible Hand. Belknap/Harvard UP, Introduction (eight propositions) and Part II ch. 3 (railroads).

Administrative Behavior: an organization is a hierarchy of decisions

Administration is decision-making

• communication is "any process whereby decisional premises are transmitted from one member of an organization to another"; every decision has factual premises (testable) and value premises; "a science must consist of factual statements"

• "The Proverbs of Administration" (1946; ch. II): "for almost every principle one can find an equally plausible and acceptable contradictory principle" — span of control vs few levels, for example

Bounded rationality and satisficing

• 1947 speaks of "limits of rationality"; "bounded rationality" appears in Models of Man (1957): "The capacity of the human mind for formulating and solving complex problems is very small compared with the size of the problems whose solution is required for objectively rational behavior in the real world"

• 1957 introduction: "economic man maximizes … his cousin, administrative man, satisfices—looks for a course of action that is satisfactory or 'good enough'"; "Administrative theory is peculiarly the theory of intended and bounded rationality"

Link to the rest of the list

• the hierarchy of decisions is a control architecture for people: the same reason Ashby gave for teams (Part 7) and Dijkstra for levels (Part 9) — bounded capacity of the deciding unit

Simon, H. A. (1947). Administrative Behavior. Macmillan (p. 62; ch. II, VIII); bounded rationality and satisficing wording from the 1957 edition and Models of Man.

Assemblage theory: wholes at every scale whose parts can be detached and re-plugged

Assemblage (verbatim)

• wholes "characterized by relations of exteriority" — against Hegelian totalities: "a component part of an assemblage may be detached from it and plugged into a different assemblage in which its interactions are different"; "a relation may change without the terms changing"

• "the properties of the component parts can never explain the relations which constitute a whole"; a whole's properties are "the result not of any aggregation of the components' own properties but of the actual exercise of their capacities"

Scale

• "a series of differently scaled assemblages, some of which are component parts of others which, in turn, become parts of even larger ones"; each is an emergent individual, and its parts remain detachable

Read as architecture

• the same two commitments as the modular view of systems: parts with identities that survive rearrangement (Csete & Doyle's module, Baldwin & Clark's substitutable module), and wholes that are more than the sum of parts because of how the parts interact

DeLanda, M. (2006). A New Philosophy of Society. Continuum, Introduction and ch. 1–2 (pp. 10–12, 18, 28; quotes verbatim).

The Postmodern Condition: legitimation by performativity, not by grand narratives

Definition (verbatim)

• "Simplifying to the extreme, I define postmodern as incredulity toward metanarratives."

Knowledge as commodity

• "Knowledge is and will be produced in order to be sold, it is and will be consumed in order to be valorized in a new production: in both cases, the goal is exchange. Knowledge ceases to be an end in itself, it loses its 'use-value'."

• "Knowledge in the form of an informational commodity indispensable to productive power is already, and will continue to be, a major—perhaps the major—stake in the worldwide competition for power"

Performativity

• the system's demand on its members: "be operational (that is, commensurable) or disappear"; rules of a game "do not carry within themselves their own legitimation"

Why it is in this list

• an account of how organizations and technical systems justify their structure: by measured performance (Chandler's "greater productivity, lower costs", Thompson's "norms of rationality") rather than by truth or by a story about progress

Lyotard, J.-F. (1984). The Postmodern Condition. Univ. of Minnesota Press (transl. Bennington & Massumi), Introduction and §1–12 (quotes verbatim).

Bhidé: McKinsey 1939–1968 was built as a "system" of norms, policies and governance

Thesis (abstract, verbatim)

• the founders "built one of the world's leading management consulting firms by developing a 'system' of professional norms, approach to serving clients, personnel policies, organization, governance, and ownership … their vision and strategy derived more from a priori faith and personal values than from scientific evidence or financial calculation"

The product

• the inherited "General Survey Outline" "forced a strategic approach to client studies by requiring consultants to analyze a firm's industry and competitive position before considering anything specific to the organization"; a partner's report proposed the firm do only "diagnostic and general survey type of studies"

Numbers in the paper

• 1939 billings $284,000; 1952: 16 professionals (about one-sixth of the staff) left; 1955 pay: associates $15,000–20,000, principals $25,000–40,000, partners above $100,000

Why it is in the list

• the organization study — drawing a client's structure and redrawing it — became a repeatable product; the firm's own architecture (one firm, up-or-out, recruiting from business schools) was designed to deliver it consistently

1966

Australia

Bhidé, A. V. (1995). Building the professional firm: McKinsey & Co., 1939–1968. HBS Working Paper 95-010 (abstract and text; office dates as given there).

Kipping 1996: US consultancies sold the divisional structure to Europe, unevenly

The product and its take-up

• Channon's count for Britain: "at least 32 out of the largest 100 companies called in consultants during the 1960s … In 22 of these cases the service provider was McKinsey"

• scale in 1962: McKinsey about 200 consultants worldwide; Booz-Allen more than 800, over 70 in Europe; A. D. Little 30 professionals in Europe

Conclusion (verbatim)

• "Considerable differences in the consultancy markets in Britain, France, and Germany thus persist, despite the apparently increasing predominance of U.S. service providers … Even consultancies with the same name tend to carry out different activities, depending largely on the systemic context in which they operate."

Read with Chandler

• the structure of Part 13 travelled as a consulting product; whether it took hold depended on the national system it met — the question the next slide tests statistically

• 1994 marker in the paper: Andersen Consulting $3.5 bn revenue, 27,000 consultants

Kipping, M. (1996). Business and Economic History 25(1), 112–123 (phases, entries, country comparisons; Channon's count as cited there).

The European Corporation: the multidivisional form spread across three national systems anyway

Design

• extends the Harvard programme (Channon 1973 for Britain; Dyas & Thanheiser 1976 for France and Germany) to 1983 and 1993 for "the domestically owned members of the Top 100 industrial companies by sales" (67 British, 66 French, 63 German firms in 1993), from public documents

Diversification

• diversified (related + unrelated) firms: 1950 — France 36%, Germany 40%, Britain 27%; 1970 — "between half and two-thirds"; 1993 — around 80% in Britain and Germany, 59–65% in France (the two secondary sources differ)

Finding

• "big business in Europe has continued to follow a strategic and structural model pioneered in the United States … encapsulated long ago in Alfred Chandler's (1962) Strategy and Structure", despite "marked differences in corporate ownership, control, and managerial elites"; convergence held "for all types of ownership"

The "social science" in the title

• the authors read the result as a test between "positivist universalism and contextualist relativism": a structural regularity that holds across institutions, against "recent relativist perspectives on organizations found in postmodern, culturalist, and institutionalist social science" — a direct reply to the previous section's Lyotard

Whittington & Mayer (2000). The European Corporation. Oxford UP, ch. 1, 5–6. Chart: divisionalized share of domestic Top-100 industrial firms (1950, 1970 as described in the book; 1993 per Rowlinson 2001).

Yates 1989: systematic management made written communication the tool of control

Thesis

• between about 1850 and 1920, systematic management made formal internal communication "the principal tool for managerial control"; downward communication imposed procedures, upward communication monitored them, and lateral needs "gave birth [to] the memo"

Genres

• circular letters and general orders; manuals ("comprehensive organizational memory"); routine and special reports; forms and tables; graphs (Brinton 1914 is part of this story); memos; in-house magazines; conferences

Three cases

• the Illinois Central Railroad before 1887 ("safety, consistency, and honesty") and after ("compliance and efficiency", under ICC regulation); "Gradual Systematization at Scovill" (the weakening of foremen); Du Pont — a conservative first century, then "Radical Change from a New Generation", 1902–1920

Why it is in the list

• the channel capacity Ashby said a regulator needs (Part 7) was, for a firm, these genres and machines; McCallum's reports (Part 12) are the first instance

Yates, J. (1989). Control Through Communication: The Rise of System in American Management. Johns Hopkins UP (thesis, genres, technologies, three cases).

Yates 1993: insurers shaped the tabulating machines that then reshaped insurance work

Abstract (verbatim)

• the article "examines both the role that tabulating machinery played in shaping insurance firms' business processes and the simultaneous role that life insurance as a user industry played in shaping the development of tabulating technology between 1890 and 1950"

Thesis

• "life insurance use of tabulating equipment may be said to have co-evolved with tabulating technology"; user industries (with railroads, utilities and governments) shaped design, and vendor–user interaction shaped both industries

• "IBM had reached its dominant advantage over Remington Rand by responding technically to repeated competitive challenges … and by learning to work closely with major user industries such as insurance"

Why it closes the list

• an architecture is not fixed by its designers alone: the users' processes and the vendors' machines constrained each other over sixty years — the same mutual shaping Conway describes between organizations and the systems they build, on a historical time scale

Yates, J. (1993). Business History Review 67(1), 1–51 (abstract verbatim; dates from the article and its companion working paper).

Six recurring ideas and where the reading list states them

historical foundations (Parts 7–14)

Simon–Ando (fast within-block, slow between-block); Simon 1962; Ashby's homeostat (fast variables, slow parameter search); Pattee (upper level constrains rates)

Parnas 1972; Dijkstra THE levels; Yourdon–Constantine (coupling, cohesion); Baldwin–Clark (DSM, hidden modules); Alexander (subsets with few links); Simon (near-decomposability)

Baldwin–Clark design rules; Parnas "uses" relation; Brinton's hour- glass chart; Shannon (source/channel separation)

Dantzig–Wolfe (columns, prices); Benders (cuts); Simon–Ando (aggregation)

Wiener (feedback); Ashby 1956, 1958 (requisite variety); Conant– Ashby (good regulator = model); Thompson (buffering the technical core)

Conway; Brooks (surgical team); Chandler (strategy → structure); McCallum (reports up, authority down); Simon 1947 (hierarchy of decisions); Yates (genres of control); Kipping, Whittington–Mayer (diffusion of the M-form)

Compiled from the preceding sections; each cell names the references whose text states the idea.

What each modern architecture takes from the historical foundations

reference that supplies the foundation

Parnas 1972 (hide the decision where it is known); Shannon 1948; Simon 1962 (near-decomposability of the stack)

Newell 1982 (levels); Baldwin–Clark 2000; Dijkstra 1968 (level = what it hides)

Simon–Ando 1961; Ashby 1956/1958; Dantzig–Wolfe 1960; Benders 1962; Conant–Ashby 1970

Simon 1962 (Hora and Tempus); Pattee 1973 (control by constraint); Alexander 1964 (subsets with few links)

Shannon 1948; Parnas 1974/1979; Conway 1968 (packages follow communities)

Ashby 1952; Simon 1947 (means–ends chains); Wiener 1948 (feedback loops)

Compiled from the preceding sections; citations in the modern texts where they exist (e.g. Clark 2018 cites Doyle; Matni–Ames–Doyle cite Simon and Ashby-era control theory), otherwise the deck's reading.

What is verified, what is recomputed, and what could not be checked

Verbatim material

• every passage in quotation marks was checked against a copy of the text; Chandler 1988 (HBR), Wrege & Sorbo 2005 and Thompson 1967 were not accessible in full — their content comes from secondary reports and Nickols's compilation of Thompson's propositions
• Parnas 1974: only the abstract was verified; the list of relations on that slide is a reconstruction, and the "uses" material is from Parnas 1979
• Yourdon & Constantine: page numbers from a quotation page and a scan search; the six-term coupling list with "stamp" and "external" is Myers's, not theirs

Diagrams

• redrawn from the papers where a figure exists (Clark, Keutzer, Sangiovanni-Vincentelli, Matni–Ames– Doyle Fig. 2, Brooks Figs. 3–6, ROS 2 Fig. 2, Shannon Fig. 1, Conant–Ashby Fig. 1, Parnas 1976 Figs. 1–2, Chandler's U/M-form); drawn from the text where none does (Doyle–Csete bowtie, Gat's layers, Ashby's homeostat, the McCallum tree, Thompson's interdependence types, Alexander's graph)

Numbers that remain uncertain

• Whittington & Mayer 1983 figures and the exact 1993 French diversification share (59% vs 65% in two secondary sources); McKinsey Paris opening (September 1964 per Bhidé, 1965 per Kipping); the leaf split of Alexander's Bavra tree; Simon & Ando's original notation (restated after Shpak et al. 2004); the year Prudential first leased Hollerith equipment

Recomputed charts (parameters stated on each slide)

• Matni–Ames–Doyle Fig. 13 and Theorem 2 example; Nakahira bounds and two-layer sweet spot (λ, ε chosen by the deck); Csete–Doyle step responses and Bode integral; Chiang NUM dynamics (toy network); Simon's Hora–Tempus ratio (exact restart model); Simon–Ando diffusion on Simon's Fig. 1 matrix; Baldwin–Clark Q(k); Dantzig–Wolfe and Benders runs (toy instances); Brooks's curves (reconstructed formula); Kashtan–Alon and Whittington–Mayer bars from reported values

Deliberate choices

• sections follow the syllabus order; within the software section the papers run chronologically; Chandler 1988 is treated with McCallum in Part 12 because that is its subject
• symbols are defined on the slide where they first appear; forward references are avoided, backward references are marked by Part number

Verification done against open copies of the texts (publisher pages, author sites, PMC, arXiv, archive.org) in September 2026.