An O( 1an)-worst-case-time solution to the granularity problem

In this paper we deal with the granularity problem, that is, the problem of implementing a shared memory in a distributed system where n processors are connected to n memory modules through a complete network (Module Parallel Computer). We present a memory organization scheme where m=O(n^2) variables, each replicated into a 2c \u2014 1 copies (for constant c), are evenly distributed among the n modules, so that a suitable access protocol allows any set of at most n distinct read/write operations to be performed by the processors in O(sqrt(n)) parallel steps in the worst case. The well known strategy based on multiple copies is needed to avoid the worst-case O(n)-time, since only a majority of the copies of each variable need be accessed for any operation. The memory organization scheme can be extended to deal with m=O(n^3) variables attaining an O(n^(2/3))-time complexity in the worst case