REACHING APPROXIMATE AGREEMENT ON HYPERCUBE

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.