Processor Renaming in Asynchronous Environments.

Abstract

Fischer, Lynch and Paterson FLP proved that in a completely asynchronous system weak agreement cannot be achieved even in the presence of a single benign fault. Following the direction proposed in ABDK, we demonstrate the interesting fact that some weaker forms of processor cooperation are still achievable in such a situation, and in fact, even in the presence of up to t < n/2 such faulty processors. In particular, we show that n processors, each having a distinct name taken from an unbonded ordered domain, can individually choose new distinct names from a space of size n+t (where n is an obvious lower bound). In case the new names are required also to preserve the original order, we give an algorithm in which the space of new names is of size 2t(n - t + 1) - 1, which is tight.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1986
Accession Number
ADA174276

Entities

People

  • Amotz Bar-noy
  • David Peleg

Organizations

  • Stanford University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Asynchronous Systems
  • Classification
  • Coding
  • Communication Networks
  • Communication Systems
  • Computer Science
  • Computers
  • Environment
  • Mathematics
  • Notation
  • Observation
  • Security
  • Sequences
  • Standards
  • Universities

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computational Linguistics

Technology Areas

  • Space