Title :
Consensus-based estimation protocol for decentralized dynamic load balancing over partially connected networks
Author :
Wang, Zhuoyao ; Hayat, Majeed M. ; Rahnamay-Naeini, Mahshid ; Mostofi, Yasamin ; Pezoa, Jorge E.
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of New Mexico, Albuquerque, NM, USA
Abstract :
A novel consensus-based protocol is developed for estimating the load information at nodes in a distributed computing system operating over a partially connected communication network. The challenge in such estimation process arises from the existence of tangible delays in the exchange of information, and the fact that loads are dynamic since nodes continue to execute their loads while the estimation process is ongoing. The protocol utilizes the concept of trust weight that each node has about any other node, based on the number of hops in between, to periodically form an updated estimate of the loads of the other nodes. The probability of consensus at any given time as well as the probability density function of the time to the first consensus are analytically characterized and used to determine the best instant for executing a dynamic load balancing (DLB) action. Detailed Monte-Carlo simulations of the average completion time of a workload by a distributed system under different system configurations are presented and discussed. The results suggest a range of time for executing the DLB over which satisfactory average completion time is achieved. The results also provide insight on the effects of network connectivity and the frequency of communication on the DLB performance.
Keywords :
Monte Carlo methods; distributed processing; probability; protocols; resource allocation; trusted computing; DLB performance; Monte Carlo simulation; consensus based estimation protocol; consensus probability; decentralized dynamic load balancing; distributed computing system; information exchange; load information estimation; network connectivity; partially connected networks; probability density function; trust weight; Delay; Estimation error; Load management; Probability density function; Protocols; Vectors; consensus-based estimation; distributed computing; load balancing; partially connected network; trust-weight;
Conference_Titel :
Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on
Conference_Location :
Orlando, FL
Print_ISBN :
978-1-61284-800-6
Electronic_ISBN :
0743-1546
DOI :
10.1109/CDC.2011.6161333