Knowledge and common knowledge in a Byzantine environment: Crash failures

DOI10.1016/0890-5401(90)90014-9zbMath0705.68019OpenAlexW2091004544MaRDI QIDQ918186

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(90)90014-9

zbMATH Keywords

distributed systems lower bound common knowledge protocols bivalent agreement simultaneous Byzantine agreement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10)

Related Items

Unbeatable consensus, Common knowledge and consistent simultaneous coordination, Synchronous condition-based consensus, The \(k\)-simultaneous consensus problem, Wanted dead or alive: epistemic logic for impure simplicial complexes, A faster distributed protocol for constructing a minimum spanning tree, I'm OK if you're OK: On the notion of trusting commmunication, Common knowledge and update in finite environments, The Firing Squad Problem Revisited., Coordinated consensus in dynamic networks, Error-free multi-valued consensus with byzantine failures, Distributed graph coloring in a few rounds, MIS on trees, Toward more localized local algorithms, The complexity of robust atomic storage, Resilience of mutual exclusion algorithms to transient memory faults, The impact of memory models on software reliability in multiprocessors, A complexity separation between the cache-coherent and distributed shared memory models, From bounded to unbounded concurrency objects and back, The space complexity of long-lived and one-shot timestamp implementations, Locally checkable proofs, Fault-tolerant spanners, Adaptively secure broadcast, revisited, Scalable rational secret sharing, Analyzing consistency properties for fun and profit, Transforming worst-case optimal solutions for simultaneous tasks into all-case optimal solutions, Optimal-time adaptive strong renaming, with applications to counting, The round complexity of distributed sorting, A tight unconditional lower bound on distributed randomwalk computation, Minimum congestion mapping in a cloud, Conflict on a communication channel, Stability of a peer-to-peer communication system, Tight bounds on information dissemination in sparse mobile networks, Time-efficient randomized multiple-message broadcast in radio networks, Faster information dissemination in dynamic networks via network coding, Determination of social laws for multi-agent mobilization, Synchronous \(t\)-resilient consensus in arbitrary graphs, Communication pattern logic: epistemic and topological views, The solvability of consensus in iterated models extended with safe-consensus, Message-optimal protocols for Byzantine Agreement, Impure Simplicial Complexes: Complete Axiomatization, Optimal algorithms for synchronous Byzantine \(k\)-set agreement, A Sufficient Condition for Gaining Belief in Byzantine Fault-Tolerant Distributed Systems, No double discount: condition-based simultaneity yields limited gain, Comparing the Update Expressivity of Communication Patterns and Action Models, Optimal Eventual Byzantine Agreement Protocols with Omission Failures, A computer scientist looks at game theory., Unnamed Item, Continuous consensus via common knowledge, Unnamed Item, Order optimal information spreading using algebraic gossip, Continuous Consensus with Failures and Recoveries, No Double Discount: Condition-Based Simultaneity Yields Limited Gain, Knowledge-based programs, A note on knowledge-based programs and specifications, Hundreds of impossibility results for distributed computing, Using counterfactuals in knowledge-based programming, A knowledge-based analysis of global function computation, Fast and compact self-stabilizing verification, computation, and fault detection of an MST, The complexity of almost-optimal simultaneous coordination, On the message complexity of binary Byzantine agreement under crash failures, A guide to completeness and complexity for modal logics of knowledge and belief, Combining fault injection and model checking to verify fault tolerance, recoverability, and diagnosability in multi-agent systems, Structuring unreliable radio networks, Continuous consensus with ambiguous failures, Byzantine agreement with homonyms, Distributed deterministic edge coloring using bounded neighborhood independence, Compact policy routing, Continuous Consensus with Ambiguous Failures, Near-optimal self-stabilising counting and firing squads, Simultaneity is harder than agreement, Choosing social laws for multi-agent systems: Minimality and simplicity, The firing squad problem revisited, Using knowledge to optimally achieve coordination in distributed systems, On the round complexity of Byzantine agreement without initial set-up, Xheal, A simple proof of the uniform consensus synchronous lower bound., Naming and identity in epistemic logic. II: A first-order logic for naming, Knowledge in shared memory systems.

Cites Work