A lower bound for the time to assure interactive consistency
From MaRDI portal
Publication:1168726
DOI10.1016/0020-0190(82)90033-3zbMath0493.68026OpenAlexW2039164882MaRDI QIDQ1168726
Michael J. Fischer, Nancy A. Lynch
Publication date: 1982
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(82)90033-3
Related Items
On the round complexity of randomized Byzantine agreement, Reliable synchronization in distributed systems, An algorithmic approach to the asynchronous computability theorem, How processes learn, Common knowledge and consistent simultaneous coordination, Broadcast-optimal two round MPC with an honest majority, Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources, Synchronous condition-based consensus, The Heard-Of model: computing in distributed systems with benign faults, Lower bound for scalable Byzantine agreement, Secure Computation with Minimal Interaction, Revisited, Agreement in synchronous networks with ubiquitous faults, Performance study of Byzantine agreement protocol with artificial neural network, Programming simultaneous actions using common knowledge, Robust gossiping with an application to consensus, Improving the round complexity of VSS in point-to-point networks, Reliable broadcasts and communication models: tradeoffs and lower bounds, The topology of distributed adversaries, Visiting Byzantine Agreement underlying ad hoc environment, The perfectly synchronized round-based model of distributed computing, Synchronous \(t\)-resilient consensus in arbitrary graphs, Detect, pack and batch: perfectly-secure MPC with linear communication and constant expected time, Cloture Votes:n/4-resilient Distributed Consensus int + 1 rounds, Message-optimal protocols for Byzantine Agreement, Modular construction of an efficient 1-bit Byzantine agreement protocol, Constant-Round Asynchronous Multi-Party Computation Based on One-Way Functions, Byzantine preferential voting, On the number of authenticated rounds in Byzantine Agreement, Optimal algorithms for synchronous Byzantine \(k\)-set agreement, Deterministic Randomness Extraction from Generalized and Distributed Santha--Vazirani Sources, Synchronous counting and computational algorithm design, Asymptotically free broadcast in constant expected time via packed VSS, An algorithm for identification of maliciously faulty units, Efficient Counting with Optimal Resilience, Uniform atomic broadcast and consensus in fully anonymous synchronous systems with crash failures, Completeness theorems for adaptively secure broadcast, Consensus in the presence of mortal Byzantine faulty processes, Brief Announcement: Improved Consensus in Quantum Networks, The overhead of consensus failure recovery, The best of both worlds: Guaranteeing termination in fast randomized Byzantine agreement protocols, A new solution for the Byzantine agreement problem, Knowledge and common knowledge in a Byzantine environment: Crash failures, Verifiable secret sharing in a total of three rounds, Fast and simple distributed consensus, Optimal time byzantine agreement for t <n/8 with linear-messages, Hundreds of impossibility results for distributed computing, Modular construction of a Byzantine agreement protocol with optimal message bit complexity, Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement, On the message complexity of binary Byzantine agreement under crash failures, Efficient parallel algorithms can be made robust, A self-adjusting algorithm for Byzantine agreement, Optimistically tuning synchronous Byzantine consensus: another win for null messages, Combining fault injection and model checking to verify fault tolerance, recoverability, and diagnosability in multi-agent systems, Efficient algorithms for anonymous Byzantine agreement, Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures, Unnamed Item, Lower bounds for weak Byzantine agreement, Narrowing Power vs. Efficiency in Synchronous Set Agreement, Round-preserving parallel composition of probabilistic-termination cryptographic protocols, On expected constant-round protocols for Byzantine agreement, Near-optimal self-stabilising counting and firing squads, Consensus algorithms with one-bit messages, Simultaneity is harder than agreement, Probabilistic Termination and Composability of Cryptographic Protocols, Probabilistic termination and composability of cryptographic protocols, Narrowing power vs efficiency in synchronous set agreement: relationship, algorithms and lower bound, Using knowledge to optimally achieve coordination in distributed systems, Wait-free implementations in message-passing systems, On the round complexity of Byzantine agreement without initial set-up, Fault-tolerant algorithms for tick-generation in asynchronous logic, Computing (and Life) Is All about Tradeoffs, Unnamed Item, Efficient agreement using fault diagnosis., Broadcast-optimal two-round MPC
Cites Work
