Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18]


Journal of Information Science and Engineering, Vol. 22 No. 5, pp. 1265-1277 (September 2006)

A Fault-Tolerant Protocol for Generating Sequence Numbers for Total Ordering Group Communication in Distributed Systems*

Chih-Ming Hsiao and Ge-Ming Chiu
Department of Computer Science and Information Engineering
National Taiwan University of Science and Technology
Taipei, 106 Taiwan

In this paper, we propose a fault-tolerant scheme for generating global sequence numbers for total ordering in group communication. Our method is based on the notion of quorums, which have been used mostly to solve the mutual exclusion problem. In our scheme, each process in the group may initiate the generation of sequence numbers independently for messages emitted by itself. For the sake of enhancing fault tolerance, the information about the sequence numbers is maintained by all the members of a quorum at all times. We show that the sequence numbers generated by our scheme are unique, consecutive natural numbers. Our mechanism only incurs a moderate amount of communication traffic. The message complexity is on the order of the size of a quorum. Failure handling and crash recovery are also addressed in the paper.

Keywords: coterie, fault-tolerance, quorum, sequence number, total order

Full Text () Retrieve PDF document (200609_16.pdf)

Received April 21, 2004; revised August 23 & November 23, 2004; accepted December 27, 2004.
Communicated by Chu-Sing Yang.
*A preliminary version of this paper has been presented in Proceedings of the ISCA 15th International Conference on Parallel and Distributed Computer Systems, 2002, pp. 231-236