  In this paper, we study fault-tolerant distributed consensus in wireless
systems. In more detail, we produce two new randomized algorithms that solve
this problem in the abstract MAC layer model, which captures the basic
interface and communication guarantees provided by most wireless MAC layers.
Our algorithms work for any number of failures, require no advance knowledge of
the network participants or network size, and guarantee termination with high
probability after a number of broadcasts that are polynomial in the network
size. Our first algorithm satisfies the standard agreement property, while our
second trades a faster termination guarantee in exchange for a looser agreement
property in which most nodes agree on the same value. These are the first known
fault-tolerant consensus algorithms for this model. In addition to our main
upper bound results, we explore the gap between the abstract MAC layer and the
standard asynchronous message passing model by proving fault-tolerant consensus
is impossible in the latter in the absence of information regarding the network
participants, even if we assume no faults, allow randomized solutions, and
provide the algorithm a constant-factor approximation of the network size.
