  CSMA (Carrier Sense Multiple Access), which resolves contentions over
wireless networks in a fully distributed fashion, has recently gained a lot of
attentions since it has been proved that appropriate control of CSMA parameters
guarantees optimality in terms of stability (i.e., scheduling) and system- wide
utility (i.e., scheduling and congestion control). Most CSMA-based algorithms
rely on the popular MCMC (Markov Chain Monte Carlo) technique, which enables
one to find optimal CSMA parameters through iterative loops of
`simulation-and-update'. However, such a simulation-based approach often
becomes a major cause of exponentially slow convergence, being poorly adaptive
to flow/topology changes. In this paper, we develop distributed iterative
algorithms which produce approximate solutions with convergence in polynomial
time for both stability and utility maximization problems. In particular, for
the stability problem, the proposed distributed algorithm requires, somewhat
surprisingly, only one iteration among links. Our approach is motivated by the
Bethe approximation (introduced by Yedidia, Freeman and Weiss in 2005) allowing
us to express approximate solutions via a certain non-linear system with
polynomial size. Our polynomial convergence guarantee comes from directly
solving the non-linear system in a distributed manner, rather than multiple
simulation-and-update loops in existing algorithms. We provide numerical
results to show that the algorithm produces highly accurate solutions and
converges much faster than the prior ones.
