Distributed channel allocation is a fundamental resource management problem in mobile cellular networks. It has a flavor of distributed mutual exclusion but is not exactly a mutual exclusion problem (because a channel may be reused in different cells). However, it is still not clear what is the relationship between the two problems.In this paper, we establish the exact relationship between the two. Specifically, we introduce the problem of relaxed mutual exclusion to model the problem of distributed channel allocation. We develop a general algorithm that guarantees relaxed mutual exclusion for a single resource, prove a necessary and sufficient condition for the information structure, and address the issues that arise in relaxed mutual exclusion, including deadlock resolution, dealing with multiple resources, and design of efficient information structure.