Agreement algorithms allow individual agents in a population to estimate a global quantity by sharing information. A common example is computing the global mean of a sensor measurement from each agent. We present a practical agreement algorithm, input-based consensus (IBC), that produces bounded error and recovery in the face of significant communications failures in a stochastic distributed system. We compare our algorithm to linear average consensus (LAC), which produces an exact result under ideal conditions, but is not robust to message loss. For both algorithms, we measure performance with respect to a varying percentage of dropped messages. The algorithms are examined analytically, simulated using the Stochastic Simulation Algorithm, and demonstrated experimentally on a testbed of 20 robots. In all cases, the IBC algorithm produced reasonable values, even when tested with up to 90% message loss.
Paper located here.