The paper introduces a randomized version of the Kaczmarz method for solving consistent, overdetermined linear systems. The method is shown to converge with an expected exponential rate, which is independent of the number of equations in the system. This is the first solver whose rate of convergence does not depend on the number of equations, and it only needs to know a small random part of the system. The algorithm outperforms previous methods on extremely overdetermined systems and even outperforms the conjugate gradient algorithm for moderately overdetermined systems. The paper also discusses the optimality of the algorithm and provides numerical simulations to support the theoretical analysis. Additionally, it explores the application of the randomized Kaczmarz method to the reconstruction of bandlimited functions from non-uniformly spaced samples and compares its performance with the conjugate gradient algorithm. The results show that the randomized Kaczmarz method can be significantly more efficient in certain scenarios.The paper introduces a randomized version of the Kaczmarz method for solving consistent, overdetermined linear systems. The method is shown to converge with an expected exponential rate, which is independent of the number of equations in the system. This is the first solver whose rate of convergence does not depend on the number of equations, and it only needs to know a small random part of the system. The algorithm outperforms previous methods on extremely overdetermined systems and even outperforms the conjugate gradient algorithm for moderately overdetermined systems. The paper also discusses the optimality of the algorithm and provides numerical simulations to support the theoretical analysis. Additionally, it explores the application of the randomized Kaczmarz method to the reconstruction of bandlimited functions from non-uniformly spaced samples and compares its performance with the conjugate gradient algorithm. The results show that the randomized Kaczmarz method can be significantly more efficient in certain scenarios.