Autonomous Decentralized Mechanisms for Generating Global Order in Large-Scale System: Using Metropolis-Hastings Algorithm and Applying to Virtual Machine Placement

摘要

Since an autonomous decentralized mechanism needs not gather state information for all subsystems, it would have high feasibility for large-scale systems. One of the challenges for leading a property of a large-scale system in desirable direction (i.e., generating global order) by using an autonomous decentralized mechanism is to connect global behavior in a large- scale system and an autonomous action rule of each subsystem. In this paper, based on a statistical mechanics methodology (i.e., Metropolis- Hastings algorithm), we propose a framework of autonomous decentralized mechanisms for generating global order in a system despite each node behaving autonomously. Then, in this paper, we apply the proposed framework to the placement control of virtual machines in data center networks. Thorough experiment, we confirm whether the proposed frame- work generates expected global order, and the performance of the proposed framework.