A delay optimal coterie on the k-dimensional folded Petersen graph
Coteries are an effective tool for enforcing mutual exclusion in distributed systems. Communication delay is an important metric to measure the performance of a coterie. The topology of the interconnection network in a distributed system also has an impact on its performance. The k-dimensional folded Petersen graph, a graph with 10k nodes and diameter 2k, qualifies as a good network topology for large distributed systems. In this paper, we present a delay optimal coterie on the k-dimensional folded Petersen graph, FPk. For any positive integer k, the coterie has message complexity 4k and delay k. Moreover, this coterie is not vote-assignable.
coterie mutual exclusion communication delay message complexity