Enabling local actions by global consensus

Abstract

Presented is an algorithm for determining whether total global consensus exists for a process to execute a local action that has interaction constraints. The algorithm assumes a virtual ring of processes each of which possesses a token. Multiple processes can simultaneously attempt and succeed in performing actions that do not constrain each other, thus exploiting the available parallelism. The algorithm can be tailored to handle any situation in which the action of one process is constrained by actions of other processes and where total global consensus is required. The use of execution time estimates and information concerning the attempts and activities of other processes reduces the number of failed attempts and hence unnecessary communication.