Uniform consensus is harder than consensus

No abstract is available for this paper.

• Publication year

  2004

• Venue

  J. Algorithms

• Publication date

  2004-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.jalgor.2003.11.001
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Lower bounds for asynchronous consensus

  2006cited by this paper
• Validity Conditions in Agreement Problems and Time Complexity

  2004cited by this paper
• A simple proof of the uniform consensus synchronous lower bound

  2003cited by this paper
• A Layered Analysis of Consensus

  2002cited by this paper
• Synchronous system and perfect failure detector: Solvability and efficiency issues

  2000cited by this paper
• Revisiting Safety and Liveness in the Context of Failures

  2000cited by this paper
• A Simple Bivalency Proof that t-Resilient Consensus Requires t + 1 Rounds

  1998influential reference
• Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony

  1998cited by this paper
• Unreliable failure detectors for reliable distributed systems

  1996cited by this paper
• Revistiting the Relationship Between Non-Blocking Atomic Commitment and Consensus

  1995cited by this paper
• A Modular Approach to Fault-Tolerant Broadcasts and Related Problems

  1994cited by this paper
• Distributed Algorithms

  1992cited by this paper
• Fault-tolerant Broadcasts and Multicasts: The Problem of Inconsistency and Contamination

  1992cited by this paper
• Unreliable Failure Detectors for Asynchronous Systems

  1991cited by this paper
• On the Relationship Between the Atomic Commitment and Consensus Problems

  1990influential reference
• Early stopping in Byzantine agreement

  1990influential reference
• Automatically Increasing the Fault-Tolerance of Distributed Algorithms

  1990influential reference
• Consensus in the presence of partial synchrony

  1988cited by this paper
• Shifting gears: changing algorithms on the fly to expedite Byzantine agreement

  1987cited by this paper
• Knowledge and Common Knowledge in a Byzantine Environment I: Crash Failures

  1986cited by this paper
• Distributed agreement in the presence of processor and communication faults

  1986cited by this paper
• Impossibility of distributed consensus with one faulty process

  1985influential reference
• Patterns of communication in consensus protocols

  1984cited by this paper
• On the minimal synchronism needed for distributed consensus

  1983cited by this paper
• The Weak Byzantine Generals Problem

  1983influential reference
• The Byzantine Generals Problem

  1982cited by this paper
• Polynomial algorithms for multiple processor agreement

  1982influential reference
• A Lower Bound for the Time to Assure Interactive Consistency

  1982cited by this paper
• Cryptographic protocols

  1982influential reference
• Reaching Agreement in the Presence of Faults

  1980cited by this paper
• SIFT: Design and analysis of a fault-tolerant computer for aircraft control

  1978cited by this paper

• Revisiting Lower Bounds for Two-Step Consensus

  2025cites this paper
• Topological Characterization of Stabilizing Consensus

  2024cites this paper
• Asynchronous Consensus in Synchronous Systems Using send_to_all Primitive

  2023cites this paper
• Rational Uniform Consensus with General Omission Failures

  2022cites this paper
• Taming the Contention in Consensus-Based Distributed Systems

  2021cites this paper
• Silence

  2020cites this paper
• P4xos: Consensus as a Network Service

  2020cites this paper
• Higher-Order Quantifier Elimination, Counter Simulations and Fault-Tolerant Systems

  2020cites this paper
• Partitioned Paxos via the Network Data Plane

  2019cites this paper
• Impact FD: An Unreliable Failure Detector Based on Process Relevance and Confidence in the System

  2018cites this paper
• Multi-shot distributed transaction commit

  2018cites this paper
• Fault-Tolerant Message-Passing Distributed Systems

  2018cites this paper
• Series in Informatics P 4 xos : Consensus as a Network Service

  2018cites this paper
• Silence

  2018cites this paper
• Parameterized Model Checking of Synchronous Distributed Algorithms by Abstraction

  2018influential citation
• The Complexity of Reliable and Secure Distributed Transactions

  2018influential citation
• How Fast can a Distributed Transaction Commit?

  2017cites this paper
• Blocks and Chains: Introduction to Bitcoin, Cryptocurrencies, and Their Consensus Mechanisms

  2017cites this paper
• COMPUTAÇÃO On-Time Fast Paxos

  2017cites this paper
• A Low-latency Consensus Algorithm for Geographically Distributed Systems

  2017cites this paper
• Speeding up Consensus by Chasing Fast Decisions

  2017cites this paper
• Toward a Faster Fault Tolerant Consensus to Maintain Data Consistency in Collaborative Environments

  2017cites this paper
• Unbeatable Set Consensus via Topological and Combinatorial Reasoning

  2016cites this paper
• Leaderless Consensus: The State of the Art

  2016cites this paper
• Making Fast Consensus Generally Faster

  2016cites this paper
• GMU: Genuine Multiversion Update-Serializable Partial Data Replication

  2016cites this paper
• Making Fast Consensus Generally Faster [ Technical Report ]

  2016cites this paper
• Practical scalable consensus for pseudo-synchronous distributed systems

  2015cites this paper
• On Improving Distributed Transactional Memory through Nesting, Partitioning and Ordering

  2015cites this paper
• On Exploiting Locality for Generalized Consensus

  2015cites this paper
• On the Fault-tolerance and High Performance of Replicated Transactional Systems

  2015influential citation
• UNIVERSIDADE FEDERAL DE SANTA CATARINA PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA EM AUTOMAÇÃO E SISTEMAS

  2014cites this paper
• Non-blocking Atomic Commitment with Byzantine Faults

  2014cites this paper
• The Generalized Loneliness Detector and Weak System Models for k-Set Agreement

  2014cites this paper
• Unbeatable consensus

  2014influential citation
• Easy Impossibility Proofs for k-Set Agreement

  2013influential citation
• Proposition et implémentation d’un protocole de la diffusion atomique dans les systèmes distribués

  2013cites this paper
• Protocolo de difusão síncrona totalmente ordenada para aglomerados de alto desempenho

  2013cites this paper
• Problème du Consensus dans le Modèle Homonyme

  2013cites this paper
• Early-deciding consensus is expensive

  2013influential citation
• Engineering a communication protocol stack to support consensus in sensor networks

  2013cites this paper
• Good, Better, Best! - Unbeatable Protocols for Consensus and Set Consensus

  2013cites this paper
• E-cast: Elastic Multicast

  2011cites this paper
• The Complexity of Early Deciding Set Agreement

  2011cites this paper
• Fast Genuine Generalized Consensus

  2011cites this paper
• Reducing Costs of Byzantine Fault Tolerant Distributed Applications

  2011cites this paper
• Synchronous consensus under hybrid process and link failures

  2011cites this paper
• Consensus in the presence of mortal Byzantine faulty processes

  2011cites this paper
• Easy impossibility proofs for k-set agreement in message passing systems

  2011cites this paper
• THE OMEGA FAILURE DETECTOR IN THE CRASH-RECOVERY MODEL

  2010cites this paper
• Structural failure models for fault-tolerant distributed computing

  2010influential citation
• Fault-tolerant Agreement in Synchronous Message-passing Systems

  2010cites this paper
• Weak Synchrony Models and Failure Detectors for Message Passing (k-)Set Agreement

  2009cites this paper
• The Complexity of Early Deciding Set Agreement: How can Topology help?

  2009influential citation
• Message and time efficient consensus protocols for synchronous distributed systems

  2008influential citation
• Impossibility Results and Lower Bounds for Consensus under Link Failures

  2008cites this paper
• Narrowing power vs efficiency in synchronous set agreement: Relationship, algorithms and lower bound

  2008cites this paper
• The overhead of consensus failure recovery

  2007cites this paper
• Synchronous Consensus with Mortal Byzantines

  2007cites this paper
• The Time-Complexity of Local Decision in Distributed Agreement

  2007cites this paper
• Making Distributed Applications Robust

  2007cites this paper
• Ììììø Óùòò× Óò Öðý Äó Blockin Blockinð ××óò× Ò Íòòòóöñ Óò××ò×ù×´´üøøòòòò ×øöö Blockinøµ

  2007influential citation
• Lower Bounds for Achieving Synchronous Consensus with Orderly Crash Failure

  2007cites this paper
• Indirect channels: a bandwidth-saving technique for fault-tolerant protocols

  2007cites this paper
• A topological treatment of early-deciding set-agreement

  2006cites this paper
• Synchronous condition-based consensus

  2006cites this paper
• Condition adaptation in synchronous consensus

  2006cites this paper
• Minimizing latency of agreement protocols

  2006influential citation
• Strongly Terminating Early-Stopping k-Set Agreement in Synchronous Systems with General Omission Failures

  2006cites this paper
• Fast Paxos

  2006cites this paper
• Optimal and Practical WAB-Based Consensus Algorithms

  2006cites this paper
• The Power and Limit of Adding Synchronization Messages for Synchronous Agreement

  2006cites this paper
• Coping with dependent failures in distributed systems

  2006cites this paper
• Optimistic Generic Broadcast

  2005cites this paper
• Time-complexity bounds on agreement problems

  2005cites this paper
• A bivalency proof of the lower bound for uniform consensus

  2005influential citation
• An Improved Algorithm for Adaptive Condition-Based Consensus

  2005cites this paper
• Fast fault-tolerant agreement algorithms

  2005cites this paper
• Early-Stopping k-Set Agreement in Synchronous Systems Prone to Any Number of Process Crashes

  2005cites this paper
• Decision optimal early-stopping k-set agreement in synchronous systems prone to send omission failures

  2005cites this paper
• Generating Fast Atomic Commit from Hyperfast Consensus

  2005cites this paper
• From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement

  2005influential citation
• Lower Bounds for Achieving Synchronous Early Stopping Consensus with Orderly Crash Failures

  2005cites this paper
• Latency-optimal Uniform Atomic Broadcast algorithm

  2004cites this paper
• Validity Conditions in Agreement Problems and Time Complexity

  2004influential citation
• The Synchronous Condition-Based Consensus Hierarchy

  2004cites this paper
• Fast non-blocking atomic commit: an inherent trade-off

  2004cites this paper
• Consensus on transaction commit

  2004cites this paper
• Simple Bivalency Proofs of the Lower Bounds in Synchronous Consensus Problems

  2004influential citation
• An approach to achieve message efficient early-stopping uniform consensus protocols

  2004cites this paper
• Synchronous Consensus for dependent process failures

  2003influential citation
• Tight Bounds on Early Local Decisions in Uniform Consensus

  2003cites this paper
• An optimal early stopping uniform consensus protocol in synchronous distributed systems with orderly crash failures

  2003influential citation
• Middleware for Supporting Inter-organizational Interactions

  2003cites this paper
• Using Conditions to Expedite Consensus in Synchronous Distributed Systems

  2003influential citation
• Distributed programming for dummies: a shifting transformation technique

  2003cites this paper
• Comparing the atomic commitment and consensus problems

  2003cites this paper
• Condition-Based Consensus in Synchronous Systems

  2003cites this paper
• The Complexity of Early-Deciding in Unreliable Synchronous Networks

  2003influential citation
• A consensus algorithm for synchronous distributed systems using mobile agent

  2002influential citation