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.
- A self-stabilizing algorithm for coloring planar graphs
- scientific article; zbMATH DE number 1696677 (Why is no real title available?)
- Multitolerant barrier synchronization
- Self-stabilizing systems in spite of distributed control
- Stabilization-preserving atomicity refinement
- Stabilizing phase-clocks
- The alternator
This page was built for publication: Optimal 1-fair alternators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1603376)
