Optimal 1-fair alternators (Q1603376)

This paper proposes a general approach to design the optimal 1-fair alternators. An alternator is a network of concurrent processors, which can stabilize to states satisfying two conditions. First, if one processor is executing the critical step, then no neighbor of that processor executes the critical step at the same time. Second, along any concurrent execution, each processor executes the critical step infinitely often. An alternator is said to be 1-fair if the second condition is changed as: For any \(x, t1\) and t2, processor \(x\) executes two successive critical steps at steps t1 and t2, then in the period of steps [t1, t2), all other processors execute the critical step exactly once. A 1-fair alternator design is optimal if each processor can 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\times D\) meshes with odd \(D.\) For both designs, each processor executes the critical step once in every two steps.