Retrieval of scattered information by EREW, CREW and CRCW PRAMs,
            Faith Fich, Miroslaw Kowaluk, Miroslaw Kutylowski, 
                   Krzysztof Lorys, Prabhakar Ragde,

The k-compaction problem arises when k out of n cells in  an  array  are
non-empty  and  the contents of these cells must be moved to the first k
locations in  the  array.  Parallel  algorithms  for  k-compaction  have
obvious   applications  in  processor  allocation  and  load  balancing;
k-compaction is also an important subroutine in many recently  developed
parallel  algorithms.  We  show  that  any  EREW  PRAM  that  solves the
k-compaction problem requires  Omega(sqrt(log  n))  time,  even  if  the
number  of processors is arbitrarily large and k=2. On the CREW PRAM, we
show that every n-processor algorithm for k-compaction problem  requires
Omega(loglog  n)  time, even if k=2. Finally, we show that O(log k) time
can be achieved on the ROBUST PRAM, a very weak CRCW PRAM model.