Distributed Defeasible Speculative Reasoning in Ambient Environment

Reference: Lam, H.-P., Governatori, G., Satoh, K. & Hosobe, H. (2012). Distributed Defeasible Speculative Reasoning in Ambient Environment. In Computational Logic in Multi-Agent Systems (CLIMA XIII), Lecture Notes in Computer Science 7486, pp. 43–60. Springer. Springer DOI · DBLP conf/clima/LamGSH12

Summary

Lam, Governatori, Satoh and Hosobe propose Distributed Defeasible Speculative Reasoning (DDSR), a framework for agents that must act on incomplete information in open, unreliable, distributed environments such as ambient-intelligence and peer-to-peer settings. The motivating problem is that communication between agents is often delayed or broken, and agents may not know a priori which peers are present or willing to answer a query. Speculative computation addresses this by letting an agent proceed with tentative solutions computed from default assumptions about missing information, then revise those conclusions when the “real” answers eventually arrive.

The paper’s central move is to drop the assumption — standard in earlier speculative-computation work — that agents are hierarchically structured with a master coordinating slaves. Instead DDSR models the environment as a Multi-Context System: each ambient agent is an autonomous logic-based entity holding a local context theory, and dependencies on knowledge held by other agents are expressed through askable literals. Local inconsistency and ambiguity are resolved by the skeptical semantics of Defeasible Logic (DL); missing or uncertain external context is first filled by defaults for speculative reasoning and later replaced by returned answers. The authors characterise the framework with the argumentation semantics of defeasible logic (following Governatori et al.), which cleanly supports reasoning in the presence of conflicting information, and they give an operational model — a process-reduction / answer-arrival machinery that spawns computation processes, suspends those contradicted by newly returned answers, and reactivates consistent ones — together with a prototype implementation.

Key Ideas

Speculative computation for unreliable networks: compute tentative conclusions from default values when a peer’s answer is delayed or unavailable, then revise once the real answer returns — so an agent need not block on slow or failed communication.
No centralized control: generalises prior master/slave (hierarchical) speculative-reasoning frameworks to a fully distributed multi-agent system where agents have equivalent functionality and collaborate as peers.
Multi-Context System model: each agent holds a local context theory; cross-agent knowledge dependencies are represented as askable literals resolved by querying other agents.
Defeasible Logic as the local engine: strict rules, defeasible rules, and defeaters plus an acyclic superiority relation; tagged literals (+∆, −∆, +∂, −∂) distinguish definite from defeasible provability and handle conflicting rules skeptically.
Argumentation semantics: the framework is characterised in argumentation-theoretic terms, giving principled support for speculative conclusions under conflict (ambiguity-blocking / ambiguity-propagation variants).
Operational model: a process-reduction phase and an answer-arrival phase manage active/suspended computation processes — belief-contradicting processes are suspended and removed from the active set; consistent ones are (re)activated — with a prototype implementation of the model.

Connections

On the Acceptability of Arguments — Dung’s abstract Argumentation Framework, the semantic basis on which DL’s argumentation semantics rests
Argumentation Framework
Non-monotonic Reasoning — defeasible logic is a rule-based non-monotonic formalism
Circumscription - A Form of Nonmonotonic Reasoning — a sibling approach to non-monotonic reasoning (McCarthy)
Defeasible Logic
Speculative Computation
Multi-Context System
SPINdle — the defeasible-logic reasoner engineered by the same lead author
Ambient Intelligence
Impossibility of Distributed Consensus with One Faulty Process — the FLP reason speculation-under-delay matters: you cannot wait indefinitely on a possibly-failed peer

Conceptual Contribution

Claim: Agents in open, unreliable ambient environments can reason usefully despite missing or delayed information by speculating with default values under a defeasible, argumentation-based semantics — and this can be done in a fully decentralized multi-agent system with no master coordinator, generalising earlier hierarchical speculative-computation frameworks.
Mechanism: Model the environment as a Multi-Context System of local defeasible theories linked by askable literals; resolve local conflict with Defeasible Logic’s skeptical, superiority-ordered rules; fill missing external literals with defaults for Speculative Computation; give the whole an argumentation semantics; and drive it with an operational model (process-reduction + answer-arrival) that suspends belief-contradicting computations and revises conclusions as real answers arrive.
Concepts introduced/used: Defeasible Logic, Speculative Computation, Multi-Context System, askable literals, tagged literals (+∆/−∆/+∂/−∂), superiority relation, ambiguity blocking vs. propagation.
Stance: technical framework paper (logic-based MAS); positions defeasible + speculative reasoning as the right tool for the dynamic, imperfect-communication nature of Ambient Intelligence.
Relates to: builds on the defeasible-logic-as-argumentation programme of Governatori et al. and on Satoh’s speculative-computation line; contrasts with hierarchical (master/slave) speculative frameworks by removing centralized control; conceptually adjacent to Dung’s argumentation and to distributed-reasoning-under-uncertainty concerns in Non-monotonic Reasoning.

Backlinks

index

Linked Pages

Non-monotonic Reasoning

Reasoning in which adding premises may invalidate previously derivable conclusions. Required for default reasoning, exception handling, and business rules where new information retracts tentative conclusions.

In this vault

On the Acceptability of Arguments

On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming, and n-Person Games

Reference: Dung, P. M. (1995). On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artificial Intelligence, 77(2), pp. 321–357. DOI · Open access PDF (CUNY)

Summary

Dung shows that an enormous span of problems in AI — nonmonotonic reasoning, logic programming, n-person game theory — share a single underlying abstraction: a directed graph whose nodes are arguments and whose edges are attacks. He calls this an abstract argumentation framework (AF) and develops, in 30 pages, the entire theory of argument acceptability that has dominated computational argumentation ever since. The headline definitions: a set of arguments is conflict-free if it contains no attacker-attackee pair; admissible if it is conflict-free and defends each of its members against every attacker (an argument is defended if every attacker on it is itself attacked by something in the set); complete if it is admissible and contains every argument it defends; grounded (the unique smallest complete extension), preferred (a maximal admissible set), stable (admissible and attacks every argument outside it). Dung then proves the unifying results: the stable extensions of an AF coincide with the stable models of the corresponding logic program (Gelfond–Lifschitz); preferred extensions correspond to the preferred logic-programming semantics; default-logic extensions arise as stable extensions of an AF derived from default rules; and (the n-person game result) the stable extensions of a game’s argumentation graph correspond to the stable strategies of the game. The framework is content-agnostic — what an “argument” is is left to the instantiating theory — which is precisely what makes it apply across so many domains. Three decades later it is the substrate for legal reasoning systems, multi-agent dialogue protocols, structured argumentation calculi (ASPIC+, ABA, DeLP), and the theoretical underpinning of LLM-agent debate frameworks.

Key Ideas

Argument as a black box, attack as a binary relation: the AF (A, R) with A a set of arguments and R ⊆ A × A is the entire syntactic apparatus. All domain-specific structure (premises, conclusions, defeasible rules) is internalised when the AF is instantiated.
Defence as the operative concept: an argument a is defended by a set S iff every attacker of a is itself attacked by some member of S. Acceptability is “S defends every member of S.”
Family of extensions: admissible (defends itself), complete (admissible + closure), grounded (least complete — sceptical), preferred (maximal admissible — credulous), stable (admissible + attacks everything outside).
Universal correspondences: stable extensions ⇔ stable models of normal logic programs; preferred extensions ⇔ preferred semantics of logic programs; default-logic extensions ⇔ stable extensions of the AF generated by the defaults; the stable extensions of a 2-person game’s defeat graph ⇔ winning strategies.
Inference as fixed-point computation: each semantics is the fixed point of a characteristic operator on 2^A; the order-theoretic structure (complete partial order of admissible sets) makes the theory algorithmically tractable.
Sceptical vs credulous reasoning: every AF supports both — a is sceptically accepted iff in every preferred extension; credulously accepted iff in some preferred extension. The choice is a downstream policy decision.
Why it works as a unifier: nonmonotonic reasoning, default logic, logic programming with negation-as-failure, and game-theoretic equilibria all reduce to “find a coherent set of accepted positions in the presence of mutual challenge” — which is exactly what Dung’s framework computes.

Connections

Conceptual Contribution

Claim: Acceptability of arguments under attack is the abstraction common to nonmonotonic reasoning, logic programming with negation-as-failure, default logic, and equilibrium notions in n-person games. A single, content-free framework — a directed graph of arguments and attacks plus a fixed family of acceptability conditions — captures all of them.
Mechanism: Abstract argumentation framework (A, R); characteristic function F_AF : 2^A → 2^A mapping a set to the arguments it defends; admissible / complete / grounded / preferred / stable extensions defined as fixed points of F_AF under various conditions; instantiation theorems mapping logic-programming and default-logic problems to AFs and proving extension-correspondence.
Concepts introduced/used: Argumentation Framework, Attack Relation, Admissible Set, Grounded Extension, Preferred Extension, Stable Extension, Defence (Argumentation), Sceptical Reasoning, Credulous Reasoning.
Stance: foundational technical paper.
Relates to: Conceptually the missing companion of Circumscription - A Form of Nonmonotonic Reasoning (McCarthy 1980) — both address nonmonotonicity, but Dung gives an argumentation-graph framing that plays directly with logic-programming semantics where circumscription works at the level of model-theoretic minimisation. Provides the formal substrate beneath the dialogue-game tradition: a Persuasion Dialogue (Walton & Krabbe) is operationally a process for constructing the attack edges of a shared AF and computing extensions over it. The structured-argumentation systems (ASPIC+, ABA, DeLP, defeasible logic programming) instantiate Dung’s abstract framework with rule-based languages — and the SPL/Hence defeasible-logic engine used elsewhere in this vault is in this same family. In the LLM-agent era, multi-agent debate / self-consistency protocols recapitulate Dung’s machinery: agents generate arguments, attacks are mined from contradictions, and grounded/preferred extensions correspond to convergent / multi-modal answers. The paper’s reach into n-person games supplies a bridge to the game-theoretic / mechanism-design strands of Pact - A Choreographic Language for Agentic Ecosystems and Deals Among Rational Agents.

In this vault

Impossibility of Distributed Consensus with One Faulty Process

Reference

Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). “Impossibility of Distributed Consensus with One Faulty Process.” Journal of the ACM, 32(2), 374-382. URL

Summary

The FLP result is the canonical impossibility theorem of asynchronous distributed computing. Its statement is sharp: no deterministic consensus protocol can guarantee termination in an asynchronous message-passing system if even a single process may crash. Unlike earlier results that required Byzantine faults or lossy networks, FLP assumes reliable messaging and only one benign crash failure — yet still derives impossibility.

The proof proceeds by showing that every consensus protocol admits an initial bivalent configuration (one from which either decision value is still reachable), and that from any bivalent configuration an adversary scheduler can always delay one message to force the system into another bivalent configuration. Thus an admissible run exists in which no process ever decides. The core technical tool is the commutativity of disjoint process steps (Lemma 1) and a careful analysis of “critical” configurations where a specific process’s next step is decision-forcing.

The result cleaves distributed computing into what is possible under various synchrony assumptions. Real-world protocols respond by weakening one axis: Paxos and Raft adopt partial synchrony and accept that liveness can only be guaranteed “eventually”; randomized consensus (Ben-Or, Rabin) achieves termination with probability 1; failure detectors (Chandra-Toueg ◊S) encapsulate the synchrony needed. FLP remains the bedrock boundary against which all consensus engineering is measured.

Key Ideas

Consensus problem: N processes, binary inputs; non-faulty processes must all decide the same value; some initial configuration must admit each decision.
Asynchronous model: unbounded message delays; no clocks; no timeouts.
One crash failure: the weakest possible fault assumption that still breaks consensus.
Bivalent configurations: states from which both 0 and 1 outcomes are still reachable.
Adversary scheduler: by reordering message deliveries, keeps the system in a bivalent configuration forever.
Safety vs. liveness: FLP shows safety + liveness + fault-tolerance cannot coexist in pure async.
Escape hatches: partial synchrony, randomization, failure detectors, or accepting non-termination in corner cases.

Connections

CAP Theorem — CAP is a direct relative: in partition-prone systems, atomic read/write also unattainable.
CALM Theorem — monotonic logic sidesteps consensus by avoiding it.
Keeping CALM - When Distributed Consistency is Easy
Coordination Avoidance — the design pattern motivated by FLP.
Gossip Protocols — probabilistic convergence as an alternative to deterministic agreement.
Time Clocks and the Ordering of Events in a Distributed System — Lamport’s logical time underlies the proof’s commutation arguments.
Knowledge and Common Knowledge in a Distributed Environment — common knowledge likewise unattainable in async systems.

Conceptual Contribution

SPINdle

(page does not exist)

Circumscription - A Form of Nonmonotonic Reasoning

Circumscription — A Form of Non-Monotonic Reasoning (1980)

Reference: John McCarthy (1980). “Circumscription — A Form of Non-Monotonic Reasoning.” Artificial Intelligence 13(1-2): 27-39. The author-hosted PDF (2004 reformatting) adds a 1996 addendum; file is mccarthy-circumscription1980.pdf. Disambiguated from the 1986 sequel Circumscription - Applications to Formalizing Common Sense Knowledge which introduces formula circumscription and the abnormality predicate. URL

Summary

McCarthy’s landmark treatment of the qualification problem: any common-sense rule (e.g. “a rowboat can be used to cross a river”) is subject to an open-ended list of possible defeaters (no oars, a leak, cannibals, a sea monster) that cannot plausibly be enumerated in advance. Standard first-order logic is monotonic — adding premises never removes conclusions — so it cannot support the everyday inference “no defeater mentioned, therefore none present.”

Circumscription is a formally specified rule of conjecture that licenses jumping to the conclusion that the objects (or tuples) shown to satisfy a predicate P are the only ones that do. Adding a sentence “There is a bridge upstream” then legitimately retracts the original conclusion — non-monotonicity is thus built in at the rule-of-conjecture level, not by weakening the logic itself. The paper explains predicate circumscription, shows how domain circumscription (minimal inference) is a special case, works through the missionaries-and-cannibals puzzle to show how circumscription blocks sea-monster-style pedantry, and connects the technique to default reasoning (Reiter), to THNOT in MICROPLANNER (Sussman et al.), and to McCarthy’s broader project of formalising common-sense knowledge in logic.

Together with Ascribing Mental Qualities to Machines and First Order Theories of Individual Concepts and Propositions, this is one of the three pillars of McCarthy’s logicist programme. Its non-monotonic commitment is directly inherited by the CBCL proposal (partial-understanding messages) and by Elephant 2000’s treatment of commitments and speech-act preconditions.

Key Ideas

The qualification problem: common-sense rules have unbounded implicit preconditions that cannot be enumerated.
Monotonicity of FOL is the obstacle; circumscription is a rule of conjecture over FOL, not a modification of its proof theory.
Predicate circumscription: the tuples shown to satisfy P are all the tuples that do.
Domain circumscription (minimal inference) subsumed as a special case.
Non-monotonicity at the level of conjecture rather than entailment — new facts retract conjectures without breaking soundness of FOL.
“Common-sense knowledge must be expressed in a form that says a boat crosses rivers unless something prevents it” — ontology must admit prevention-entities.

Connections

Ascribing Mental Qualities to Machines — philosophical companion; circumscription is the formal tool for the ascriptive logicist programme argued for there.
First Order Theories of Individual Concepts and Propositions — shares the methodology of extending expressive power without abandoning first-order logic.
Common Sense Reasoning
Knowledge Representation
Elephant 2000 - A Programming Language Based on Speech Acts — Elephant’s commitments and speech-act preconditions are governed by defeasible, common-sense rules of exactly the kind circumscription was designed to formalise.
Foundations of Logic Programming - Lloyd — negation-as-failure in logic programming is a close cousin of circumscription.
Common Business Communication Language — CBCL’s ADJECTIVE construct and partial-understanding fallback are predicated on non-monotonic reading.

Conceptual Contribution

Claim: Common-sense reasoning requires non-monotonic inference, and this can be supplied to ordinary first-order logic by a rule of conjecture (circumscription) without modifying the logic itself.
Mechanism: Predicate circumscription schema: from a set of facts A mentioning P, conjecture that the only tuples satisfying P are those whose satisfaction follows from A. Domain circumscription as minimal-model inference. Combination with ordinary FOL rules of inference. Explicit introduction into the ontology of prevention-entities (“something wrong with the boat”).
Concepts introduced/used: Circumscription, Non-monotonic Reasoning, Qualification Problem, Default Reasoning, Minimal Model, Common Sense Reasoning, Rule of Conjecture.
Stance: foundational
Relates to: One of the three McCarthy pillars alongside Ascribing Mental Qualities to Machines and First Order Theories of Individual Concepts and Propositions; provides the defeasibility semantics that Elephant 2000 - A Programming Language Based on Speech Acts needs for commitment revision and Common Business Communication Language needs for partial-understanding messaging.

Distributed Defeasible Speculative Reasoning in Ambient Environment

Summary

Key Ideas

Connections

Conceptual Contribution

Tags

Backlinks