The idea: mask a fault by voting

Any part can fail. One way to keep going is to build the part three times and let them vote. This is triple modular redundancy (TMR). Three modules get the same input and do the same work. A voter passes on the answer that at least two of them agree on. If one module gives a wrong answer, the other two outvote it. The fault is masked: the output is right, at once, with no retry and no failover.

Input x = 7 goes to three copies M1, M2, M3 of version A, each computing 3 times x. M1 and M3 output 21, M2 is faulty and outputs 17. A 2-of-3 voter sees two 21s and outputs 21, which is correct
TMR: three copies and a majority voter; one wrong output is outvoted.

On the page each module computes y = 3 × x. Pick a design, an input and a fault and press Vote. The input flies to the three modules, their outputs fly to the voter's slots, and the voter colours the agreeing slots green and the odd one red. The bottom panel turns MTTF and MTTR into availability for three ways of wiring the modules.

What TMR masks, and what it does not

With no fault, all three modules say 21 and the output is 21 (Demo 1). A transient fault, such as a bit flipped by a cosmic ray, makes M2 say 17 (21 XOR 4). M1 and M3 still agree on 21, so the output is right, and the voter can also report M2 as the module that disagreed (Demo 2). TMR is used this way in spacecraft computers, aircraft flight controls and radiation-hardened FPGAs.

TMR masks one faulty module. If M2 flips a bit and M3 is stuck at 0, the three outputs are 21, 17 and 0. No two agree, so the voter cannot pick a value. It raises an error instead (Demo 3). The fault is now detected but not masked. If the two faulty modules happened to give the same wrong value, the voter would pass that value on. To mask f faults you need 2f + 1 modules.

The voter itself is a single part in series with everything else. If it fails, the system fails. Real designs keep the voter very simple, or triplicate it too.

Common-mode failures and N-version programming

TMR assumes the three modules fail independently. A common-mode failure breaks that: one cause hits all copies at once. A shared power supply, the same overheating rack, or the same design bug. On the page, version A keeps 3 × x in 8 bits. For x = 7 that is fine. For x = 120 the true answer 360 does not fit, and every copy of A returns 360 − 256 = 104. All three agree, the voter sees a unanimous 104, and a wrong answer goes out with no alarm (Demo 4). Copying a module copies its bugs.

N-version programming attacks design faults. Several teams write the module independently from the same specification, and the versions vote. On the page, M1 runs A, M2 runs B (16 bits) and M3 runs C (x + x + x). Now A's bug hits only one version: the outputs are 104, 360 and 360, and A is outvoted (Demo 5). Airbus flight-control computers use different hardware and software teams for this reason.

N-version programming is not a cure-all. Experiments (Knight and Leveson, 1986) found that independent teams often make the same mistakes on the same hard inputs, and a mistake in the shared specification reaches every version. It also costs N times the development.

MTTF, MTTR and availability

MTTF (mean time to failure) is how long a module runs, on average, before it fails. MTTR (mean time to repair) is how long it then stays down. Over a long time the module is up a share

A = MTTF / (MTTF + MTTR)

of the time. This share is its availability. With MTTF = 990 h and MTTR = 10 h, A = 990 / 1000 = 0.99. Note that a faster repair helps as much as a longer life: halving MTTR to 5 h gives 990 / 995 ≈ 0.995.

Series and parallel

When a system needs all its parts (they are in series), its availability is the product: three modules of 0.99 give 0.99³ = 0.970299. Every extra part makes it worse. When any one part is enough (they are in parallel), the system is down only when all are down at once, so the unavailabilities multiply: 1 − 0.01³ = 0.999999. TMR sits between the two: it needs 2 of 3 up, which gives 3A² − 2A³ = 0.999702 (Demo 6). These formulas assume the parts fail independently.

Three modules with availability 0.99. In series all must be up: 0.99 cubed is 0.970299, down 260 hours a year. In parallel any one is enough: 1 minus 0.01 cubed is 0.999999, down 31.5 seconds a year, but a wrong answer is not caught. Two of three with a voter: 3A squared minus 2A cubed is 0.999702, down 2.6 hours a year, and one wrong answer is outvoted
Series multiplies availabilities, parallel multiplies unavailabilities, and 2-of-3 lies in between.

Plain parallel spares give more uptime than TMR, so why vote? A spare helps only when a failed module stops. A module that keeps running but gives a wrong answer is not caught by a spare. TMR trades some uptime for catching wrong answers.

The nines

Availability is often quoted as a number of nines: 99.9 % is "three nines". Downtime per year is (1 − A) × 8760 h:

availabilityninesdowntime per year
99 %287.6 h (3.65 days)
99.9 %38.76 h
99.99 %452.6 min
99.999 %55.26 min
99.9999 %631.5 s

Each extra nine cuts the downtime ten times. Service level agreements (SLAs) are written in these terms, and a system in series with a 99.9 % dependency can never be better than 99.9 %.

When TMR hurts

TMR needs two good modules. If each module is up less than half the time, two being up at once is rarer than one. With MTTF = 400 h and MTTR = 600 h, A = 0.4, and TMR gives 3(0.16) − 2(0.064) = 0.352, worse than a single module (Demo 7). The same holds for reliability over a mission with no repair: with R(t) = e−t / MTTF, TMR beats one module only while R > 0.5, that is for t < 0.69 × MTTF. TMR suits short missions or quick repair, not long unattended runs.

See also Circuit Breaker and Bulkhead and Retry, Exponential Backoff and Jitter for living with a failing remote service, How Raft Elects a Leader and Replicates a Log for replicas that agree on a log by majority, Byzantine Fault Tolerance: PBFT for voting when replicas may lie (3f + 1 of them), RAID 0, 1, 5 and 10 for redundancy across disks and Hamming Code (7,4) for redundancy inside the data.

See also Fault Tree Analysis: Gates, Minimal Cut Sets and P(top), which works down from one failure to the minimal cut sets and shows how a shared power supply undoes redundancy.

What the page leaves out

A faulty voter and triplicated voters; time redundancy (run twice and compare) and duplex systems with comparison; standby spares, hot and cold, and failover time; the full reliability curve R(t) and Markov models with repair; dependent failures in the formulas; bathtub curves and MTBF; and how real N-version projects split hardware, compilers and languages.

On the mind map

Open the Distributed Systems mind mapDistributedSystemsReplication: copies of data · what reads seeReplicationPartitioning: split data over nodesPartitioningTime and membership: order events, know who is aliveTime and membershipConsensus: agree on one value or logConsensusTransactions: one change across many servicesTransactionsMessaging: send events between systemsMessagingKafka internals: a replicated append-only logKafka internalsRedis internals: one thread, data in memoryRedis internalsKubernetes: reconcile desired stateKubernetesResilience and speed: stay up and fast under loadResilience and speedCache strategiesCache strategiescache-aside, write-through, write-behindCircuit breakerCircuit breakerstop calling a failing serviceTMR and N-VersionMajority masks one fault, not a shared bugFault Tree AnalysisFault Tree AnalysisMinimal cut sets; AND multiplies, OR 1−ΠToken vs leaky bucketToken vs leaky buckettoken allows bursts; leaky smoothsBackpressureBackpressurebounded queue: block, drop or ask lessLatency vs throughputLatency vs throughputnear full load, queues blow up p99Monolith vs microservicesMonolith vs microservicesfunction call vs network callDistributed tracingDistributed tracingtraceparent links spans across servicesRate limit windowsRate limit windowsfixed window lets 2x burst at the edgeRetry, backoff and jitterRetry, backoff and jitterWait 2^n plus random, or retries stampedeHedged requestsHedged requestsSlow? Send a copy; take the first replyOpen the Distributed Systems mind mapDistributed Systemsstay up and fast under loadResilience and speedCache strategiesCache strategiescache-aside, write-through, write-behindCircuit breakerCircuit breakerstop calling a failing serviceTMR and N-VersionMajority masks one fault, not a shared bugFault Tree AnalysisFault Tree AnalysisMinimal cut sets; AND multiplies, OR 1−ΠToken vs leaky bucketToken vs leaky buckettoken allows bursts; leaky smoothsBackpressureBackpressurebounded queue: block, drop or ask lessLatency vs throughputLatency vs throughputnear full load, queues blow up p99Monolith vs microservicesMonolith vs microservicesfunction call vs network callDistributed tracingDistributed tracingtraceparent links spans across servicesRate limit windowsRate limit windowsfixed window lets 2x burst at the edgeRetry, backoff and jitterRetry, backoff and jitterWait 2^n plus random, or retries stampedeHedged requestsHedged requestsSlow? Send a copy; take the first reply
This page on the Distributed Systems mind map · 88 pages in 10 branches · open it to see the whole map and test yourself in recall mode.