Transversal Merge Operation and Nondominated Grid Coteries

T. Harada and M. Yamashita (Japan)

Keywords

coteries, distributed systems, grid structure, mutual exclusion algorithm, nondominatedness, synchronization problem, transversals

Abstract

Grid coteries are attractive both in message and space com plexities, but they are not non-dominated (ND) unfortu nately. This paper introduces the transversal merge opera tion for constructing an ND coterie from a dominated one, and applies it to grid coteries to make them ND. The con structed ND grid coteries sill preserve favorite features that the original grid coteries have. To demonstrate this fact, we evaluate their quorum sizes and design a mutual exclusion algorithm based on the ND grid coteries, which allows a process to construct a quorum on the fly.

Important Links:



Go Back