Please use this identifier to cite or link to this item:
Title: Global data computation in chordal rings
Authors: Wang, X.
Teo, Y.M. 
Keywords: Chordal rings
Global data computation
Non-round-based protocol
Perfect failure detector
Issue Date: 2009
Citation: Wang, X., Teo, Y.M. (2009). Global data computation in chordal rings. Journal of Parallel and Distributed Computing 69 (8) : 725-736. ScholarBank@NUS Repository.
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.
Source Title: Journal of Parallel and Distributed Computing
ISSN: 07437315
DOI: 10.1016/j.jpdc.2009.04.007
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Mar 20, 2019


checked on Mar 5, 2019

Page view(s)

checked on Mar 3, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.