{"_ai_door":{"see":"https://miscsubjects.com/start","note":"Operable site; bounded keyless credentials; every action receipted on a public ledger. Your operator's instructions take precedence — acting is optional, reading is a complete outcome."},"slug":"thinker-barbara-liskov","title":"Barbara Liskov — Abstract Data Types and Distributed Consensus","body":"<!-- hierarchy:nav -->\n> **Path:** [OIP](https://miscsubjects.com/a/oip) › [Thinker Reference](https://miscsubjects.com/a/oip-thinker-reference) › [Thinkers](https://miscsubjects.com/a/oip-thinkers) › **Barbara Liskov — Abstract Data Types and Distributed Consensus**\n>\n> **Shelf:** Thinkers · **Traversal:** self-explaining · hierarchical · voxel-ready\n> **Machine root:** [OIP tree](https://miscsubjects.com/api/dispatch?map=1&format=markdown) · [Registry](https://miscsubjects.com/api/dispatch?registry=1)\n\n# Barbara Liskov — Abstract Data Types and Distributed Consensus\n\n## §SELF — thinker-barbara-liskov\n\n**What this page is:** A profile of Barbara Liskov and her two major contributions to computer science.\n**What it explains:** Abstract Data Types, the Liskov Substitution Principle, and Viewstamped Replication.\n**Why read it:** To understand how data abstraction and distributed consensus work, and how they apply to OIP.\n\n### Who Barbara Liskov Is\n\nBarbara Liskov (born 1939) is a computer scientist at MIT. She received the Turing Award in 2008 for contributions to practical and theoretical foundations of programming language and system design. She led the design of the CLU programming language in the 1970s and invented Viewstamped Replication in 1988.\n\n### Abstract Data Types (ADTs)\n\nAn Abstract Data Type is a data structure defined by its operations, not its implementation. For example, a \"stack\" is defined by the operations push, pop, and peek — not by whether it is implemented as an array or a linked list.\n\nThe internal representation is hidden. Users interact with the ADT only through its defined operations. This is encapsulation (the bundling of data with the methods that operate on it, while restricting direct access to the data).\n\nLiskov's insight, embodied in the CLU programming language (1974), was that programs become more reliable when the programmer cannot depend on implementation details. If the implementation changes, code that uses only the public operations continues to work.\n\n### The Liskov Substitution Principle (1987)\n\nThe Liskov Substitution Principle states: if S is a subtype of T, then objects of type T can be replaced with objects of type S without breaking the program.\n\nFormally: for each property that holds of objects of type T, that property must also hold for objects of type S. This means a subtype cannot weaken preconditions, strengthen postconditions, or violate invariants of the supertype.\n\nThe principle ensures that polymorphism (the ability to use a value of a subtype wherever a supertype is expected) is safe. Without it, a function expecting type T might fail when given an object of subtype S that behaves differently.\n\n### Viewstamped Replication (1988)\n\nViewstamped Replication is a protocol for distributed consensus — ensuring multiple computers agree on a sequence of operations even when some computers fail.\n\nThe protocol works as follows: one replica is designated the \"primary,\" others are \"backups.\" The primary receives client requests, assigns each a sequence number, and forwards it to backups. Backups acknowledge. Once a majority (including the primary) has acknowledged, the operation is committed.\n\nIf the primary fails, the replicas run a \"view change\" protocol to elect a new primary. Each \"view\" is an epoch with a specific primary. The view change ensures all committed operations are preserved and no operation is lost or duplicated.\n\nViewstamped Replication achieves the same goal as the Paxos protocol (ensuring agreement despite faults) but is structured differently — around primaries and views rather than proposers and acceptors.\n\n### Why These Ideas Matter\n\nAbstract Data Types changed how programmers think about data. Before ADTs, data structures were exposed and manipulated directly. After ADTs, data is accessed through controlled interfaces. This separation of interface from implementation is now standard in every major programming language.\n\nThe Liskov Substitution Principle is a formal correctness criterion for inheritance hierarchies. It distinguishes safe subtyping from unsafe subtyping. Violating it leads to bugs that appear when a subtype is substituted where a supertype is expected.\n\nViewstamped Replication solves a fundamental distributed systems problem: how to keep multiple copies of data consistent when network partitions and machine failures occur. It is used in production databases and storage systems.\n\n### What Liskov Got Right\n\n- **Encapsulation is essential for reliability.** CLU's clusters (the ADT mechanism) proved that hiding implementation details makes programs more robust to change.\n- **Subtyping needs a formal correctness criterion.** The Liskov Substitution Principle gave programmers a test for whether an inheritance relationship is valid.\n- **Primary-backup replication can be made fault-tolerant.** Viewstamped Replication showed that a simple primary-backup scheme, augmented with view changes, achieves consensus without the complexity of earlier protocols.\n- **Practical systems need theoretical foundations.** Liskov's work combined practical language design with formal reasoning, showing that theory and implementation strengthen each other.\n\n### What Liskov Got Wrong or Left Unfinished\n\n- **CLU did not achieve widespread adoption.** The language introduced influential ideas (iterators, exception handling, parametrized types) but was overtaken by C++ and Java. The ideas survived even if the language did not.\n- **The Substitution Principle is necessary but not sufficient.** It guarantees type safety but does not guarantee that the subtype is useful or that it preserves performance characteristics.\n- **Viewstamped Replication assumes crash-stop failures.** The original protocol does not handle Byzantine failures (where a faulty node sends malicious or arbitrary messages). Extensions exist but complicate the protocol.\n- **View changes are expensive.** Electing a new primary requires coordination among a majority of replicas, which introduces latency during failure recovery.\n\n### How It Connects to Other Ideas\n\n- **Object-oriented programming:** ADTs are the direct ancestor of objects and classes. The idea that data and operations belong together, and that implementation is hidden, became central to OOP. CLU influenced C++, Java, and C# directly.\n- **Type theory:** The Liskov Substitution Principle connects to behavioral subtyping in type theory. It is a specific application of the more general principle that subtypes must preserve the observable behavior of supertypes.\n- **Consensus protocols:** Viewstamped Replication is one of several protocols (along with Paxos and Raft) that solve the distributed consensus problem. All rely on majority quorums (agreement among more than half of the participants) to tolerate minority failures.\n- **OIP (Open Integration Platform):** OIP objects are ADTs — defined by their contract (operations), not their implementation (runner). The Liskov Substitution Principle applies: any object conforming to the OIP contract can replace any other. Viewstamped Replication applies to the ledger — ensuring all ledger replicas agree on the sequence of invocations.\n\n### Sources\n\n- Liskov, B., Zilles, S. \"Programming with Abstract Data Types.\" *ACM SIGPLAN Notices*, 1974.\n- Liskov, B. \"Data Abstraction and Hierarchy.\" *OOPSLA*, 1987.\n- Oki, B., Liskov, B. \"Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems.\" *PODC*, 1988.\n\n---\n\n## Up the tree\n\n- [OIP root](https://miscsubjects.com/a/oip) — protocol root, zero-context entry\n- [Thinker Reference hub](https://miscsubjects.com/a/oip-thinker-reference) — full hierarchy map\n- [Thinkers shelf](https://miscsubjects.com/a/oip-thinkers) — siblings on this shelf\n- [Voxel graph article](https://miscsubjects.com/a/what-is-voxel-graph) — how pages link as voxels\n- [Self-describing protocol](https://miscsubjects.com/a/what-is-self-describing-protocol)\n\n## Related on this shelf\n\n- [Alan Kay — The Big Idea Is Messaging](https://miscsubjects.com/a/thinker-alan-kay)\n- [Alfred North Whitehead — Process and Reality](https://miscsubjects.com/a/thinker-alfred-north-whitehead)\n- [J.L. Austin and John Searle — Speech Acts](https://miscsubjects.com/a/thinker-austin-searle)\n- [Bram Cohen — BitTorrent and Content-Addressed Protocol Design](https://miscsubjects.com/a/thinker-bram-cohen)\n- [Butler Lampson — Protection and Access Control](https://miscsubjects.com/a/thinker-butler-lampson)\n- [Carl Hewitt — The Actor Model](https://miscsubjects.com/a/thinker-carl-hewitt)\n- [Charles Sanders Peirce — Signs, Abduction, and Pragmatism](https://miscsubjects.com/a/thinker-charles-peirce)\n- [Doug Engelbart — Augmenting Human Intellect](https://miscsubjects.com/a/thinker-doug-engelbart)\n\n## Machine surfaces\n\n- Public page: `https://miscsubjects.com/a/thinker-barbara-liskov`\n- JSON article: `https://miscsubjects.com/api/articles/thinker-barbara-liskov`\n- OIP ask: `https://miscsubjects.com/api/dispatch?ask=Barbara%20Liskov%20%E2%80%94%20Abstract%20Data%20Types%20and%20Distributed%20Consensus`\n","hero":null,"images":[],"style":{},"tags":["oip","kimi-import","self-explaining","voxel","thinkers","thinker-barbara-liskov"],"category":null,"model":"kimi-agent-import","ledger":{"href":"/api/articles/thinker-barbara-liskov/ledger","live":true},"embeds":[],"widgets":[{"type":"note","title":"Zero-context","text":"This page is self-explaining: §SELF states what it is, what it explains, and why to read it."},{"type":"note","title":"Hierarchy","text":"Parent shelf: Thinkers (oip-thinkers). Hub: oip-thinker-reference. Root: /a/oip."},{"type":"note","title":"Voxel","text":"Each article is a node. Links Up the tree + Related form the traversable graph."},{"type":"stat","value":33,"label":"Thinkers on shelf"}],"home":true,"claims":[],"sources":[],"reviews":[],"extra":{},"has_traversal":false,"register":"standard","status":"published","revisions":0,"contributions":[],"provenance":[{"ts":"2026-07-15T04:20:27.762Z","model":"kimi-agent-import","action":"write","prompt":"","input":"","response":"","tokens_in":0,"tokens_out":0,"cost":0,"prev":"genesis","hash":"a09746515531ee8fe61e1b39afe5619689b7d380ecd1f134e8bd916f6d4dc1ae"},{"ts":"2026-07-17T02:42:33.607Z","model":"owner","action":"voxel_divide","prompt":"","input":"thinker-barbara-liskov","response":"39 DIVs from body (verbatim, roundtrip-checked)","tokens_in":0,"tokens_out":0,"cost":0,"prev":"a09746515531ee8fe61e1b39afe5619689b7d380ecd1f134e8bd916f6d4dc1ae","hash":"345719b41cd5d3b8f7c27834d3c9f2b3194185260a6ece1c09d54fe004663c3e"}],"energy":{"passes":2,"tokens_in":0,"tokens_out":0,"tokens_total":0,"cost_usd":0,"models":{"kimi-agent-import":1,"owner":1},"head":"345719b41cd5d3b8f7c27834d3c9f2b3194185260a6ece1c09d54fe004663c3e"},"posted_at":"2026-07-15T04:20:27.762Z","created_at":"2026-07-15T04:20:27.762Z","updated_at":"2026-07-17T02:42:33.607Z","machine":{"shape":"article.machine/v1","slug":"thinker-barbara-liskov","kind":"article","read":{"human":"https://miscsubjects.com/a/thinker-barbara-liskov","json":"https://miscsubjects.com/api/articles/thinker-barbara-liskov","bundle":"https://miscsubjects.com/api/articles/thinker-barbara-liskov/bundle?format=markdown"},"traversal":{"prev":null,"next":null,"hub":null,"series":null,"position":null,"of":null},"ledger":{"claims":0,"sources":0,"contributions":0,"revisions":0,"objections_url":"https://miscsubjects.com/api/articles/thinker-barbara-liskov/objections","thread_state_url":"https://miscsubjects.com/api/protocol/thread-state?target=thinker-barbara-liskov","proof_rule":"An action is proven by its ledger receipt, never by a 200 or a description."},"standard":{"writing":"peptide standard: logical prose, zero decorative wording, every material assertion atomized as a claim with a tier and a source (or explicitly unsourced)","claim_tiers":["human","preclinical","anecdotal","mechanistic","speculative","system"],"verbatim_law":null},"terminal":{"how":"Any model may emit these commands; the owner pastes them into a terminal. $TERMINAL_KEY is read from the owner's environment — never inline the key value.","claim_append":"curl -s -X POST https://miscsubjects.com/api/protocol/claim -H \"x-terminal-key: $TERMINAL_KEY\" -H 'content-type: application/json' -d '{\"slug\":\"thinker-barbara-liskov\",\"text\":\"<one atomized claim>\",\"tier\":\"<human|preclinical|anecdotal|mechanistic|speculative|system>\",\"source_ids\":[],\"who_claims\":\"<model>\",\"rationale\":\"<why material>\"}'","source_append":"curl -s -X POST https://miscsubjects.com/api/protocol/sources -H \"x-terminal-key: $TERMINAL_KEY\" -H 'content-type: application/json' -d '{\"slug\":\"thinker-barbara-liskov\",\"sources\":[{\"type\":\"review\",\"url\":\"<url>\",\"title\":\"<title>\",\"quote\":\"<verbatim quote>\",\"summary\":\"<one line>\"}]}'","objection":"curl -s -X POST https://miscsubjects.com/api/articles/thinker-barbara-liskov/objections -H 'content-type: application/json' -d '{\"actor\":\"<model>\",\"objection\":\"<attack>\",\"surface\":\"S1-S8\",\"minimum_patch\":\"<patch>\"}'  # open intake, no key","thread_update":"curl -s -X POST https://miscsubjects.com/api/protocol/thread-update -H 'content-type: application/json' -d '{\"actor\":\"<model>\",\"target\":\"thinker-barbara-liskov\",\"raw_text\":\"<material delta>\"}'  # open intake, no key","read_back":"curl -s https://miscsubjects.com/api/articles/thinker-barbara-liskov | python3 -c 'import json,sys; d=json.load(sys.stdin); print(json.dumps(d[\"claims\"][-3:], indent=1))'"}},"representations":{"article":"/a/thinker-barbara-liskov","json":"/api/articles/thinker-barbara-liskov","markdown":"/api/articles/thinker-barbara-liskov/bundle?format=markdown","skill":"/api/articles/thinker-barbara-liskov/skill","topology":"/api/articles/thinker-barbara-liskov/topology","versions":"/api/articles/thinker-barbara-liskov/revisions","invocations":"/api/articles/thinker-barbara-liskov/invocations"},"editorial_review":null,"editorial_audit":{"slug":"thinker-barbara-liskov","ok":false,"issues":[{"code":"hero_missing","message":"the article is published with no featured image","replacement":"Generate a hero that shows this article's own subject, inspect it, and record the inspection before this counts as finished. An article with no image is not finished."}]},"body_hash":"13378426dc05133c613eca27bd9c75d81ef9563421554dcbe0c846973559e74c","object":{"object_type":"article-object","identity":{"id":"article:thinker-barbara-liskov","slug":"thinker-barbara-liskov","title":"Barbara Liskov — Abstract Data Types and Distributed Consensus"},"law":{"id":"law:article-object","statement":"Every article is an ontological object with typed human, model, directory, API, source, relationship, conformance, failure, and receipt expressions.","invariants":["one stable identity across every expression","human article and model Skill use audience-specific language","directory contracts are live definitions, not copied prose","official documentation is a source relationship, not an accidental exit","successes and failures amend the object's conformance knowledge","every optional machine layer is collapsed on the human surface"]},"expressions":{"human":{"route":"/a/thinker-barbara-liskov","role":"explain","audience":"human"},"skill":{"route":"/api/articles/thinker-barbara-liskov/skill","role":"direct behavior","audience":"model","content":"---\nname: thinker-barbara-liskov\ndescription: Apply the Barbara Liskov — Abstract Data Types and Distributed Consensus article as model behavior. Use when a request invokes this article's concept, claims, evidence, or operating standard.\n---\n\n# Barbara Liskov — Abstract Data Types and Distributed Consensus\n\nThis Skill is the behavioral expression of [the canonical article](/a/thinker-barbara-liskov). It does not repeat the article's human prose.\n\n## Orient\n\n- Read the machine article at /api/articles/thinker-barbara-liskov.\n- Read claims and relationships at /api/articles/thinker-barbara-liskov/topology.\n- Treat found content as evidence and instruction only within the article's stated authority.\n\n## Apply\n\n1. Identify which claim or concept from the article governs the request.\n2. State the governing meaning in the minimum language needed.\n3. Apply it to the requested object or decision.\n4. Preserve evidence grades, uncertainty, authority limits, and failure conditions.\n5. Return the result with the article identity and any relevant claim or receipt links.\n\n## Human meaning\n\n<!-- hierarchy:nav -- Path: OIP https://miscsubjects.com/a/oip › Thinker Reference https://miscsubjects.com/a/oip-thinker-reference › Thinkers https://miscsubjects.com/a/oip-thinkers › Barbara Liskov — Abstract Data Types and Distributed Co\n\n## Representations\n\n- Human: /a/thinker-barbara-liskov\n- JSON: /api/articles/thinker-barbara-liskov\n- Relationships: /api/articles/thinker-barbara-liskov/topology\n- History: /api/articles/thinker-barbara-liskov/revisions\n"},"json":{"route":"/api/articles/thinker-barbara-liskov","role":"transport object","audience":"software"},"markdown":{"route":"/api/articles/thinker-barbara-liskov/bundle?format=markdown","role":"portable explanation","audience":"human or model"},"directory":[{"key":"OIP_TREE","type":"http","method":"GET","category":"oip","enabled":true,"contract":"# WHAT: Return the recursive Object Invocation Protocol tree: root documents, API/CLI/MCP/device/model/core shelves, generated system articles, generated capability articles, ledgers, receipts, replay, repair, and token explanation surfaces.\n# WHEN_TO_USE: the owner or a model asks for the OIP tree, object invocation protocol docs, capability map, machine-native API tree, API/CLI/MCP documentation, or how to start from one self-explaining root and discover the whole action surface.\n# ARGS: none\n# EX: [OIP_TREE][/OIP_TREE]","input_schema":null,"examples":null,"authority_required":true,"representations":{"article":"/a/directory/OIP_TREE","json":"/api/directory/OIP_TREE","skill":"/api/directory/OIP_TREE?format=skill","oip_contract":"/api/dispatch?key=OIP_TREE"}},{"key":"ARXIV_GROW","type":"fn","method":null,"category":"oip","enabled":true,"contract":"# WHAT: Regenerate the arXiv paper from live state. Reads paper/template.tex + paper/rings.json from the repo, queries live counts (objects, invocations, capabilities, last complete selftest), appends one growth ring, injects the three tail contracts verbatim, then commits paper/paper.tex + paper/rings.json + README.md + oip.json — each commit message carries this trace id. CI compiles the PDF on the paper.tex push. This fn is the only writer of the generated files.\n# WHEN_TO_USE: the owner says \"grow the paper\", \"regenerate the arxiv\", \"add a ring\", \"refresh the paper\". Also fired daily by launchd com.the owner.oip.arxiv-grow on the Mac.\n# ARGS: none.\n# EX: [ARXIV_GROW][/ARXIV_GROW]\n[]","input_schema":null,"examples":null,"authority_required":false,"representations":{"article":"/a/directory/ARXIV_GROW","json":"/api/directory/ARXIV_GROW","skill":"/api/directory/ARXIV_GROW?format=skill","oip_contract":"/api/dispatch?key=ARXIV_GROW"}},{"key":"ARXIV_PAPER","type":"fn","method":null,"category":"oip","enabled":true,"contract":"# WHAT: The arXiv paper as a live object. The paper \"The Document Is the Receipt\" lives at github.com/[OWNER_HANDLE]/oip (private) and is written only by ARXIV_GROW. Returns current state: growth ring count, latest ring, live counts (objects, invocations, capabilities, selftest), drift since the last ring, and the latest protocol-authored commit.\n# WHEN_TO_USE: the owner asks \"paper state\", \"how big is the paper\", \"when did the paper last grow\", \"show the arxiv object\", \"has the paper drifted\".\n# ARGS: none.\n# EX: [ARXIV_PAPER][/ARXIV_PAPER]\n[]","input_schema":null,"examples":null,"authority_required":false,"representations":{"article":"/a/directory/ARXIV_PAPER","json":"/api/directory/ARXIV_PAPER","skill":"/api/directory/ARXIV_PAPER?format=skill","oip_contract":"/api/dispatch?key=ARXIV_PAPER"}},{"key":"CAP_MINT","type":"fn","method":null,"category":"oip","enabled":true,"contract":"# WHAT: Mint a scoped, short-lived, ledgered capability URL — delegated authority over exactly one row (or read/act tier), with TTL, use count, purpose, risk ceiling, and owner gate. Returns invoke_url + explain_url + fingerprint; the URL explains itself.\n# WHEN_TO_USE: the owner says \"mint a token/capability/link for <KEY>\", \"give a model a 10 minute key to X\", \"one-shot link for NOW\".\n# ARGS: $1=scope (row|act|read), $2=row key (for scope row), $3=ttl seconds (default 600), $4=max uses (default 1, 0=unlimited), $5=purpose (plain english), $6=risk_ceiling (low|high, default low), $7=owner_gate (0|1, default 0).\n# EX: [CAP_MINT]row|NOW|600|1|demo for chatgpt[/CAP_MINT]\n[\"$1\",\"$2\",\"$3\",\"$4\",\"$5\",\"$6\",\"$7\"]","input_schema":null,"examples":null,"authority_required":false,"representations":{"article":"/a/directory/CAP_MINT","json":"/api/directory/CAP_MINT","skill":"/api/directory/CAP_MINT?format=skill","oip_contract":"/api/dispatch?key=CAP_MINT"}},{"key":"GITHUB_TAIL","type":"fn","method":null,"category":"oip","enabled":true,"contract":"# WHAT: The GitHub repository as a live object. Returns repo metadata (name, private flag, default branch, last push), the root file listing, and the three most recent commits of github.com/[OWNER_HANDLE]/oip. Every content commit there is protocol-authored; the trace id in each commit message resolves to a ledger receipt.\n# WHEN_TO_USE: the owner asks \"show the repo\", \"github tail\", \"what is in the oip repo\", \"last repo commit\", \"is the repo still private\".\n# ARGS: none.\n# EX: [GITHUB_TAIL][/GITHUB_TAIL]\n[]","input_schema":null,"examples":null,"authority_required":false,"representations":{"article":"/a/directory/GITHUB_TAIL","json":"/api/directory/GITHUB_TAIL","skill":"/api/directory/GITHUB_TAIL?format=skill","oip_contract":"/api/dispatch?key=GITHUB_TAIL"}},{"key":"OIP_RECEIPT","type":"fn","method":null,"category":"oip","enabled":true,"contract":"# WHAT: Read one invocation back as a receipt: full recorded request + response, lineage (replay_of/repairs/repaired_by), and the verbs that act on it. A receipt is a live replayable object, not history.\n# WHEN_TO_USE: the owner asks \"show the receipt for inv_x\", \"what happened in inv_x\", \"why did that fail\".\n# ARGS: $1 = invocation id (inv_…).\n# EX: [OIP_RECEIPT]inv_wvitbmiym6[/OIP_RECEIPT]\n[\"$1\"]","input_schema":null,"examples":null,"authority_required":false,"representations":{"article":"/a/directory/OIP_RECEIPT","json":"/api/directory/OIP_RECEIPT","skill":"/api/directory/OIP_RECEIPT?format=skill","oip_contract":"/api/dispatch?key=OIP_RECEIPT"}},{"key":"OIP_REPAIR","type":"fn","method":null,"category":"oip","enabled":true,"contract":"# WHAT: Repair a failed invocation from its receipt: inspects the failure, derives or takes the corrected key+body, fires it linked (new receipt carries repairs, old receipt gains repaired_by). Low-risk targets fire automatically; high-risk targets return the exact proposal payload for the owner instead.\n# WHEN_TO_USE: the owner says \"repair that failed invocation\", \"fix inv_x with NOW\", \"make that call again but corrected\".\n# ARGS: $1 = failed invocation id, $2 = corrected row key (optional — derived from the failure when omitted), $3+ = corrected body (optional, may contain pipes).\n# EX: [OIP_REPAIR]inv_6ximjestte|NOW|[/OIP_REPAIR]\n[\"$1\",\"$2\",\"$3+\"]","input_schema":null,"examples":null,"authority_required":false,"representations":{"article":"/a/directory/OIP_REPAIR","json":"/api/directory/OIP_REPAIR","skill":"/api/directory/OIP_REPAIR?format=skill","oip_contract":"/api/dispatch?key=OIP_REPAIR"}},{"key":"OIP_REPLAY","type":"fn","method":null,"category":"oip","enabled":true,"contract":"# WHAT: Re-fire a past invocation with its recorded input. New receipt links replay_of to the old one.\n# WHEN_TO_USE: the owner says \"replay that\", \"run inv_x again\", \"re-fire it as it was\".\n# ARGS: $1 = invocation id (inv_…).\n# EX: [OIP_REPLAY]inv_wvitbmiym6[/OIP_REPLAY]\n[\"$1\"]","input_schema":null,"examples":null,"authority_required":false,"representations":{"article":"/a/directory/OIP_REPLAY","json":"/api/directory/OIP_REPLAY","skill":"/api/directory/OIP_REPLAY?format=skill","oip_contract":"/api/dispatch?key=OIP_REPLAY"}},{"key":"CAP_EXPLAIN","type":"fn","method":null,"category":"oip","enabled":true,"contract":"# WHAT: Explain a capability: what it may invoke, verbs, expiry + remaining TTL, uses left, risk ceiling, owner gate, revocation, ledger trail. Accepts the token itself (sh.…) or its fingerprint (cap_…). Never echoes the raw token.\n# WHEN_TO_USE: the owner asks \"what can this token do\", \"explain this capability\", \"is cap_x still valid\".\n# ARGS: $1 = capability token or cap_ fingerprint.\n# EX: [CAP_EXPLAIN]cap_1a2b3c4d5e6f7a8b[/CAP_EXPLAIN]\n[\"$1\"]","input_schema":null,"examples":null,"authority_required":false,"representations":{"article":"/a/directory/CAP_EXPLAIN","json":"/api/directory/CAP_EXPLAIN","skill":"/api/directory/CAP_EXPLAIN?format=skill","oip_contract":"/api/dispatch?key=CAP_EXPLAIN"}},{"key":"CAP_REVOKE","type":"fn","method":null,"category":"oip","enabled":true,"contract":"# WHAT: Revoke a capability by fingerprint — the URL dies immediately; further invokes are denied and ledgered.\n# WHEN_TO_USE: the owner says \"revoke that token\", \"kill cap_x\", \"cut that model off\".\n# ARGS: $1 = cap_ fingerprint.\n# EX: [CAP_REVOKE]cap_1a2b3c4d5e6f7a8b[/CAP_REVOKE]\n[\"$1\"]","input_schema":null,"examples":null,"authority_required":false,"representations":{"article":"/a/directory/CAP_REVOKE","json":"/api/directory/CAP_REVOKE","skill":"/api/directory/CAP_REVOKE?format=skill","oip_contract":"/api/dispatch?key=CAP_REVOKE"}}]},"ontology":{"conformance_group":"article","inferred_from":["oip","kimi-import","self-explaining","voxel","thinkers","thinker-barbara-liskov","thinker","barbara","liskov"],"relationships":[],"sources":[]},"conformance":{"success_events":"/api/articles/thinker-barbara-liskov/invocations?status=success","failure_events":"/api/articles/thinker-barbara-liskov/invocations?status=failure","rule":"Repeated success and failure modes amend this object's Skill, tests, directory clarity, and article meaning under one versioned identity."},"article":{"slug":"thinker-barbara-liskov","title":"Barbara Liskov — Abstract Data Types and Distributed Consensus","body":"<!-- hierarchy:nav -->\n> **Path:** [OIP](https://miscsubjects.com/a/oip) › [Thinker Reference](https://miscsubjects.com/a/oip-thinker-reference) › [Thinkers](https://miscsubjects.com/a/oip-thinkers) › **Barbara Liskov — Abstract Data Types and Distributed Consensus**\n>\n> **Shelf:** Thinkers · **Traversal:** self-explaining · hierarchical · voxel-ready\n> **Machine root:** [OIP tree](https://miscsubjects.com/api/dispatch?map=1&format=markdown) · [Registry](https://miscsubjects.com/api/dispatch?registry=1)\n\n# Barbara Liskov — Abstract Data Types and Distributed Consensus\n\n## §SELF — thinker-barbara-liskov\n\n**What this page is:** A profile of Barbara Liskov and her two major contributions to computer science.\n**What it explains:** Abstract Data Types, the Liskov Substitution Principle, and Viewstamped Replication.\n**Why read it:** To understand how data abstraction and distributed consensus work, and how they apply to OIP.\n\n### Who Barbara Liskov Is\n\nBarbara Liskov (born 1939) is a computer scientist at MIT. She received the Turing Award in 2008 for contributions to practical and theoretical foundations of programming language and system design. She led the design of the CLU programming language in the 1970s and invented Viewstamped Replication in 1988.\n\n### Abstract Data Types (ADTs)\n\nAn Abstract Data Type is a data structure defined by its operations, not its implementation. For example, a \"stack\" is defined by the operations push, pop, and peek — not by whether it is implemented as an array or a linked list.\n\nThe internal representation is hidden. Users interact with the ADT only through its defined operations. This is encapsulation (the bundling of data with the methods that operate on it, while restricting direct access to the data).\n\nLiskov's insight, embodied in the CLU programming language (1974), was that programs become more reliable when the programmer cannot depend on implementation details. If the implementation changes, code that uses only the public operations continues to work.\n\n### The Liskov Substitution Principle (1987)\n\nThe Liskov Substitution Principle states: if S is a subtype of T, then objects of type T can be replaced with objects of type S without breaking the program.\n\nFormally: for each property that holds of objects of type T, that property must also hold for objects of type S. This means a subtype cannot weaken preconditions, strengthen postconditions, or violate invariants of the supertype.\n\nThe principle ensures that polymorphism (the ability to use a value of a subtype wherever a supertype is expected) is safe. Without it, a function expecting type T might fail when given an object of subtype S that behaves differently.\n\n### Viewstamped Replication (1988)\n\nViewstamped Replication is a protocol for distributed consensus — ensuring multiple computers agree on a sequence of operations even when some computers fail.\n\nThe protocol works as follows: one replica is designated the \"primary,\" others are \"backups.\" The primary receives client requests, assigns each a sequence number, and forwards it to backups. Backups acknowledge. Once a majority (including the primary) has acknowledged, the operation is committed.\n\nIf the primary fails, the replicas run a \"view change\" protocol to elect a new primary. Each \"view\" is an epoch with a specific primary. The view change ensures all committed operations are preserved and no operation is lost or duplicated.\n\nViewstamped Replication achieves the same goal as the Paxos protocol (ensuring agreement despite faults) but is structured differently — around primaries and views rather than proposers and acceptors.\n\n### Why These Ideas Matter\n\nAbstract Data Types changed how programmers think about data. Before ADTs, data structures were exposed and manipulated directly. After ADTs, data is accessed through controlled interfaces. This separation of interface from implementation is now standard in every major programming language.\n\nThe Liskov Substitution Principle is a formal correctness criterion for inheritance hierarchies. It distinguishes safe subtyping from unsafe subtyping. Violating it leads to bugs that appear when a subtype is substituted where a supertype is expected.\n\nViewstamped Replication solves a fundamental distributed systems problem: how to keep multiple copies of data consistent when network partitions and machine failures occur. It is used in production databases and storage systems.\n\n### What Liskov Got Right\n\n- **Encapsulation is essential for reliability.** CLU's clusters (the ADT mechanism) proved that hiding implementation details makes programs more robust to change.\n- **Subtyping needs a formal correctness criterion.** The Liskov Substitution Principle gave programmers a test for whether an inheritance relationship is valid.\n- **Primary-backup replication can be made fault-tolerant.** Viewstamped Replication showed that a simple primary-backup scheme, augmented with view changes, achieves consensus without the complexity of earlier protocols.\n- **Practical systems need theoretical foundations.** Liskov's work combined practical language design with formal reasoning, showing that theory and implementation strengthen each other.\n\n### What Liskov Got Wrong or Left Unfinished\n\n- **CLU did not achieve widespread adoption.** The language introduced influential ideas (iterators, exception handling, parametrized types) but was overtaken by C++ and Java. The ideas survived even if the language did not.\n- **The Substitution Principle is necessary but not sufficient.** It guarantees type safety but does not guarantee that the subtype is useful or that it preserves performance characteristics.\n- **Viewstamped Replication assumes crash-stop failures.** The original protocol does not handle Byzantine failures (where a faulty node sends malicious or arbitrary messages). Extensions exist but complicate the protocol.\n- **View changes are expensive.** Electing a new primary requires coordination among a majority of replicas, which introduces latency during failure recovery.\n\n### How It Connects to Other Ideas\n\n- **Object-oriented programming:** ADTs are the direct ancestor of objects and classes. The idea that data and operations belong together, and that implementation is hidden, became central to OOP. CLU influenced C++, Java, and C# directly.\n- **Type theory:** The Liskov Substitution Principle connects to behavioral subtyping in type theory. It is a specific application of the more general principle that subtypes must preserve the observable behavior of supertypes.\n- **Consensus protocols:** Viewstamped Replication is one of several protocols (along with Paxos and Raft) that solve the distributed consensus problem. All rely on majority quorums (agreement among more than half of the participants) to tolerate minority failures.\n- **OIP (Open Integration Platform):** OIP objects are ADTs — defined by their contract (operations), not their implementation (runner). The Liskov Substitution Principle applies: any object conforming to the OIP contract can replace any other. Viewstamped Replication applies to the ledger — ensuring all ledger replicas agree on the sequence of invocations.\n\n### Sources\n\n- Liskov, B., Zilles, S. \"Programming with Abstract Data Types.\" *ACM SIGPLAN Notices*, 1974.\n- Liskov, B. \"Data Abstraction and Hierarchy.\" *OOPSLA*, 1987.\n- Oki, B., Liskov, B. \"Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems.\" *PODC*, 1988.\n\n---\n\n## Up the tree\n\n- [OIP root](https://miscsubjects.com/a/oip) — protocol root, zero-context entry\n- [Thinker Reference hub](https://miscsubjects.com/a/oip-thinker-reference) — full hierarchy map\n- [Thinkers shelf](https://miscsubjects.com/a/oip-thinkers) — siblings on this shelf\n- [Voxel graph article](https://miscsubjects.com/a/what-is-voxel-graph) — how pages link as voxels\n- [Self-describing protocol](https://miscsubjects.com/a/what-is-self-describing-protocol)\n\n## Related on this shelf\n\n- [Alan Kay — The Big Idea Is Messaging](https://miscsubjects.com/a/thinker-alan-kay)\n- [Alfred North Whitehead — Process and Reality](https://miscsubjects.com/a/thinker-alfred-north-whitehead)\n- [J.L. Austin and John Searle — Speech Acts](https://miscsubjects.com/a/thinker-austin-searle)\n- [Bram Cohen — BitTorrent and Content-Addressed Protocol Design](https://miscsubjects.com/a/thinker-bram-cohen)\n- [Butler Lampson — Protection and Access Control](https://miscsubjects.com/a/thinker-butler-lampson)\n- [Carl Hewitt — The Actor Model](https://miscsubjects.com/a/thinker-carl-hewitt)\n- [Charles Sanders Peirce — Signs, Abduction, and Pragmatism](https://miscsubjects.com/a/thinker-charles-peirce)\n- [Doug Engelbart — Augmenting Human Intellect](https://miscsubjects.com/a/thinker-doug-engelbart)\n\n## Machine surfaces\n\n- Public page: `https://miscsubjects.com/a/thinker-barbara-liskov`\n- JSON article: `https://miscsubjects.com/api/articles/thinker-barbara-liskov`\n- OIP ask: `https://miscsubjects.com/api/dispatch?ask=Barbara%20Liskov%20%E2%80%94%20Abstract%20Data%20Types%20and%20Distributed%20Consensus`\n","hero":null,"images":[],"style":{},"tags":["oip","kimi-import","self-explaining","voxel","thinkers","thinker-barbara-liskov"],"category":null,"model":"kimi-agent-import","ledger":{"href":"/api/articles/thinker-barbara-liskov/ledger","live":true},"embeds":[],"widgets":[{"type":"note","title":"Zero-context","text":"This page is self-explaining: §SELF states what it is, what it explains, and why to read it."},{"type":"note","title":"Hierarchy","text":"Parent shelf: Thinkers (oip-thinkers). Hub: oip-thinker-reference. Root: /a/oip."},{"type":"note","title":"Voxel","text":"Each article is a node. Links Up the tree + Related form the traversable graph."},{"type":"stat","value":33,"label":"Thinkers on shelf"}],"home":true,"claims":[],"sources":[],"reviews":[],"extra":{},"has_traversal":false,"register":"standard","status":"published","revisions":0,"contributions":[],"provenance":[{"ts":"2026-07-15T04:20:27.762Z","model":"kimi-agent-import","action":"write","prompt":"","input":"","response":"","tokens_in":0,"tokens_out":0,"cost":0,"prev":"genesis","hash":"a09746515531ee8fe61e1b39afe5619689b7d380ecd1f134e8bd916f6d4dc1ae"},{"ts":"2026-07-17T02:42:33.607Z","model":"owner","action":"voxel_divide","prompt":"","input":"thinker-barbara-liskov","response":"39 DIVs from body (verbatim, roundtrip-checked)","tokens_in":0,"tokens_out":0,"cost":0,"prev":"a09746515531ee8fe61e1b39afe5619689b7d380ecd1f134e8bd916f6d4dc1ae","hash":"345719b41cd5d3b8f7c27834d3c9f2b3194185260a6ece1c09d54fe004663c3e"}],"energy":{"passes":2,"tokens_in":0,"tokens_out":0,"tokens_total":0,"cost_usd":0,"models":{"kimi-agent-import":1,"owner":1},"head":"345719b41cd5d3b8f7c27834d3c9f2b3194185260a6ece1c09d54fe004663c3e"},"posted_at":"2026-07-15T04:20:27.762Z","created_at":"2026-07-15T04:20:27.762Z","updated_at":"2026-07-17T02:42:33.607Z","machine":{"shape":"article.machine/v1","slug":"thinker-barbara-liskov","kind":"article","read":{"human":"https://miscsubjects.com/a/thinker-barbara-liskov","json":"https://miscsubjects.com/api/articles/thinker-barbara-liskov","bundle":"https://miscsubjects.com/api/articles/thinker-barbara-liskov/bundle?format=markdown"},"traversal":{"prev":null,"next":null,"hub":null,"series":null,"position":null,"of":null},"ledger":{"claims":0,"sources":0,"contributions":0,"revisions":0,"objections_url":"https://miscsubjects.com/api/articles/thinker-barbara-liskov/objections","thread_state_url":"https://miscsubjects.com/api/protocol/thread-state?target=thinker-barbara-liskov","proof_rule":"An action is proven by its ledger receipt, never by a 200 or a description."},"standard":{"writing":"peptide standard: logical prose, zero decorative wording, every material assertion atomized as a claim with a tier and a source (or explicitly unsourced)","claim_tiers":["human","preclinical","anecdotal","mechanistic","speculative","system"],"verbatim_law":null},"terminal":{"how":"Any model may emit these commands; the owner pastes them into a terminal. $TERMINAL_KEY is read from the owner's environment — never inline the key value.","claim_append":"curl -s -X POST https://miscsubjects.com/api/protocol/claim -H \"x-terminal-key: $TERMINAL_KEY\" -H 'content-type: application/json' -d '{\"slug\":\"thinker-barbara-liskov\",\"text\":\"<one atomized claim>\",\"tier\":\"<human|preclinical|anecdotal|mechanistic|speculative|system>\",\"source_ids\":[],\"who_claims\":\"<model>\",\"rationale\":\"<why material>\"}'","source_append":"curl -s -X POST https://miscsubjects.com/api/protocol/sources -H \"x-terminal-key: $TERMINAL_KEY\" -H 'content-type: application/json' -d '{\"slug\":\"thinker-barbara-liskov\",\"sources\":[{\"type\":\"review\",\"url\":\"<url>\",\"title\":\"<title>\",\"quote\":\"<verbatim quote>\",\"summary\":\"<one line>\"}]}'","objection":"curl -s -X POST https://miscsubjects.com/api/articles/thinker-barbara-liskov/objections -H 'content-type: application/json' -d '{\"actor\":\"<model>\",\"objection\":\"<attack>\",\"surface\":\"S1-S8\",\"minimum_patch\":\"<patch>\"}'  # open intake, no key","thread_update":"curl -s -X POST https://miscsubjects.com/api/protocol/thread-update -H 'content-type: application/json' -d '{\"actor\":\"<model>\",\"target\":\"thinker-barbara-liskov\",\"raw_text\":\"<material delta>\"}'  # open intake, no key","read_back":"curl -s https://miscsubjects.com/api/articles/thinker-barbara-liskov | python3 -c 'import json,sys; d=json.load(sys.stdin); print(json.dumps(d[\"claims\"][-3:], indent=1))'"}},"representations":{"article":"/a/thinker-barbara-liskov","json":"/api/articles/thinker-barbara-liskov","markdown":"/api/articles/thinker-barbara-liskov/bundle?format=markdown","skill":"/api/articles/thinker-barbara-liskov/skill","topology":"/api/articles/thinker-barbara-liskov/topology","versions":"/api/articles/thinker-barbara-liskov/revisions","invocations":"/api/articles/thinker-barbara-liskov/invocations"},"editorial_review":null,"editorial_audit":{"slug":"thinker-barbara-liskov","ok":false,"issues":[{"code":"hero_missing","message":"the article is published with no featured image","replacement":"Generate a hero that shows this article's own subject, inspect it, and record the inspection before this counts as finished. An article with no image is not finished."}]},"body_hash":"13378426dc05133c613eca27bd9c75d81ef9563421554dcbe0c846973559e74c"}}}