A constructive proof for FLP

We present a simple elementary proof for the result of Fischer, Lynch, and Paterson (FLP) [J. ACM 32 (2) (April 1985) 374-382] that the consensus problem cannot be solved deterministically in an asynchronous system where a single process may fail by crashing. Our proof is, in contrast to the original, constructive in its crucial lemma, showing not only that a non-terminating execution does exist but also how it can be constructed. Our proof is based on the new notion of non-uniformity of a configuration. Non-uniformity is different from bivalency, which is the central notion in the original proof as well as in proofs of related results.