This paper considers stochastic consensus problems over lossy wireless networks. We first propose a measurement model with a random link gain, additive noise, and Markovian lossy signal reception, which captures uncertain operational conditions of practical networks. For consensus seeking, we apply stochastic approximation and derive a Markovian mode dependent recursive algorithm. Mean square and almost sure (i.e., probability one) convergence analysis is developed via a state space decomposition approach when the coefficient matrix in the algorithm satisfies a zero row and column sum condition. Subsequently, we consider a model with arbitrary random switching and a common stochastic Lyapunov function technique is used to prove convergence. Finally, our method is applied to models with heterogeneous quantizers and packet losses, and convergence results are proved. (C) 2010 Elsevier Ltd. All rights reserved.