An optimal early stopping algorithm with one-bit messages for distributed consensus

10 References

Bibliographic Information

Other Title
  • 分散合意のための1-ビットメッセージ最適早期停止アルゴリズム

Search this article

Description

We consider a synchronous distributed system of n processors at most t of which are faulty. Each correct processors has an initial binary value. The Distributed Consensus problem is a problem for all correct processors to agree on a common value that was held by one of them despite any behavior of faulty processors. Many distributed algorithms have been studied for this problem. This paper presents an early stopping algorithm (i.e., the number of rounds is proportional to the number of actual faults f) which achives round and message optimality simultaneously. This algorithm requires number of prosessors n ≥ (4t+1)(t+1), number of rounds r=min{f+2,t+1}, maximal message bit m=1.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 47 33-40, 1995-09-21

    Information Processing Society of Japan (IPSJ)

References(10)*help

See more

Details 詳細情報について

  • CRID
    1573105977000141312
  • NII Article ID
    110002812317
  • NII Book ID
    AN1009593X
  • ISSN
    09196072
  • Text Lang
    ja
  • Data Source
    • CiNii Articles

Report a problem

Back to top