We develop a family of reformulations of an arbitrary consistent linear\nsystem into a stochastic problem. The reformulations are governed by two\nuser-defined parameters: a positive definite matrix defining a norm, and an\narbitrary discrete or continuous distribution over random matrices. Our\nreformulation has several equivalent interpretations, allowing for researchers\nfrom various communities to leverage their domain specific insights. In\nparticular, our reformulation can be equivalently seen as a stochastic\noptimization problem, stochastic linear system, stochastic fixed point problem\nand a probabilistic intersection problem. We prove sufficient, and necessary\nand sufficient conditions for the reformulation to be exact. Further, we\npropose and analyze three stochastic algorithms for solving the reformulated\nproblem---basic, parallel and accelerated methods---with global linear\nconvergence rates. The rates can be interpreted as condition numbers of a\nmatrix which depends on the system matrix and on the reformulation parameters.\nThis gives rise to a new phenomenon which we call stochastic preconditioning,\nand which refers to the problem of finding parameters (matrix and distribution)\nleading to a sufficiently small condition number. Our basic method can be\nequivalently interpreted as stochastic gradient descent, stochastic Newton\nmethod, stochastic proximal point method, stochastic fixed point method, and\nstochastic projection method, with fixed stepsize (relaxation parameter),\napplied to the reformulations.\n