Efficient algorithms for dynamic allocation of distributed memory

The problem of dynamically allocating and deallocating local memory resources among multiple users in a parallel or distributed system is considered. The goal is to devise an online allocation algorithm that minimizes both the fraction of unused space due to fragmentation of the memory and the slowdown needed by the system to service user requests. The problem is solved in near-optimal fashion by devising an algorithm that allows the memory to be used to 100% of capacity despite the fragmentation and guarantees that service delays will always be within a constant factor of optimal. The algorithm is completely online (no foreknowledge of user activity is assumed) and can accommodate any sequence of insertions and deletions by the users which does not violate global memory bounds. The results have applications in the domain of parallel disk allocation