Transversal Merge Operation and Nondominated Grid Coteries

摘要

Grid coteries are attractive both in message and space complexities, but they are not non-dominated (ND) unfortunately. This paper introduces the transversal merge operation for constructing an ND coterie from a dominated one, and applies it to grid coteries to make them ND. The constructed 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.