A scalable distributed stochastic routing algorithm (GODDeS) is developed to effectively exploit high quality paths in lossy ad-hoc wireless environments, typically with a large number of nodes. The routing problem is modeled as an optimal control problem for a decentralized Markov decision process via a probabilistic local broadcast model, with links characterized by locally known or estimated drop probabilities that either remain constant on average or change slowly. Equivalence of this optimization problem to that of performance maximization of probabilistic automata allows us to effectively apply the theory of quantitative measures of probabilistic regular languages, and design a distributed, highly efficient, scalable, and stationary routing policy that very nearly minimizes source-to-sink drop probabilities across the network. Theoretical results provide rigorous guarantees on global performance, showing that the algorithm achieves near-global optimality in polynomial time, and worst case asymptotic convergence time is shown to scale linearly with network size. Furthermore, the theoretical results establish that it is possible to trade off deviation from global optimality against convergence time. It is also argued that GODDeS is significantly congestion-aware and exploits multipath routes optimally. Theoretical development is supported by detailed network simulations.