The first part of the paper shows that C_f\mathcal{C}_f is made up of a hierarchy of classes of conditions, C^[d]_f\mathcal{C}^{[d]}_f where d is a parameter (called degree of the condition), starting with d = min(n-f,\allowbreak f)d = \min(n-f,\allowbreak f) and ending with d = 0, where C^[0]_f = C_f\mathcal{C}^{[0]}_f = \mathcal{C}_f . We prove that each one is strictly contained in the previous one: C^[d]_f Ì C^[d-1]_f\mathcal{C}^{[d]}_f\subset\mathcal{C}^{[d-1]}_f . Various properties of the hierarchy are also derived. It is shown that a class can be characterized in two equivalent but complementary ways: one is convenient for designing protocols while the other is for analyzing the class properties. The paper also defines a linear family of conditions that can be used to derive many specific conditions. In particular, for each d, two natural conditions are presented.

The second part of the paper is devoted to the design of efficient condition-based protocols. A generic condition-based protocol is presented. This protocol can be instantiated with any condition C, C Î C^[d]_fC\in\mathcal{C}^{[d]}_f , and requires at most (2n + 1) élog₂(é(f-d)/2ù + 1)(2n + 1) \lceil{\log_2(\lceil{(f-d)/2\rceil} + 1)} shared memory read/write operations per process in the synchronization part of the protocol. Thus, the value (f-d) represents the C^[d]_f\mathcal{C}^{[d]}_f . An improvement of the protocol for the conditions in C^[0]_f\mathcal{C}^{[0]}_f is also presented.