The primary objective of load balancing for distributed systems is to minimize the job execution time while maximizing the resource utilization. Load balancing on decentralized systems need effective information exchange policy so that with minimum amount of communication the nodes have up to date information about other nodes in the system. Periodic, event-based and on-demand information exchange are some important policies used for the same. All these approaches involve a lot of overhead and even sometime leading toward obsolete data with the nodes if there is a delay in the updation. This work presents an adaptive threshold-based hybrid load balancing scheme with sender and receiver initiated approach (HLBWSR) using random information exchange (RIE). RIE ensures that the information is exchanged in such a way that each node in the system has up-to-date state of the other nodes with much reduced communication overhead. Further, the adaptive threshold ensures that almost an average numbers of jobs are executed by all the nodes in the system. The study of the effect of the use of RIE on sender initiated, receiver initiated and hybrid of sender and receiver initiated load balancing approach establishes the superior performance of HLBWSR among its RIE-based peers. A comparative analysis of HLBWSR, with periodic information exchange strategy, modified estimated load information scheduling algorithm and load balancing on arrival reveals its effectiveness under various test conditions. Copyright (c) 2016 John Wiley & Sons, Ltd.