Skip Navigation


The Computer Journal Advance Access originally published online on December 22, 2008
The Computer Journal 2009 52(4):499-509; doi:10.1093/comjnl/bxn069
This Article
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
52/4/499    most recent
bxn069v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Yan, K.-Q.
Right arrow Articles by Wang, S.-C.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2008. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

The Agreement Problem in Unreliable Scale-Free Networks

Kuo-Qin Yan1, Shun-Sheng Wang2 and Shu-Ching Wang3,*

1 Department of Business Administration, Chaoyang University of Technology, 168 Gifeng E. Rd., Wufeng, Taichung County, Taiwan 413, Republic of China
2 Department of Industrial Engineering and Management, Chaoyang University of Technology, 168 Gifeng E. Rd., Wufeng, Taichung County, Taiwan 413, Republic of China
3 Department of Information Management, Chaoyang University of Technology, 168 Gifeng E. Rd., Wufeng, Taichung County, Taiwan 413, Republic of China

* Corresponding author: scwang{at}cyut.edu.tw

Received 4 March 2008; revised 8 November 2008

Generally, tasks in a distributed system must reach agreement. This requires a set of processors to agree on a common value even though some components may be corrupt. There have been several significant studies on this agreement problem in regularized network environments such as the fully connected, broadcast and multicast networks. Recently, many large complex networks have emerged displaying a scale-free feature that influences the system to reach a common value in a novel way. This unanimity problem is called Byzantine agreement (BA). The BA problem is one of the most significant problems in designing a fault-tolerant distributed system. Unfortunately, existing BA protocols cannot cope with the new network environment, and the BA problem thus must be revisited. In this paper, a new BA protocol is proposed that adapts to the scale-free network (SFN) environment and derives its limit of allowable faulty components while maintaining the minimum number of message exchanges. The correctness and complexity of this protocol have been proved. It is observed that an SFN in conjunction with the proposed agreement protocol can tolerate the maximum number of faulty components.

Key Words: distributed processing • Byzantine agreement • fault tolerance • scale-free network • complex network and random network

Handling editor: Ing-Ray Chen


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.