Better Sooner Rather Than Later

09/20/2023
by   Anaïs Durand, et al.
0

This article unifies and generalizes fundamental results related to n-process asynchronous crash-prone distributed computing. More precisely, it proves that for every 0≤ k ≤ n, assuming that process failures occur only before the number of participating processes bypasses a predefined threshold that equals n-k (a participating process is a process that has executed at least one statement of its code), an asynchronous algorithm exists that solves consensus for n processes in the presence of f crash failures if and only if f ≤ k. In a very simple and interesting way, the "extreme" case k=0 boils down to the celebrated FLP impossibility result (1985, 1987). Moreover, the second extreme case, namely k=n, captures the celebrated mutual exclusion result by E.W. Dijkstra (1965) that states that mutual exclusion can be solved for n processes in an asynchronous read/write shared memory system where any number of processes may crash (but only) before starting to participate in the algorithm (that is, participation is not required, but once a process starts participating it may not fail). More generally, the possibility/impossibility stated above demonstrates that more failures can be tolerated when they occur earlier in the computation (hence the title).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset