by Natalia Amelina and Yuming Jiang
During the process of resource allocation in a computer system, it is vital that consensus is attained, ie: every node in the system must reach the same state with respect to certain chosen measures, such as having the same amount of steady-state remaining workload. Despite its importance, consensus is rarely considered in studies that model and evaluate resource allocation problems in computer and communication systems. Our research focuses on resource allocation from a consensus angle: we investigate the consensus properties of a distributed control strategy and apply this control strategy to various computer and communication systems.
{jcomments on}Consensus, which has long been considered a crucial issue in distributed systems [1], requires that there are control strategies or protocols in place that can drive the states of all nodes in a system to the same steady-state values. Many computer and communication systems, such as distributed computing systems, sensor networks, and wireless mesh networks, also require distributed control and are run under a stochastic environment. To achieve optimal resource allocation in these systems, a consensus requirement is often implied. For example, a fundamental problem in distributed computing is how to distribute load to different servers. This problem is essentially one of consensus, hence consensus control strategies can represent a solution.
Specifically, in a distributed computing system, the load must be distributed among different computing nodes to shorten task completion time; in a sensor network, the battery usage must be balanced among sensor nodes to maximize the lifetime of the network; in a wireless mesh network, nodes need to be scheduled properly in using the wireless channel so that the overall network capacity is maximized. To address these needs, various resource allocation approaches have been proposed and evaluated. However, the literature has largely focused on the classic performance perspectives of the proposed approaches, such as throughput, delay, capacity, etc., and the consensus aspect is often overlooked, which can unfortunately sometimes lead to new issues [2].
Our research, which investigates computer and communication systems from a consensus perspective, assumes a more general and realistic stochastic environment. We show that many of the problems in the considered systems can be solved by achieving consensus among nodes. For example, in the load-balancing case, the completion time can be minimized by distributing the load in such a way that at any time, every node is given the same load weighted against its computing capability, ie when consensus in achieved in weighted load among nodes.
Specifically, we study and apply a control strategy that only requires local information and information exchange among neighbouring nodes, to various distributed computer and communication systems including distributed computing systems, sensor networks, and wireless mesh networks. We prove consensus properties of this control strategy for these systems, such as whether the strategy will lead to consensus, and how quickly consensus can be reached by what means. In addition, we investigate how well the system performs under this control strategy. A summary of early results can be found in [3]. Specifically, analytic conditions for achieving approximate consensus in a stochastic network with noise, delays and switched topology have been obtained. The results have been applied to a load balancing problem in the network. Simulation results show that the performance of an adaptive strategy, which has proven consensus properties, is significantly better than that of the strategy with no adaptation.
References:
[1] J. Turek, D. Shasha: “The Many Faces of Consensus in Distributed Systems”, IEEE Computer, 25(6): 8-17, June 1992
[2] J. Cho, J-Y. Le Boudec, Y. Jiang: “On the Asymptotic Validity of the Decoupling Assumption for Analyzing 802.11 MAC Protocol”, IEEE Transactions on Information Theory, 58(11): 6879-6893, 2012
[3] N. Amelina et al: “Approximate Consensus Multi-Agent Control Under Stochastic Environment with Application to Load Balancing”, eprint arXiv:1306.3378, June 2013 (http://arxiv.org/abs/1306.3378).
Please contact:
Natalia Amelina (ERCIM Fellow)
Department of Telematics, NTNU, Norway
E-mail:
