This paper proposes a general approach to design the optimal 1-fair alterna
tors. An alternator is a network of concurrent processors, which can stabil
ize to states satisfying two conditions. First, if one processor is executi
ng the critical step, then no neighbor of that processor executes the criti
cal step at the same time. Second, along any concurrent execution, each pro
cessor executes the critical step infinitely often. An alternator is said t
o be 1-fair if the second condition is changed as: For any x, t1 and t2, pr
ocessor x executes two successive critical steps at steps t1 and t2, then i
n the period of steps [tl, t2), all other processors execute the critical s
tep exactly once. A 1-fair alternator design is optimal if each processor c
an execute the critical step once in every fewest possible steps. Adopting
this approach, we have demonstrated two optimal 1-fair alternator designs:
one for hypercubes and the other for D x D meshes with odd D. For both desi
gns, each processor executes the critical step once in every two steps. (C)
2001 Elsevier Science B.V. All rights reserved.