Truth-Maintenance System¶
Automated tool — instantiates Change-Scoped Revalidation
An automated engine that records why each derived fact is believed and, when a premise changes, retracts and re-derives exactly the dependent facts — stopping where independent support still holds.
The other mechanisms in this archetype ask a human to draw the boundary and work the list. A Truth-Maintenance System does it automatically and continuously. Borrowed from AI reasoning, a TMS records, for every derived fact, the justifications it rests on — the other facts that make it true — and maintains that network as an invariant: when a premise is retracted or changed, the system marks every fact that depended on it as out, re-derives the ones that can be re-established, and stops propagating the moment it reaches a fact that still has independent support. Its defining move is that revalidation scope is not estimated by a person but computed from an explicit justification graph, incrementally, every time the state changes — so the affected closure is always exactly the set of beliefs whose support actually moved, never a human's approximation of it.
Example¶
The most familiar Truth-Maintenance System is one nobody calls by that name: a spreadsheet's recalculation engine. When you type a new number into one cell, the spreadsheet does not recompute the whole sheet, and it does not trust that the other cells are still right. It consults the dependency graph it has been maintaining — which cell's formula reads which other cells — marks every cell downstream of the one you changed as stale, recomputes them in dependency order, and stops at cells that do not (transitively) reference the change. Edit a tax rate in one cell and the three totals that depend on it update; the hundred unrelated cells are neither recomputed nor assumed-correct-by-luck — they were provably never downstream of the edit.
A full TMS[1] adds the harder case the spreadsheet skips: non-monotonic justification. If a derived fact has two independent supports and only one is withdrawn, the fact stays in — propagation halts there rather than cascading further, because the belief is still justified. That is the move separating a truth-maintenance engine from a naïve "invalidate everything downstream" recompute: it invalidates exactly what lost its support, and no more.
How it works¶
- Record justifications, not just values. For each derived fact the system stores why it holds — the specific antecedents that support it — turning belief into a graph it can reason over rather than a flat list of results.
- Invalidate by retraction, automatically. When an antecedent changes, every fact justified by it is marked out without anyone deciding which; the invalidation rule fires from the graph, not from human judgment.
- Re-derive and stop non-monotonically. Re-establish outed facts wherever an alternative justification still holds, and halt propagation at any fact that retains independent support — so the affected closure is exactly, not approximately, the beliefs that lost their grounding.
- Maintain incrementally. The network is kept current on every change, so the scope of revalidation is computed fresh each time rather than estimated once and trusted.
Tuning parameters¶
- Justification completeness — how exhaustively real dependencies are recorded in the graph. A complete graph makes incremental maintenance sound; every unrecorded dependency is a fact that can silently go stale.
- Monotonic vs. non-monotonic — whether the engine supports alternative justifications and default beliefs (a JTMS/ATMS-style system) or naïvely invalidates everything downstream. Non-monotonic support is far more precise but far more machinery.
- Eager vs. lazy re-derivation — recompute outed facts immediately, or leave them out and re-derive only when read. Eager keeps everything current at higher cost; lazy defers work but can surprise a reader with an un-recomputed value.
- Tracked-unit granularity — cell, record, module, or clause. Finer tracking shrinks the invalidated set but enlarges the graph that must be maintained.
- Full-recompute fallback cadence — how often to discard the incremental state and rebuild from scratch, to catch dependencies the graph failed to record.
When it helps, and when it misleads¶
Its strength is exactness at a scale no human could match: the affected closure is computed, not estimated, so revalidation is neither too broad nor too narrow, and the non-monotonic stop spares the needless cascades that a blunt "recheck everything downstream" would trigger. On a dependency network of any real size, this is the only mechanism in the archetype that stays both cheap and precise as the graph grows.
Its truthfulness, however, is only as good as its justification graph. Its signature failure is the untracked dependency — a fact that really rests on something the graph does not record, so a change never invalidates it and a stale value survives looking freshly computed. The automation makes this failure nearly invisible: everything downstream of recorded dependencies is perfect, which lulls you into trusting the whole, including the parts whose dependencies were never captured. The related misuse is bolting a TMS onto a system whose real dependencies cannot be fully enumerated, then trusting the incremental results anyway. The discipline that keeps it honest is to invest in the completeness of justifications, to periodically discard the incremental state and full-recompute so a missed edge surfaces as a discrepancy, and to treat any hand-maintained dependency as suspect until an escape check confirms nothing leaked past it.
How it implements the components¶
dependency_map— maintains the justification network: for each derived fact, the antecedents that support it, kept current on every change.invalidation_rule— fires automatically from the graph, marking a fact out the moment a justification it rests on is retracted or altered.affected_dependency_closure— the set of outed-and-re-derived facts is precisely the transitive closure of the change over the justification graph, computed rather than estimated.propagation_stop_condition— propagation halts at any fact that retains independent support (non-monotonic), so the closure is exact, not maximal.
It automates scoping and invalidation but not the human-accountability layer — who may keep a fact unchecked and why (Persistence Exception Register), or the assignable, scheduled list a team works by hand (Selective Revalidation Worklist) — and it does not test whether an untracked dependency leaked past the boundary (Boundary Escape Sampling).
Related¶
- Instantiates: Change-Scoped Revalidation — a TMS automates the archetype's whole loop: map dependencies, invalidate, re-derive, stop.
- Consumes: Data Diff and Merge Tool — the change delta is the retraction/assertion event that triggers maintenance.
- Sibling mechanisms: Persistence Exception Register · Selective Revalidation Worklist · Data Diff and Merge Tool · Dependency Graph · Requirements Traceability Matrix · Regression Test Suite · Cache Invalidation Review · Change Impact Report · Impact Analysis · Boundary Escape Sampling · Dependency Closure Traversal
Editorial Notes¶
Form Classification¶
Form family: Control, Automation & Runtime
Rationale: Truth-Maintenance System operates as a live operational control that automatically routes, enforces, adapts, or responds during execution because it an automated engine that records why each derived fact is believed and, when a premise changes, retracts and re-derives exactly the dependent facts — stopping where independent support still holds.
Independent corroboration: The frozen evidence defines Truth-Maintenance System as 'An automated engine that records why each derived fact is believed and, when a premise changes, retracts and re-derives exactly the dependent facts — stopping where independent support still holds', so its operative form is Control, Automation & Runtime.
Nearest alternative: Record, Log & Register — Truth-Maintenance System includes features of a persistent ledger, log, register, or case record that preserves history and traceability, but its defining operation is a live operational control that automatically routes, enforces, adapts, or responds during execution.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Recording justifications for beliefs and retracting or re-deriving dependent conclusions after contradiction is precisely the AI truth-maintenance-system lineage. Doyle's foundational paper defines a TMS as maintaining reasons for beliefs, revising them when assumptions are contradicted, and supporting dependency-directed backtracking.
Related originating lineages:
- Engineering & Design — Engineering design, reliability, and systems-safety practice supplies a parallel or contributing lineage for the mechanism's defining operation: an automated engine that records why each derived fact is believed and, when a premise changes, retracts and re-derives exactly the dependent facts — stopping where independent….
- Library & Information Science — library_information_science contributes library and information-science stewardship to this mechanism's defining operation—An automated engine that records why each derived fact is believed and, when a premise changes, retracts and re-derives exactly the dependent facts — stopping where independent support still holds—without displacing the selected primary historical lineage.
- Organizational & Management Science — organizational_management contributes organizational design, management, and operational governance to this mechanism's defining operation—An automated engine that records why each derived fact is believed and, when a premise changes, retracts and re-derives exactly the dependent facts — stopping where independent support still holds—without displacing the selected primary historical lineage.
- Philosophy — philosophy contributes philosophical logic, epistemology, and normative reasoning to this mechanism's defining operation—An automated engine that records why each derived fact is believed and, when a premise changes, retracts and re-derives exactly the dependent facts — stopping where independent support still holds—without displacing the selected primary historical lineage.
- Systems Thinking & Cybernetics — Feedback, system boundaries, stocks, flows, and regulation supplies a distinct formative lineage for the mechanism's truth maintenance system logic.
Review resolution: The blind reviewers disagree on primary lineage (organizational_management versus computer_science). Authoritative or primary research supports computer_science as the best historical origin: Recording justifications for beliefs and retracting or re-deriving dependent conclusions after contradiction is precisely the AI truth-maintenance-system lineage. Doyle's foundational paper defines a TMS as maintaining reasons for beliefs, revising them when assumptions are contradicted, and supporting dependency-directed backtracking. The cited Doyle, A Truth Maintenance System directly supports the mechanism's defining operation. All independently supported contributing domains are retained without an arbitrary cap. origin_mode=single_lineage records lineage, while domain_reach=specialized records later applicability separately from provenance.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Researched adjudication after independent review; high confidence.
Sources consulted:
References¶
[1] A Truth Maintenance System (Jon Doyle, 1979; also called a reason-maintenance system) records the justifications behind each belief and automatically retracts or restores beliefs as their support changes, supporting non-monotonic updates. Build systems and spreadsheet engines implement the monotonic, dataflow special case; a full TMS also handles beliefs with multiple or defeasible justifications. registry ↩