Global data computation in chordal rings

Abstract

Existing Global Data Computation (GDC) protocols for asynchronous systems are round-based algorithms designed for fully connected networks. In this paper, we discuss GDC in asynchronous chordal rings, a non-fully connected network. The virtual links approach to solve the consensus problem may be applied to GDC for non-fully connected networks, but it incurs high message overhead. To reduce the overhead, we propose a new non-round-based GDC protocol for asynchronous chordal rings with perfect failure detectors. The main advantage of the protocol is that there is no notion of rounds. Every process creates two messages initially, with one message traversing in a clockwise direction and visiting each and every process in the chordal ring. The second message traverses in a counterclockwise direction. When there is direct connection between two processes, a message is sent directly. Otherwise, the message is sent via virtual links. When the two messages return, the process decides according to the information maintained by the two messages. The perfect failure detector of a process need only detect the crash of neighboring processes, and the crash information is disseminated to all other processes. Analysis and comparison with two virtual links approaches show that our protocol reduces message complexity significantly. © 2009 Elsevier Inc. All rights reserved.