  Consider a wireless network of n nodes represented by a graph G=(V, E) where
an edge (i,j) models the fact that transmissions of i and j interfere with each
other, i.e. simultaneous transmissions of i and j become unsuccessful. Hence it
is required that at each time instance a set of non-interfering nodes
(corresponding to an independent set in G) access the wireless medium. To
utilize wireless resources efficiently, it is required to arbitrate the access
of medium among interfering nodes properly. Moreover, to be of practical use,
such a mechanism is required to be totally distributed as well as simple. As
the main result of this paper, we provide such a medium access algorithm. It is
randomized, totally distributed and simple: each node attempts to access medium
at each time with probability that is a function of its local information. We
establish efficiency of the algorithm by showing that the corresponding network
Markov chain is positive recurrent as long as the demand imposed on the network
can be supported by the wireless network (using any algorithm). In that sense,
the proposed algorithm is optimal in terms of utilizing wireless resources. The
algorithm is oblivious to the network graph structure, in contrast with the
so-called `polynomial back-off' algorithm by Hastad-Leighton-Rogoff (STOC '87,
SICOMP '96) that is established to be optimal for the complete graph and
bipartite graphs (by Goldberg-MacKenzie (SODA '96, JCSS '99)).
