Abstract

We solve the consensus problem using a new class of broadcasts that are very appropriate to ad-hoc networking: every broadcast message is eventually ensured to be garbage-collected, thus freeing buffers in the resource-constrained mobile devices. We identify an impossibility result, the conditions in which a consensus protocol that assumes normal, message-keeping broadcasts can work using the new broadcast, and the adaptation such a protocol would require when these conditions do not hold. The cost of achieving quiescent consensus, estimated through simulations, is shown to be affordable for hosting practical dependable applications.

Keywords

Ad-hoc networking, crash-tolerance, group communication, consensus, quiescence, simulations.