Finding a Majority Among N Votes.

Abstract

A commonly-used technique for fault-tolerant computing is to perform n redundant computations and then vote on the results, choosing on the majority value if one exists. We present an algorithm for carrying out the voting which uses (3n/2) -2 comparisons, and we prove the algorithms optimal. This solves Problem 81-5 posed in the Journal of Algorithms, June 1981. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1982
Accession Number
ADA121160

Entities

People

  • Michael J. Fischer
  • Steven Salzberg

Organizations

  • Yale University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Fault Tolerant Computing
  • Information Systems
  • Marine Corps
  • Mathematics
  • Military Research
  • New York
  • Standards
  • System Software
  • Technical Information Centers
  • Universities

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Systems Analysis and Design