Decentralized load balancers are gaining in popularity because they offer scalability, resilience, and the ability to handle high-demand workloads in distributed network systems. In practice, decentralized algorithms face such network issues as connection losses, dropped packets during data transmission, network latency. They should also account for the physical limitations of real systems. Existing works primarily consider different meta-heuristic approaches to carry out load balancing. Nevertheless, theoretically grounded algorithms that work under non-stationary conditions are of interest. In this paper, we improve the convergence rate of an existing decentralized load balancing protocol based on Local Voting Protocol (LVP) to obtain a solution that tends towards the optimal load balancing strategy over time. We propose a new Accelerated-LVP protocol and derive its parameters required to achieve the acceleration. The simulation demonstrates superiority of the proposed solution over the existing approaches in terms of convergence rate. In our experiments, we consider two scenarios: steady and bursty. In the first scenario, we observe that, on average, the proposed algorithm achieves the lowest error rate 15% faster than the nearest competitor. In the second scenario, on average, the proposed algorithm achieves an error rate that is 10% less than the nearest competitor. © 2013 IEEE.