TY - GEN
T1 - Constructing non-dominated m-group coteries for group mutual exclusion
AU - Harada, Takashi
AU - Yamashita, Masafumi
PY - 2010
Y1 - 2010
N2 - A typical group mutual exclusion algorithm among m groups makes use of anm-group coterie, which determines the performance of the algorithm. There are two main performance measures: The availability is the probability that an algorithm tolerates process crash failures, and the concurrency is the number of processes that it allows simultaneous access to the resources. Since non-dominated (ND, for short) m-group coteries (locally) maximize the availability and their degrees roughly correspond to the concurrency, methods to construct ND m-group coteries with large degrees are looked for. Nevertheless, only a few naive methods have been proposed. This paper presents three methods to construct desirable m-group coteries. The first method constructs an ND m-group coterie from a dominated one using the transversal composition. The second one constructs an ND (m - 1)-group coterie from an ND m-group coterie. The last one uses the coterie join operation to produce an ND m-group coterie from an ND coterie and another ND mgroup coterie. These methods preserve the degrees of the original m-group coteries.
AB - A typical group mutual exclusion algorithm among m groups makes use of anm-group coterie, which determines the performance of the algorithm. There are two main performance measures: The availability is the probability that an algorithm tolerates process crash failures, and the concurrency is the number of processes that it allows simultaneous access to the resources. Since non-dominated (ND, for short) m-group coteries (locally) maximize the availability and their degrees roughly correspond to the concurrency, methods to construct ND m-group coteries with large degrees are looked for. Nevertheless, only a few naive methods have been proposed. This paper presents three methods to construct desirable m-group coteries. The first method constructs an ND m-group coterie from a dominated one using the transversal composition. The second one constructs an ND (m - 1)-group coterie from an ND m-group coterie. The last one uses the coterie join operation to produce an ND m-group coterie from an ND coterie and another ND mgroup coterie. These methods preserve the degrees of the original m-group coteries.
UR - http://www.scopus.com/inward/record.url?scp=77954611727&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954611727&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:77954611727
SN - 9780889868205
T3 - Proceedings of the 9th IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2010
SP - 119
EP - 126
BT - Proceedings of the 9th IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2010
T2 - 9th IASTED International Conference on Parallel and Distributed Computing and Networks, PDCN 2010
Y2 - 16 February 2010 through 18 February 2010
ER -