Optimal 1-fair alternators

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.