JISE


  [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


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

  Retrieve PDF document (JISE_200605_16.pdf)