| Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] | [ 16] | [ 17] | [ 18] |
¡@
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.
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