This paper presents a novel decentralized algorithm for adaptive task allocation and load balancing in multi-agent systems operating under heterogeneous and evolving workloads. The proposed Cluster-Aware Local Voting Protocol (CaLVP) integrates local voting mechanisms with cluster-specific parameter tracking to enable context-sensitive scheduling decisions. Each agent independently adjusts its routing strategy based on performance feedback and statistical characteristics of task clusters, allowing the system to dynamically adapt to real-time load conditions. The algorithm builds on the principles of stochastic approximation and consensus-based coordination, offering theoretical robustness under noise and minimal communication assumptions. Experimental results on a real-world call center dataset demonstrate the effective-ness of the approach in minimizing agent workload imbalance and average task waiting time. The method is scalable, robust to dynamic task streams, and suitable for applications requiring fine-grained, decentralized control. © © 2025 The Authors.