Abstract
The need for exclusive accesses to shared resources, like memory and communications facilities, requires the synchronization of asynchronous processes, which degrades the performance of a distributed system. A Markov chain, which models a set of cyclic processes, can be used to evaluate the performance degradation. This is demonstrated for systems with a single shared resource (e.g. a communications bus), and ring-structured systems (e.g., as defined by the scenario of the Dining Philosophers [4,6]) for which a distributed, a centralized, and a "fair" synchronization algorithm are considered. Performance data for both system types are plotted and the respective merits of the three algorithms are discussed. The state space of the Markov chain equals that of the status variables used to verify synchronization algorithms, and, thus, provides a common framework for evaluating correctness and performance.