Distributed Algorithms for Resource Allocation to process groups and Their Applications

分布式资源分配问题是分布式系统中一个众所周知的基本问题。已经开发出许多避免僵局和饥饿的解决方案。然而，随着计算机网络的发展，网络环境中的分布式协作群体活动越来越多，使得多个群体可能在网络环境中争夺某些资源，从而可能出现群体间的死锁和群体的饥饿。由于以往的分配模型主要用于表示进程间的资源竞争，不能清楚地反映进程组之间的资源竞争。此外，虽然已有的分布式资源分配问题的解决方案可以避免死锁和饥饿，但它们不能解决组之间的死锁和组内的饥饿问题。我们提出了一种新的问题--进程组的资源分配问题，它是对传统资源分配问题的扩展，并对该问题的分布式解决方案进行了研究。在本研究中，对群体间的资源竞争进行了公式化，并提出了几种解决问题的资源分配方法。此外，为了将该问题应用到更广泛的领域，提出了几种新的任务，并且每种解决方案都被证明是成功的；为了将我们的解决方案应用到实际应用中，我们还研究了如何分配有能力的资源，以及如何利用局部多数小圈子来构造更有效的解。

The distributed resource allocation problem is a well-known fundamental problem in distributed systems. Many solutions that avoid deadlock and starvation have been developed. With the progress of computer networks, however, distributed cooperative group activities in a network environment have been increasing, so that several groups may compete for some resources in the network environment and "deadlock among groups" and "starvation of a group" may happen. Since previous allocation models are mainly for representation of competition for resources among processes, they cannot reflect clearly the competition for resources among groups of processes. Moreover, though the previous solutions to the distributed resource allocation problem can avoid the deadlock and starvation, they cannot deal with the deadlock among groups and starvation of a group.We posed a new problems called "resource allocation to the process groups", which as an extension from the traditional resource allocation problem, and we focus our research on the distributed solutions to this issue. In this research, the competition for resources among groups is formulized, and we also proposed several resource allocation methods to solve the problems. Furthermore, in order to apply this problem into more wildly fields, several new tasks that extended from it are proposed, and every resolution is proved successful.In order to apply our solution to real applications we also researched how to allocate a resource with capacity, and how to use local majority coterie to construct more efficient solutions.