A technique for decomposing algorithms which use a single shared variable

摘要

A general theorem is proved which shows how a system of contending asynchronous processes with a special auxiliary supervisor process can be simulated by a system of contending processes without such a supervisor, with only a small increase in the shared space needed for communication. Two applications are presented, synchronization algorithms with different fairness properties requiring N + c and [N/2] + c (c a constant) shared values to synchronize N processes, respectively.