Cliques in Hypergraphs and Mutual Exclusion using Tokens

Abstract

Token-passing algorithms are a well-known way of solving distributed mutual exclusion problems in computer networks. A simple abstraction of the concept of tokens allows the use of elementary constructions in general hypergraphs to show that certain sets of tokens are minimal. This suggests other problems about hypergraphs worthy of exploration. As an application, we introduce a new mutual exclusion problem, the $ExcludedTaxpayerProblem$, which requires exponentially many tokens even though it can be solved in linear time by other methods.