Distributed Computing on Neighbourhood Constrained Systems

Neighbourhood Constrained Systems are resource sharing systems in which each computing entity needs all the resources it shares with the other computing entities in order to operate. Such systems are general enough for representing a large class of resource sharing systems requiring mutual exclusion resources allocation policies. Scheduling nodes for operation in such a way that no deadlock or starvation occurs represents the key control problem in such systems. Scheduling by Edge Reversal (SER) is a distributed scheduling mechanism for controlling concurrent operations amongst the elements of Neighbourhood Constrained Systems of arbitrary topologies. This scheduling mechanism is based on the manipulation of the acyclic orientations of the graph representing the system and can be implemented very easily both in a synchronous and in an asynchronous environment. SER has also been widely applied in the simulation by distributed memory machines of massively parallel models of computation and proposed as a basic tool in the design of distributed algorithms. Herein we have further investigated the application of SER in these fields.