Happens-Before and Lamport Clocks

Symptom Two writes to the same key. Which one wins? Your first instinct is timestamps: whichever has the later wall-clock time is newer. This works in testing. In production you get a bug report saying an update vanished, and when you dig in, node B’s clock was 40 ms behind node A’s, so B’s later write carried an earlier timestamp and lost. NTP is running. NTP does not make clocks identical, it makes them close, and “close” is not “ordered.” ...

P vs NP

Symptom You are handed a scheduling problem. Two hundred tasks, precedence constraints, shared resources, and a deadline. Somebody wants an optimal schedule. Checking a proposed schedule takes seconds: walk the list, verify each constraint, add up the makespan. Finding one is different. Your search runs for a day and finds nothing. You try simulated annealing, then a genetic algorithm, then branch and bound. Each gives good schedules and none gives the best one, and you cannot tell whether the problem is hard or you are not clever enough. ...

The Coffman Conditions

Symptom Production is wedged. Not slow — wedged. CPU is at zero, no errors are being logged, and two threads are sitting in a lock wait with no timeout. The stack traces show thread A holding the account lock and waiting for the ledger lock, thread B holding the ledger lock and waiting for the account lock. Somebody restarts the service and it goes away. ...

The Chomsky Hierarchy

Symptom The most upvoted answer in Stack Overflow history is a refusal to answer. Someone asked how to match nested HTML tags with a regular expression, and the reply is a page of escalating horror about the centre not holding. It is funny, and it is also a theorem, which is not obvious from reading it. ...

The Universal Machine

Symptom You write a Python program. It runs. What ran it? CPython — itself a program, written in C, compiled to x86 instructions, executed by a CPU whose control unit is arguably interpreting microcode, possibly inside a virtual machine, on a kernel that scheduled it, all perhaps within a container image. At no point in that stack does anyone find it strange that a program’s job is running other programs. We build emulators, JITs, WebAssembly runtimes, Docker, QEMU, and browsers that download and execute arbitrary code from strangers, and treat every layer as ordinary engineering. ...

The Church–Turing Thesis

Symptom Somebody says “CSS is Turing-complete” and the room splits. Half the people treat it as a joke about a styling language, the other half as a serious claim with consequences. Both reactions are common and only one is right. ...

Linearity of Expectation

Symptom You are analyzing a hash table. You want the expected number of buckets that end up empty. The bucket occupancies are all tangled together — one key landing in bucket 3 makes every other bucket slightly less likely to be chosen — and the dependencies look like they will make the sum intractable. ...

The Birthday Bound

Symptom You need a short ID for uploads. Eight hex characters feels generous, so you take the first 32 bits of a hash and move on. At about 80,000 uploads, two files collide, and one of them silently overwrites the other, and the bug report says the customer’s invoice contains someone else’s line items. ...

The Two Generals Problem

Symptom You call the payment API. The request goes out. Nothing comes back. Did the charge happen? You genuinely do not know. Retrying might double-charge the customer. Not retrying might drop the payment. There is no third option available, and no amount of care in your client library creates one. ...

Conway's Law

Symptom The service has four layers. Nobody designed four layers. There were four teams. Or the version that arrives in a postmortem: the outage happened at the boundary between two services, in the retry logic, because each side assumed the other owned the deduplication. Both teams were right about their own component and neither had ever been in a room with the other. ...

The Halting Problem

Symptom Your CI has a test that hangs. Not fails — hangs. Somebody suggests the obvious fix: before running a test, check whether it terminates, and skip it if not. ...

Cantor's Diagonal Argument

Symptom Somebody proposes a tool that will find all the bugs. Not most bugs. All of them. The pitch has the shape: we enumerate the failure modes, we write a checker for each, we keep adding checkers, and the set of undetected bugs shrinks toward zero. ...

Amdahl's Law

Symptom The profile was unambiguous: 94% of wall-clock time in one loop, and the loop’s iterations are independent. You parallelise it across sixteen cores, the flame graph flattens exactly as predicted, and the end-to-end time goes from 40 seconds to 17. ...

Hyrum's Law and Postel's Principle

Symptom You fix a typo in an error message. Four days later a customer escalates: their alerting pipeline greps for the old string and has gone quiet. Or you make a function faster, and a test suite that had been green for two years starts failing intermittently — not because the function is wrong, but because it used to be slow enough to hide a race. ...

No Universal Lossless Compressor

Symptom Someone sends you a pitch deck. The claim is a compression algorithm that reduces any file by a guaranteed ratio, and — this is always the tell — that it can be applied repeatedly. Four gigabytes down to one, then one down to two fifty, and so on until the whole film is a few hundred bytes and a clever decoder. ...

The Pigeonhole Principle

Symptom You are asked to build a cache key. You have a 64-bit hash, and someone on the team says: “collisions are basically impossible, there are eighteen quintillion values.” Or: your service assigns short IDs to uploads, six characters of base-36, and you are wondering when you need to worry. ...