A high performance critical section protocol for distributed systems

Parallel and distributed processing is a system level approach used to develop high performance and fault tolerant systems. For example, an airborne or a space platform computational system consists of several subsystems (possibly replicated for speed and reliability) and sometimes optimized to perform specific tasks such as flight control, communications, information display, or telemetry. The computation in a distributed system is modeled as a collaboration of interacting processes. When processes share information in a read/write fashion a problem may arise. Although each individual process performs its computation correctly, the result of the computation of the distributed system may be incorrect because of an improper sharing of the information. In this paper we present a new high performance critical section protocol designed for distributed systems with general topologies where the communication network is implemented as point-to-point physical links in contrast to a shared access bus. Distributed systems can be modeled by a graph G(V, E) where V denotes the set of processors (nodes) and E the set of communication links (edges). n denotes the number of processors, D(G) the diameter of G, and D(T) the diameter of the spanning tree. An important measure of the protocol performance is the network traffic caused by a single access to the critical section. Another important measure of performance is the time required to access the critical section-in the absence of other requests-the cs-access time. The proposed protocol has a better network traffic performance and (depending on the topology) a better or equal cs-access time performance than previously published fully distributed protocols. The protocol bounds the clock and message sizes in well designed systems using a distributed predictive “clock squashing” mechanism. Other protocols, even for well designed systems, have unbounded clocks and hence unbounded messages sizes