Delay optimal coteries on regular symmetric networks

Coteries, introduced by Garcia-Molina and Barbara [Journal for the Association for Computing Machinery, 32 (4) (1985) 841], are an important and effective tool for enforcing mutual exclusion in distributed systems. Communication delay is an important performance measure for a coterie. Fu et al. [IEEE Transactions on Parallel and Distributed Systems, 8 (1) (1997) 59] emphasize that while calculating communication delay, the actual distances between different sites in a network must be taken into account and using this idea, obtain delay optimal coteries for trees, rings and hypercubes. Also, topology of an interconnection network plays an important role in the performance of a distributed system. For certain applications, it is desirable that the degree of each node in the interconnection network is the same. Constant Degree Four Cayley Graphs introduced by Vadapalli and Srimani [IEEE Transactions on Parallel and Distributed Systems 7(2) (1996) 26] provide an ideal topology for such applications. They are regular, have a logarithmic diameter and a node connectivity of four. In this paper, we prove that no coterie on an arbitrary network can have a delay of less than half the diameter of the network and use this result to obtain delay optimal coteries on regular symmetric networks with special reference to constant degree four Cayley interconnection-network.