Distributed computing in the presence of mobile faults

A distributed computing environment is a collection of networked computational entities communicating with each other by means of messages, in order to achieve a common goal; for example, to perform a given task, to compute the solution to a problem, to satisfy a request either from the user (i.e., outside the environment) or from other entities. Although each entity is capable of performing computations, it is the collection of all these entities that together will solve the problem or ensure that the task is performed. Such are for example distributed systems, grids of processors, data communication networks, distributed databases, transaction processing systems. More precisely, our universe is a system of n ≥ 2 entities x1, …, xn connected through dedicated communication links. The connection structure is an arbitrary undirected, connected simple graph G = (V, E). We will denote by deg (G) the maximum node degree in G, by con(G) the edge-connectivity of G, by diam(G) the diameter of G, and by m(G) the number of links of G