Title :
I-coterie: a new generalization of coterie for decentralized consensus
Author :
Cheng, Zixue ; Tajima, Naka ; Noguchi, Shoichi
Author_Institution :
Dept. of Comput. Software, Aizu Univ., Japan
Abstract :
Coterie is a kind of communication structure used in mutual exclusion, decentralized consensus, and other distributed problems. Coterie has been generalized to k-coterie for k-mutex problem. Algorithms based on the k-coteries guarantee at most k processes access a resource simultaneously, since for any k+1 quorums there is such a pair of quorums that rite intersection of the pair is not empty, (intersection property of k-coterie). However, it can´t be used for the consensus problem, because every pair processes have to exchange (directly or indirectly) their local data to reach the consensus. Therefore, we define the intersection property, in a different way from the k-coterie, called l-coterie, for the decentralized consensus problem, though it is not suitable for k-mutex problem. Intuitively, l is the times of communication for reaching a consensus for every pair of processes
Keywords :
concurrency control; distributed algorithms; communication structure; consensus; decentralized consensus; distributed problems; intersection property; k-mutex problem; mutual exclusion; Centralized control; Cities and towns; Clocks; Communication channels; Communication system control; Computer networks; Distributed computing; Process control; Protocols; Software;
Conference_Titel :
Information Networking, 1998. (ICOIN-12) Proceedings., Twelfth International Conference on
Conference_Location :
Tokyo
Print_ISBN :
0-8186-7225-0
DOI :
10.1109/ICOIN.1998.648446