Topological Spaces and Computer Science

On a Monday morning in 1947, what waited for Richard Hamming at Bell Labs was not the output of the batch he had submitted over the weekend, but an error report. The relay computer had noticed through a parity check that something was wrong, and had stopped right there. The machine could see the error. Having seen it, it did nothing, and threw away an entire weekend.

Hamming’s thought was this: if it can detect an error, it should be able to locate it and fix it. To answer that question, he reached for a notion of “distance” between bit strings.

That is the first contact between computer science and topology. And the same thing kept happening afterwards. People who wanted to decide whether a program halts, who wanted to write the meaning of a while loop in mathematics, who wanted to know why a distributed system cannot agree. Every one of them, stuck at the wall, came back to the same question: for this kind of object, what does “near” mean?

This article follows six such scenes in chronological order. A scene where a metric sufficed; one where it did not and open sets were needed; one where nearness turned into an order; one where nearness became a figure. Topology was never sitting there as an abstract theory waiting to be applied. It was imported, each time, because something concrete demanded it.

Conclusion

• Computer science borrowed the language of topology not for abstraction’s sake, but because concrete problems stalled until “nearness” was redefined
• 1947, error-correcting codes: measuring nearness of bit strings with Hamming distance turns code design into the geometry of packing non-overlapping balls
• 1936 through the 1980s, the halting problem: properties of programs admit no metric. Reading “confirmable in finite time” as an open set draws the map semi-decidable = open, decidable = clopen
• 1969, the meaning of recursion: replacing a value with “how much is known so far” puts a topology on the order of information, and recursion means the end of an approximation sequence (a least fixed point)
• 1977, static analysis: abstract interpretation ties the concrete and abstract worlds with a Galois connection, carrying the same fixed-point skeleton into real tooling
• 1993, distributed consensus: drawing all possible executions as a figure turns impossibility into the topological fact that a connected figure cannot be torn apart
• 2002, data analysis: refusing to commit to one scale, and carrying all scales at once, turns the “shape” of a point cloud into a feature
• If a metric suffices, stay with the metric. Move up to topology only when the objects admit no metric at all

Assumptions

• Intended readers: people who can read the notation of sets and maps, and who have touched at least one of computability, types, static analysis, or distributed systems
• Goal: not to prove theorems, but to grasp how each field came to borrow topological language and what it gained
• Prerequisites: the basics of sets, maps, and limits. Algebraic topology (homology and so on) is covered only in outline
• There are six interactive figures. The text stands on its own without them

The Question Running Through: What Is “Near”?

Before the stories, three tools. Each is a way of putting “near” into words.

The first is distance. A pair of a set $X$ and a function $d: X \times X \to \mathbb{R}_{\geq 0}$ is a metric space when it satisfies these three conditions.

1. $d(x, y) = 0 \iff x = y$ (identity)
2. $d(x, y) = d(y, x)$ (symmetry)
3. $d(x, z) \leq d(x, y) + d(y, z)$ (triangle inequality)

Nothing requires the objects to be real numbers. Bit strings and text qualify too, as long as a $d$ satisfying the three conditions exists. Chapter 1 needs nothing beyond this generality.

The second is open sets. Once a distance is fixed, the open ball $B(x, \varepsilon) = \{ y \in X \mid d(x, y) < \varepsilon \}$ is defined: in plain words, the neighbourhood of $x$. A subset $U$ is open when, for every point of $U$, a sufficiently small ball around that point fits inside $U$. Read it as a set that contains each of its points together with its neighbourhood.

Swap the ruler and the shape of the ball changes, as the figure below shows.

Here is the first discovery. Euclidean, Manhattan, and Chebyshev distance produce completely different shapes, yet exactly the same family of open sets, because each ball contains a smaller ball of the others. So a metric determines the open sets, but the open sets do not determine a metric. A metric carries information that is beside the point.

The third is topological spaces. So throw the number away and keep only the family $\mathcal{O}$ of open sets as the structure.

1. $\emptyset \in \mathcal{O}$ and $X \in \mathcal{O}$
2. The union of any number (possibly infinite) of members of $\mathcal{O}$ belongs to $\mathcal{O}$
3. The intersection of finitely many members of $\mathcal{O}$ belongs to $\mathcal{O}$

Unions may be infinite; intersections may not. That asymmetry becomes meaningful in chapter 2.

Continuity, too, needs no distance. $f: X \to Y$ is continuous when the preimage $f^{-1}(V)$ of every open $V$ is open. Continuity asks “once we decide what we want to know about the output, what is enough to know about the input,” and that direction lines up exactly with the dependency structure of computation.

That is the whole toolkit. Now the six scenes, in order.

1947: The Weekend That Vanished, and Hamming Distance

The “near” of this chapter: how many bits two strings differ in. The most straightforward case, fully served by a metric.

“If it can detect it, it should be able to fix it”

Back to the opening scene. The relay computers at Bell Labs had a parity check and stopped when they found an error. A machine that can only detect wastes the whole weekend. Hamming later recalled his frustration along these lines: if the machine can detect an error, why can it not locate it and correct it?

The plain answer is “add more parity bits.” But how many bits? Arranged how, to reach correction rather than mere detection? And how many is enough? No pile of ad hoc tinkering answers those three.

Holding a ruler up to bit strings

Hamming changed the frame. He viewed the codewords as a subset of $\{0, 1\}^n$ and measured how many bit positions two words differ in.

That is Hamming distance. Counting differing positions is a plain definition, yet it satisfies the metric axioms.

• No differing position means the same word (identity)
• The count is the same from either side (symmetry)
• Changing $x$ into $z$ directly costs no more bits than going via $y$ (triangle inequality)

$\{0, 1\}^n$ became a finite metric space of $2^n$ points: purely discrete, with no continuity or limits anywhere in sight.

Design becomes geometry

The moment a distance is in place, error correction turns geometric. A $t$-bit error means the received word drifts to within distance $t$ of the codeword sent. Therefore:

• If the radius-$t$ balls around the codewords do not overlap, the ball the received word lands in pins down exactly one original (correctable)
• If they overlap, there is no deciding which one to restore (not correctable)

Writing $d$ for the minimum distance of the code, the balls stay disjoint exactly when $d \geq 2t + 1$, that is:

Designing a code is packing balls into a finite metric space. Pick some vertices in the figure and watch it happen.

Counting the volume of a ball gives the limit. A ball of radius $t$ holds $\sum_{i=0}^{t} \binom{n}{i}$ words, so placing $M$ codewords requires:

This is the Hamming bound (the sphere-packing bound). The repetition code $\{000, 111\}$ in the figure meets it with equality, $2 \times (1 + 3) = 8 = 2^3$: the smallest example of a perfect code, packed with no room to spare. The $(7, 4)$ code from Hamming’s 1950 paper is perfect too, at $16 \times (1 + 7) = 128 = 2^7$.

Key points

• Hamming distance satisfies the metric axioms, so the set of all bit strings is a finite metric space
• Correctability is exactly “the radius-$t$ balls are disjoint,” and design becomes ball packing
• “More information” and “more robustness” become one tug of war: more balls, or bigger ones

And topology never appears in this chapter. A distance on a finite set is all it takes. If a metric suffices, stay with the metric. The story changes when an object appears that admits no metric at all.

References for this chapter

• Hamming code - Wikipedia
• Hamming bound - Wikipedia
• Richard W. Hamming, “Error Detecting and Error Correcting Codes”, Bell System Technical Journal, 1950 (the original)
• F. J. MacWilliams, N. J. A. Sloane, “The Theory of Error-Correcting Codes”, North-Holland (the standard reference)

“It Never Halts” Can Never Be Confirmed, and Open Sets

The “near” of this chapter: nearness between properties of programs. The first object where no number of metres will do, and topology is required.

“Undecidable” does not say enough

As Turing showed in 1936, no algorithm decides whether an arbitrary program halts. The halting problem is undecidable.

Work through it by hand, though, and the conclusion feels a little coarse, because the two sides are not symmetric at all.

• If it does halt, keep running and you will eventually see that it stopped
• If it does not halt, no amount of waiting ever settles “it will not stop”

“It halts” can be confirmed in finite time but never refuted. Computability theory calls this semi-decidability (recursive enumerability). The decidable/undecidable dichotomy cannot express the asymmetry. So where is the language that can?

Reading the asymmetry of observation as topology

In the 1980s, Michael Smyth and Steven Vickers organized that asymmetry into topological language. Call a property $P$ observable when “if $P$ holds, it can be confirmed in finite time.” Then:

• Finitely many observable properties can be checked in turn and combined, so finite intersections are observable
• If any one of infinitely many suffices, the one that holds is found in finite time, so infinite unions are observable
• That infinitely many all hold cannot be confirmed in finite time, so infinite intersections are not allowed

Word for word, the axioms from the preparation. That asymmetry — infinite unions, only finite intersections — was the machine’s own constraint all along: finitely many observations can be waited for, infinitely many cannot. The title of Vickers’s book, Topology via Logic, points at exactly this coincidence.

The correspondence:

• Semi-decidable property = open set
• Property whose refutation is semi-decidable = closed set
• Decidable property = clopen (both open and closed)

“It halts” is open, “it does not halt” is closed, and since it is not clopen it is not decidable. Undecidability became a statement about shape: open, but not closed.

Observing one bit at a time makes the difference tangible. Looking at the very same sequence, the properties settle at wildly different moments.

Compactness is what makes a search terminate

Make the stage concrete: the set $2^{\omega}$ of all infinite bit sequences, which you can read as a program’s output stream or an endless history of observations. The basic open sets here are the cylinders “the first $n$ bits have such-and-such values,” exactly the properties decidable from a finite prefix.

This space is compact, and a computational fact falls straight out of that. The clopen sets of a compact space are finite unions of cylinders, so a decidable property is always decidable from some finite prefix. There is no convenient property that is decidable yet needs reading infinitely far.

Martín Escardó turned this around. He exhibited Haskell programs that exhaustively search sets of infinite bit sequences and finish in finite time. Code that “tries all” of infinitely many candidates really does terminate, and the reason is that the space is compact.

Key points

• Open = confirmable in finite time, closed = refutable in finite time, clopen = decidable
• The asymmetry in the axioms matches the constraint that only finitely many observations can be waited for
• Compactness corresponds to “exhaustive search terminates”

Open sets gave structure to an object no metric could measure. In the next chapter, this idea of “finite observation” goes after the meaning of programs themselves.

References for this chapter

• Halting problem - Wikipedia
• Topological space - Wikipedia
• Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem”, 1936 (the original)
• Steven Vickers, “Topology via Logic”, Cambridge University Press (a book built entirely on reading open sets as observations)
• Martín Escardó, “Infinite Sets That Admit Fast Exhaustive Search”, LICS 2007 (exhaustive search over infinite sets that terminates)

The Meaning of a While Loop Cannot Be Written Down, and the Scott Topology

The “near” of this chapter: nearness between intermediate states of a computation. This is where nearness turns into an order.

The man who argued against it built the model

In the late 1960s at Oxford, Christopher Strachey was trying to define the meaning of programs as mathematical objects — denotational semantics. Assignment and branching can be written as functions. Recursion and while stop the effort dead.

1fact n = if n == 0 then 1 else n * fact (n-1)

fact is defined using fact. One would like the meaning to be “the function $f$ satisfying this equation,” but whether such an $f$ exists, and which to pick if several do, is unclear. And since some inputs never terminate, it cannot be written as “a function returning a value on every input.”

Building a model of the λ-calculus is a harder wall. Since λ-calculus applies functions to functions, the space of meanings $D$ needs $D \cong D \to D$. Cantor’s diagonal argument gives $\lvert D^D \rvert > \lvert D \rvert$ for any $D$ with at least two elements, so no such $D$ exists among ordinary sets and functions.

Dana Scott, who arrived in Oxford in 1969, took that as grounds for holding that the untyped λ-calculus admits no mathematical meaning. Then, in the autumn of that same year, he built the model himself. What broke the wall?

Replace a value with “how much is known so far”

Treat a value not as a finished product but as a record of how much is known so far.

• Read $x \sqsubseteq y$ as “the information in $x$ is contained in $y$ ($y$ is more defined)”
• Write $\bot$ (bottom) for the state where nothing is known: the meaning of a non-terminating computation
• An infinite list settled to its first 10 elements has less information than one settled to 20

When such an ordered set is directed complete (every directed subset has a supremum), it is a directed complete partial order (dcpo). Directed means “any two intermediate states have a third refining both”; directed complete means “where ever-growing information heads always exists.” The supremum $\bigsqcup$ is the end of continuing the computation.

Here is where topology enters. The Scott topology takes as open the sets satisfying two conditions.

1. Upward closed ($x \in U$ and $x \sqsubseteq y$ imply $y \in U$)
2. Inaccessible by directed suprema (if $\bigsqcup D \in U$, then some $d \in D$ is already in $U$)

Condition 1 says “once true, it stays true as information grows”; condition 2 says “if it becomes true in the limit, it is already true at a finite stage.” In the language of the previous chapter, a Scott open set is a property confirmable from finite information alone. The rereading discovered for the halting problem became the foundation of semantics.

Continuity takes a concrete form under this topology.

More information in means more information out, and taking the limit before or after makes no difference. A computation producing finite output from finite input satisfies it. A function that must see infinite information at once does not, and cannot be implemented either.

Recursion means the end of the approximations

A Scott continuous $f$ on a dcpo with $\bot$ has a least fixed point (Kleene’s fixed point theorem).

The meaning of fact is the limit of the approximations obtained by unfolding the definition one step at a time from $\bot$. After $n$ unfoldings only inputs below $n$ are correct, and the end of that sequence is the meaning of the program. Inputs where it does not terminate keep the value $\bot$.

The $D \cong D \to D$ wall falls to the same idea. Restrict the function space to Scott continuous functions only and the cardinality contradiction disappears; that is how Scott constructed $D_\infty$. “Only computable functions count as functions” turned out to be expressible as topological continuity.

Key points

• A topology on the order of information puts non-terminating computation inside the semantics as $\bot$
• Recursive definitions get a unique, natural solution: the least fixed point
• Lazy evaluation and infinite lists are handled directly as directed suprema

Metric intuition has to be dropped, though. The Scott topology is not Hausdorff. An open set containing $\bot$ is upward closed, so it can only be the whole space, and $\bot$ cannot be separated from any other point. The fact that “a computation that has returned nothing yet” is indistinguishable by finite observation shows up as the failure of a separation axiom.

References for this chapter

• Domain theory - Wikipedia
• Scott continuity - Wikipedia
• Dana S. Scott, “Outline of a Mathematical Theory of Computation”, 1970 (the original)
• Dana S. Scott, Christopher Strachey, “Toward a Mathematical Semantics for Computer Languages”, 1971
• Samson Abramsky, Achim Jung, “Domain Theory”, Handbook of Logic in Computer Science (a survey to read end to end)

An Approximation That Does Not Lie, and Abstract Interpretation

The “near” of this chapter: the order of how coarse an approximation is. Chapter 3’s framework descends into everyday tooling.

Exact answers are undecidable, sloppy ones are lies

You want to know “can this variable be zero,” “is this array access in range,” without running the program. The executions are infinite in number, so trying them all is out, and as chapter 2 showed, answering exactly runs into undecidability.

So you approximate. And a new fear appears: an approximation that lies is no guarantee at all. The problem becomes how to ensure the error always falls on the safe side.

A Galois connection carries the soundness

Abstract interpretation, as Patrick and Radhia Cousot set it out in 1977, formalized that approximation with orders and fixed points.

• Prepare the concrete meaning (the set of all executions) and the abstract meaning (signs, intervals, types) as ordered sets
• Connect them with a Galois connection $\alpha: C \to A$, $\gamma: A \to C$, a pair satisfying $\alpha(c) \sqsubseteq a \iff c \sqsubseteq \gamma(a)$, which guarantees that abstraction does not lose soundness
• Analysis becomes computing the least fixed point of a monotone function on the abstract domain. Ever watched a static analyzer burn time on one loop? That is this fixed point being found through approximations

The skeleton is identical to chapter 3. Only the purpose differs: defining meaning there, building an analyzer here.

The link between orders and topologies matters here too. Topologies on a finite set correspond one-to-one with preorders, a correspondence Alexandrov gave in 1937. From a topology, defining $x \leq y$ as “every open set containing $x$ contains $y$” yields a preorder (the specialization order); conversely the upward closed sets of a preorder form a topology. The $T_0$ separation axiom corresponds to antisymmetry of the preorder.

Abstract domains, subtyping, dependencies, causal order — all order structures, and by this correspondence all already topological spaces. The rule “upward closed sets are open” reads, computationally, as “a property that keeps holding once it holds, however much more information arrives.”

Key points

• A Galois connection is the framework guaranteeing that coarsening never turns into lying
• Termination of the analysis becomes a question about the height of the order (the length of its chains)
• On domains of infinite height the iteration never stops, so an operator forcing convergence (widening) is introduced

Widening cuts the process off after finite observation instead of waiting to reach the limit: the implementer’s answer to chapter 2’s constraint that only what is confirmable in finite time can be handled.

References for this chapter

• Abstract interpretation - Wikipedia
• Galois connection - Wikipedia
• Patrick Cousot, Radhia Cousot, “Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints”, POPL 1977 (the original)
• P. S. Alexandroff, “Diskrete Räume”, Matematicheskii Sbornik, 1937 (finite topologies and preorders)

The Reason Nobody Can Agree Was in the Shape, and Simplicial Complexes

The “near” of this chapter: nearness between possible executions. Here nearness becomes a figure.

The impossibility of 1985

Getting several processes to agree on a value (consensus) is a basic job in a distributed system. Yet in 1985 Fischer, Lynch, and Paterson proved that if the system is asynchronous and even one process may crash, no algorithm reliably reaches agreement. Known as the FLP impossibility, it received the Dijkstra Prize in 2001.

The proof tracks the ability to stay in an undecided state, and the conclusion is crisp. The intuition for why, less so. Worse, changing the setting — “at most two of three processes may fail” — meant rebuilding the argument each time. Was there no clearer way to decide, problem by problem, what is solvable?

1993: three groups arrive at the same figure

At STOC 1993, three groups independently brought in the same idea: Herlihy and Shavit, Borowsky and Gafni, Saks and Zaharoglou. They drew the whole space of executions as a figure.

• A vertex is the fact that “a given process is in a given local state”
• A simplex (a set of vertices) is the compatibility relation “these local states can occur simultaneously”
• The resulting simplicial complex is the protocol complex

Then the following can be shown.

• In an asynchronous model where processes may crash, the protocol complex stays connected as execution proceeds: adjacent executions differ only in what a single process sees, so the states join up smoothly
• The output complex of binary consensus is not connected, because the world that decides $0$ and the world that decides $1$ lie apart
• There is no continuous map (simplicial map) from a connected complex to a disconnected one

So the reason consensus cannot be solved was the topological fact that a continuous map cannot tear a connected figure apart. Why no implementation trick gets around it becomes visible as a shape. For the message passing model, Biran, Moran, and Zaks gave a characterization by connectivity in 1990.

Key points

• The connectivity of the protocol complex settles the impossibility of agreement outright
• Problems are handled uniformly instead of rebuilding an argument each time. The impossibility of $k$-set agreement follows from Sperner’s lemma, a combinatorial statement about colourings of a triangulation that is essentially equivalent to Brouwer’s fixed point theorem
• “What is solvable” becomes the question of whether a simplicial map from the input complex to the output complex exists

The 2004 Gödel Prize was awarded for this line of results. Counting in discrete mathematics passes through a topological theorem and comes out as a limit on distributed systems.

References for this chapter

• Consensus (computer science) - Wikipedia
• Sperner’s lemma - Wikipedia
• Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson, “Impossibility of Distributed Consensus with One Faulty Process”, Journal of the ACM, 1985 (the FLP original)
• Maurice Herlihy, Nir Shavit, “The Topological Structure of Asynchronous Computability”, Journal of the ACM, 1999
• Maurice Herlihy, Dmitry Kozlov, Sergio Rajsbaum, “Distributed Computing Through Combinatorial Topology”, Morgan Kaufmann (the textbook for this area)

Seeing Holes in a Cloud of Points, and Persistent Homology

The “near” of this chapter: nearness among points in a cloud — without committing to a single scale.

The scale cannot be chosen

Sensor placements, point clouds from embedded time series, high-dimensional feature vectors. Sometimes you want to know not just “how many clusters” but “does it form a loop,” “is there a hole.” Yet a bare collection of points has no such structure.

Join points within radius $\varepsilon$ and holes do appear. But shrink $\varepsilon$ and it falls into isolated points; grow it and it becomes one blob. The wall here is that no single $\varepsilon$ is the right one.

Carry every scale at once

The answer Edelsbrunner and colleagues gave in 2002 was blunt: do not choose one — carry all of them.

1. Put a distance on the point cloud (as in chapter 1, whatever suits the objects)
2. Join points within radius $\varepsilon$ into a simplicial complex (the Vietoris-Rips complex)
3. Grow $\varepsilon$ from $0$ and record how holes are born and filled

flowchart LR
  points["Point cloud<br/>a metric space"] --> complex["Simplicial complex<br/>join within ε"] --> homology["Homology<br/>number of holes"] --> barcode["Barcode<br/>born when, filled when"]

That record is persistent homology. Features that survive long are essential structure; features that vanish quickly are noise. Refusing to fix a scale is itself what makes it robust to noise.

Key points

• Coverage in sensor networks: build a complex from the sensors’ ranges and detect gaps by whether holes exist (de Silva and Ghrist, 2007)
• Periodicity in time series: turn the series into a point cloud by delay embedding and look for circular structure (a one-dimensional hole)
• Features for machine learning: add summary statistics of persistent homology to ordinary features

Build a complex from a distance, compute invariants from the complex. This application walks through distance, discreteness, and topology in exactly the order this article followed.

References for this chapter

• Persistent homology - Wikipedia
• Simplicial complex - Wikipedia
• Herbert Edelsbrunner, David Letscher, Afra Zomorodian, “Topological Persistence and Simplification”, Discrete & Computational Geometry, 2002 (the original)
• Vin de Silva, Robert Ghrist, “Coverage in Sensor Networks via Persistent Homology”, Algebraic & Geometric Topology, 2007
• Herbert Edelsbrunner, John Harer, “Computational Topology: An Introduction”, American Mathematical Society

What the Six Stories Show

Lined up, one thread runs through them. Every chapter reopens the question “what does near mean for this object,” and the wall comes down the moment an answer arrives. And with each reopening, the expression of nearness moved further from numbers.

flowchart LR
  n1["Nearness as<br/>a number"] --> n2["Nearness as<br/>open sets"] --> n3["Nearness as<br/>an order"] --> n4["Nearness as<br/>a figure"]
  n1 -.- c1["Error-correcting codes"]
  n2 -.- c2["The halting problem"]
  n3 -.- c3["Semantics, static analysis"]
  n4 -.- c4["Consensus, data analysis"]

Here is the terminology as a table: how the topological words on the left read as words about computation on the right.

Other Contact Points

Topics in the same lineage that do not need a chapter of their own.

• Stone duality, types, and logic: Boolean algebras determine Stone spaces, distributive lattices determine spectral spaces, frames determine locales, and each pair determines the other. “The algebra of properties” and “the space of things satisfying them” are two sides of one coin. Abramsky’s Domain theory in logical form matched semantic domains with the logic of observable properties over them: chapter 2’s “open set = observable property” seen from the algebraic side
• Homotopy type theory: types as spaces, terms as points, identity types as spaces of paths. It runs as a formal system in proof assistants such as Cubical Agda
• Pruning by the triangle inequality: $d(q, x) \geq \lvert d(q, p) - d(p, x) \rvert$ lets one distance measurement discard candidates, which is what BK-trees and VP-trees prune on. Conversely, treating a quantity that violates the triangle inequality (cosine similarity, say) as a distance makes an index go quietly wrong
• Banach’s fixed point theorem: on a complete metric space, a map with $d(f(x), f(y)) \leq c \cdot d(x, y)$ for $c < 1$ has a unique fixed point. Where chapter 3 handled recursion with order and a least fixed point, this plays the same role with distance and a unique fixed point, used for the convergence of numerical iteration and in metric semantics of concurrent processes
• Network topology: that “topology” is about the shape of a graph, not about applying theorems of topology. The word is shared; the theory is not

Taking It Back to Work

You may have read this far thinking it is interesting but unrelated to tomorrow’s job. Fair enough: chances to embed a topological theorem in an implementation are rare. What does carry over is the judgement.

1. Check the axioms of anything calling itself a distance. Embedding similarities, hand-rolled closeness scores, domain-specific diffs. Before any of them backs an index or a pruning rule, check the triangle inequality once. Prune with a quantity that violates it and candidates that should survive get dropped — quietly, which is what makes it hard to catch later.

2. Split requirements by whether confirmation terminates. Health checks, retries, timeouts: all of them are really about the asymmetry “YES arrives eventually, NO never does.” In chapter 2’s terms, you are designing where to cut off in a world where only open sets are observable. It is worth asking whether any branch assumes a NO that can never be settled.

3. Give every approximation an order and a fixed point. Chapter 4’s skeleton is not limited to static analysis. Anything that accumulates information in stages — a warming cache, a retry loop converging on an answer, a staged rollout’s decision rule — is steadier when the order and the monotonicity are decided up front. And if the height is infinite, plan the widening (the cut-off) from the start.

4. Impossibility pays off the earlier you learn it. Chapter 5 says plainly that some walls no implementation gets around. A design chasing perfect agreement in an asynchronous model can be stopped before it starts. Knowing for certain that there is no silver bullet is itself an input to the design.

5. For an unfamiliar object, first ask whether a metric fits. If it does, chapter 1’s toolkit applies as is. If it does not, enumerate what can be observed in finite time instead. Even that two-way split tends to bring the shape of an awkward object into focus.

A Small Glossary

The words used above, boiled down. The rigorous definitions are in the text and the references; this table only gives the feel of each one.

Caveats

• Each chapter keeps only the main thread of its story; in reality many researchers contributed to each. Read the years as markers for when the principal papers appeared
• The Hamming anecdote is a summary of his own recollection, not a verbatim quotation
• The Scott topology is not Hausdorff and cannot be generated by a metric. Carrying over the metric intuition that “nearby points can be separated” leads to mistakes
• Topological arguments are strong for founding semantics and proving impossibility, not for speeding up everyday implementation. Chapters 1 and 6 are the ones closest to implementation
• Persistent homology tends to cost on the order of the cube of the number of points in a naive implementation, so applying it directly to large data is hard
• The correspondences “open = semi-decidable” and “compact = exhaustive search terminates” hold only when an appropriate topology is in place

Summary

• In all six scenes, a wall came down when someone redefined what “near” means for the object at hand
• Chapter 1: recognizing Hamming distance as a metric turns code design into ball packing, expressing correction strength and information capacity as one geometry
• Chapter 2: reading “confirmable in finite time” as an open set gives semi-decidable = open and decidable = clopen, and compactness yields “decidable implies decidable from a finite prefix”
• Chapter 3: replacing values with an order of information brings in a topology, so recursion is defined as a least fixed point with non-terminating computation kept inside as $\bot$
• Chapter 4: abstract interpretation guarantees soundness of approximation with a Galois connection and a least fixed point, and an order is already a topology
• Chapter 5: drawing all executions as a simplicial complex turns impossibility into the topological fact that a connected figure cannot be torn apart
• Chapter 6: carrying every scale instead of choosing one extracts the shape of a point cloud as a noise-resistant feature
• If a metric suffices, stay with the metric; move up to topology when the objects admit none. That judgement is what the six chapters have in common

Further Reading

The original papers sit in each chapter’s own reference list. What follows is for reading end to end.

• James R. Munkres, “Topology”, Prentice Hall (the standard textbook)
• G. Gierz et al., “Continuous Lattices and Domains”, Cambridge University Press (orders and topologies, systematically)
• Steven Vickers, “Topology via Logic”, Cambridge University Press (exactly the viewpoint of chapters 2 and 3)
• Maurice Herlihy, Dmitry Kozlov, Sergio Rajsbaum, “Distributed Computing Through Combinatorial Topology”, Morgan Kaufmann (for chapter 5 in earnest)
• Richard W. Hamming, “The Art of Doing Science and Engineering”, Gordon and Breach (his own recollections behind chapter 1)
• Samson Abramsky, “Domain Theory in Logical Form”, Annals of Pure and Applied Logic, 1991 (the duality of semantics and logic)
• Peter T. Johnstone, “Stone Spaces”, Cambridge University Press (Stone duality)
• The Univalent Foundations Program, “Homotopy Type Theory: Univalent Foundations of Mathematics”, 2013 (types as spaces)
• 内田伏一『集合と位相』裳華房 (a Japanese introduction)