The Weakest Failure Detector for Solving Consensus

Abstract

We determine what information about failures is necessary and sufficient to solve Consensus in asynchronous distributed systems subject to crash failures. In [CT91], we proved that W, a failure detector that provides surprisingly little information about which processes have crashed, is sufficient to solve Consensus in asynchronous systems with a majority of correct processes. In this paper, we prove that to solve Consensus, any failure detector has to provide at least as much information as W. Thus, W is indeed the weakest failure detector for solving Consensus in asynchronous systems with a majority of correct processes.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1992
Accession Number
ADA253611

Entities

People

  • Sam Toueg
  • Tushar D. Chandra
  • Vassos Hadzilacos

Organizations

  • Cornell University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Agreements
  • Algorithms
  • Asynchronous Systems
  • Automata
  • Coding
  • Computations
  • Computer Science
  • Computers
  • Consensus Algorithms
  • Construction
  • Damage Detection
  • Detection
  • Detectors
  • Distributed Computing
  • Simulations
  • Universities

Readers

  • Aviation Safety Risk Assessment.
  • Linear Algebra
  • Team-Based Human-Centered Cognitive Task Decision Making and Information Performance.