Reaching approximate agreement on hypercube

Ren Lianq Cheng, Chung-Ping Chung*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

The interactive convergence algorithm has been used for reaching agreement in systems with multiple procesors. This algorithm must utilize a broadcast mechanism regardless of the underlying architecture. This paper proposes an appropriate algorithm, the local interactive convergence algorithm, for reaching an approximate agreement on systems with high locality. The hypercube is one such system, and it is used as a vehicle for studying the algorithm. This algorithm requires only local information with simple computation. Convergence rate analysis shows that the local interactive convergence algorithm is able to achieve an approximate agreement in a predetermined rate.

Original languageEnglish
Pages (from-to)765-775
Number of pages11
JournalParallel Computing
Volume19
Issue number7
DOIs
StatePublished - 1 Jan 1993

Keywords

  • Approximate agreement
  • convergence rate analysis
  • hypercube architecture
  • local interactive convergence algorithm

Fingerprint Dive into the research topics of 'Reaching approximate agreement on hypercube'. Together they form a unique fingerprint.

Cite this