Please use this identifier to cite or link to this item:
|Title:||Global data computation in chordal rings|
Global data computation
Perfect failure detector
|Source:||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. https://doi.org/10.1016/j.jpdc.2009.04.007|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 7, 2017
WEB OF SCIENCETM
checked on Nov 29, 2017
checked on Dec 11, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.