Publication

Uniform Consensus Harder than Consensus

André Schiper
2000
Reports

Abstract

We compare the consensus problem with the uniform consensus problem in synchronous systems. In contrast to consensus, uniform consensus is not solvable in synchronous systems with byzantine failures. This still holds for the omission failure model if a majority of processes may be faulty. For the crash failure model, both consensus and uniform consensus are solvable, no matter how many processes are faulty. We consider this failure model and we examine the number of rounds required to reach a decision in consensus and uniform consensus algorithms. We show that compared with the best consensus algorithm, any uniform consensus algorithm takes at least one additional round to take a decision. We thus prove that uniform consensus is also harder than consensus whatever the failure model is.

Official source

https://infoscience.epfl.ch/entities/publication/43d77712-7f80-446c-a788-810598a0b3c6

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

André Schiper
2000
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/43d77712-7f80-446c-a788-810598a0b3c6

About this result

Related concepts (7)

Consensus (computer science)

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts.

Byzantine fault

A Byzantine fault (also Byzantine generals problem, interactive consistency, source congruency, error avalanche, Byzantine agreement problem, and Byzantine failure) is a condition of a computer system, particularly distributed computing systems, where components may fail and there is imperfect information on whether a component has failed. The term takes its name from an allegory, the "Byzantine generals problem", developed to describe a situation in which, to avoid catastrophic failure of the system, the system's actors must agree on a concerted strategy, but some of these actors are unreliable.

Byzantine Empire

The Byzantine Empire, also referred to as the Eastern Roman Empire, was the continuation of the Roman Empire primarily in its eastern provinces during Late Antiquity and the Middle Ages, when its capital city was Constantinople. It survived the fall of the Western Roman Empire in the 5th century AD and continued to exist until the fall of Constantinople to the Ottoman Empire in 1453. During most of its existence, the empire remained the most powerful economic, cultural, and military force in the Mediterranean world.