Queues in Cloud Computing

云计算是一种现代范式，其中计算任务在共存于大型分布式计算机网络(称为云)的服务器子集上执行。这些云中的计算机数量正在迅速增加，目前已超过数十万台。无论从商业角度还是从科学角度来看，普遍提供大型并行计算设施都是可取的。具体地说，如今的研究人员不需要拥有一台昂贵的超级计算机来研究复杂的系统，因为他们可以一次访问云几个小时、几周或几个月，远远低于维护一个小得多的设施所需的成本。这项研究将为这些大规模系统的分析和有效控制提供新的易于处理的数学方法。目前用于大型计算作业的分布式处理的许多系统的复杂性使得很难理解服务器信息对调度协议设计的影响。通过该奖项完成的研究将从分析服务器网络的数学易处理模型开始，在该网络中，作业在到达时被分成多个部分，然后在随机选择的服务器上分配/排队。该模型的主要特点是作业的所有部分都必须以同步的方式接受服务。该模型与第二个模型相结合，即作业等待所需数量的服务器可用，将为设计和量化实际调度策略的收益提供基准。通过指出这两个模型构成了没有服务器信息和拥有完整、集中的信息的极端情况，这项工作基本上将为这些知识提供价格，这将在未来的云系统设计中发挥重要作用。

Cloud computing is a modern paradigm where computing tasks are performed on a subset of servers which coexist in a large distributed network of computers, called clouds. The number of computers in these clouds is rapidly increasing, surpassing hundreds of thousands today. Making large and parallel computing facilities generically available is desirable both from the business as well as the scientific perspective. Specifically, researchers today do not need to own an expensive supercomputer for studying complex systems, since they can tap into the cloud for hours, weeks or months at a time, well below the cost that they would need to pay to maintain a much smaller facility. This research will provide new tractable mathematical techniques for the analysis and efficient control of these large-scale systems.The complexity of many of the systems used today for the distributed processing of large computing jobs makes it difficult to understand the impact of server information on designing scheduling protocols. The research done through this award will start by analyzing a mathematically tractable model for a network of servers where jobs are, upon arrival, split into a number of pieces, which are then assigned/queued at randomly chosen servers. The main characteristic of the model is that all pieces of a job must receive service in a synchronized fashion. This model, combined with a second model where jobs wait for the required number of servers to become available, will provide a benchmark for designing as well as quantifying the gains of practical scheduling policies. By noting that the two models constitute the extreme cases of having no server information versus having full, centralized information, this work will essentially provide a price for this knowledge, which will play an important role in designing future cloud systems.