R.P. Hopkins
University of Newcastle upon Tyne. 1993
We deal with the "votability" conditions which need to be satisfied by a component of a concurrent system in order that it be possible to apply the fault-tolerance technique of voting on multiple instances ("versions" or "replicas") of the component. If one of the usual models of concurrent processes is used (such as CCS), then there are votability restrictions, particularly a requirement for non-blocking input, that make this technique inapplicable to systems that use synchronous communication. We show that by the use of an extended process model (related to Milner's SCCS), the restrictions can be weakened to just lack of internal non-determinism, allowing multi-instance fault-tolerance to be applied to a reasonably wide class of synchronously-communicating systems, which is the largest general class for which it is possible for any process model. We then consider votability requirements on components of asynchronously-communicating systems and the extent to which the extended process model is relevant to that context. Our interest here is primarily theoretical, the existence and consequences of the extended process model; rather than the practical implementability of the model, although that is addressed in related work.