I-coterie: a new generalization of coterie for decentralized consensus
Zixue Cheng, Naka Tajima, S. Noguchi · 2002
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.