Byzantine Geoconsensus

We define and investigate consensus for a set of N processes embedded in the d-dimensional plane, d >= 2, which we call the Geoconsensus Problem. The processes have unique coordinates and can communicate with each other through oral messages. Faulty processes are covered by a finite-size convex fault area F. The correct processes know the fault area size but not its location. We prove that the geoconsensus is impossible if all processes may be covered by at most three areas the size of the fault area. On the constructive side, for M >= 1 fault areas F of arbitrary shape with diameter D, we present a consensus algorithm BASIC that tolerates f <= N - (2M + 1) Byzantine processes provided that there are 9M + 3 processes with pairwise distance between them greater than D. We present another consensus algorithm GENERIC that lifts this distance requirement. For square F with side l, GENERIC tolerates f <= N - 15M Byzantine processes given that all processes are covered by at least 22M axis aligned squares of the same size as F. For a circular F of diameter l, GENERIC tolerates f <= N - 57M Byzantine processes if all processes are covered by at least 85M circles. We then estimate the tolerance of GENERIC for various size combinations of fault and non-fault areas as well as d-dimensional process embeddings, where d >= 3.