Recently, it has been shown that CSMA-type random access algorithms can achieve the maximum throughput in
wireless ad hoc networks. Central to these results is a distributed randomized algorithm which selects
schedules according a product-form distribution. The product-form distribution is achieved by considering a
continuous-time Markov model of an idealized CSMA protocol under which collisions cannot occur. In this
paper, we present an algorithm which achieves the same product-form distribution in a discrete-time setting
where collision of data packets is avoided through the exchange of control messages (however, the control
messages are allowed to collide as in the 802.11 suite of protocols). In our discrete-time model, each time
slot consists of a few control mini-slots followed by a data slot. We show that two control mini-slots are
sufficient for our distributed scheduling algorithm to realize the same steady-state distribution as in the
continuous-time case. Thus, the overhead can be as low as twice the ratio of a control mini-slot to a data
slot.