Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Information Science and Engineering, Vol.18 No.4, pp.601-625 (July 2002)


Reaching Strong Consensus in a General Network

Hsien-Sheng Hsiao, Yeh-Hao Chin* and Wei-Pang Yang**
Department of Industrial Technology Education
National Taiwan Normal University
Taipei, 106 Taiwan
*Department of Computer Science
National Tsing Hua University
Hsinchu, 300 Taiwan
**Department of Computer and Information Science
National Chiao Tung University

The strong consensus (SC) problem is a variant of the conventional distributed consensus problem (also known as the Byzantine agreement problem). The SC problem requires that the agreed value among fault-free processors be one of the fault-free processoríŽs initial values. Originally, the problem was studied in a fully connected network with malicious faulty processors. In this paper, the SC problem is re-examined in a general network, in which the components (processors and communication links) may be subjected to different faulty types simultaneously (also called the hybrid fault model or mixed faulty types) and the network topology does not have to be fully connected. The proposed protocol can tolerate the maximum number of tolerable faulty components such that each fault-free processor obtains a common value for the SC problem in a general network.

Keywords: Byzantine agreement, fault-tolerant distributed system, general network, hybrid fault model, strong consensus

Full Text (ą■Ąň└╔) Retrieve PDF document (200207_09.pdf)

Received May 11, 1999; revised November 13, 2000; accepted April 16, 2001.
Communicated by Jang-Ping Sheu.