Apparatus and method for non-mediated, fair, multi-type resource partitioning among processes in a fully-distributed environment

Abstract

The present invention sets forth a methodology that allows involved processes to partition among themselves a pre-defined set of multi-type resources in a way that all processes end up satisfied with the outcome of the partitioning, and no central mediation for such partitioning is required. One exemplary embodiment of the invention sets forth a method of allocating multiple type resources among a distributed set of processes that includes the steps of selecting a process from the set of processes for partitioning the resources; partitioning the resources at the selected process; sharing results of the partitioning with others of the set of processes, wherein said other processes select a partition from the partitioned resources; the selected process being able to select a partition subsequent to the other processes having selected a partition. The method also repeats the above steps until all currently involved processes are satisfied by a selected partition of available resources. Additionally, if more than one process contends for the same partition, a next-in-line process not having been allocated resources repartitions remaining resources for selection by currently unsatisfied processes.