In a distributed computing system, computing nodes share a number of different resources. Such a resource could be, for example, a database or other data structure that requires exclusive access in order to avoid interference among the operations of different computing nodes. Distributed mutual exclusion is used to control computing nodes in such a way that only one node will access the shared resource at a given time, and this exclusion control is recognized to be one of the most fundamental and important problems of distributed computing. The distributed k-mutual exclusion problem is a generalization of the classic mutual exclusion problem, and is specifically the problem of guaranteeing that no more than k computing nodes will have access to shared resources, in other words, enter the critical sections simultaneously. The solution to this problem is useful for a number of different applications in a distributed environment. For example, the solution can be used to restrict the number of broadcasting nodes for congestion control. It can also be useful in replicated databases that allow bounded ignorance. In such databases, simultaneous updates are allowed in order to increase concurrency. The use of a k-coterie is known as a robust approach for solving the distributed k-mutual exclusion problem. A k-coterie is a special set of node groups, and each node group in a k-coterie is called a quorum. For any k+1 quorums in a k-coterie, there is always a node that is shared by at least two of the k+1 quorums. In the k-mutual exclusion mechanism based on a k-coterie, each node has to gain permission from all members of a quorum before entering the critical section. This technique guarantees that no more than k nodes enter the critical sections at the same time. In the presence of node and link failures, the k-mutual exclusion mechanisms based on a k-coterie provide desirable fault-tolerance capability. For example, as long as all nodes of a quorum are connected via operational paths when a failure occurs, there still exists a node that can enter the critical section by obtaining permission from the quorum. The availability of the k-mutual exclusion mechanism clearly depends on the k-coterie adopted. In order to achieve highly reliable k-mutual exclusion, therefore, construction of k-coteries that provide high availability is indispensable. In addition, the ability to evaluate availability of k-coteries is also essential for choosing an appropriate k-coterie out of various different k-coteries. In this dissertation, we address these issues of design and evaluation of k-coteries. To resolve the evaluation issue, we propose two methods for evaluating the availability of a given k-coterie. Most of the previous research on evaluating k-coteries has not taken network topology and link failures into consideration. Unlike the existing methods, our proposed methods can handle networks with arbitrary topology and unreliable nodes and links. The first evaluation method is based on a new graph-theoretic notion, which we refer to as r-Minimal Quorum Spanning Forests (r-MQSFs), while the second evaluation method is based on Binary Decision Diagrams. The superiority of both proposed methods over an exhaustive state enumeration is shown through the results of an experiment conducted for various network structures. Using the proposed evaluation method also helps us obtain some properties of the availability of k-coteries in general topology networks. To resolve the design issue, we address two problems: design of nondominated k-coteries and design of optimal k-coteries. Nondominated k-coteries are considered as a class of k-coteries most resilient to failures and are definitely superior to dominated k-coteries in terms of availability. However, previous constructions