QRQW: Accounting for Concurrency in PRAMs and Ascynchronous PRAMs

We introduce the queue-read, queue-write (QRQW) PRAM and Asynchronous PRAM models, which permit concurrent reading and writing, but at a cost proportional to the number of readers/writers to a memory location in a given step. These models more accurately reflect the cost of such steps on machines with simple, non-combining interconnection networks. In such machines, multiple read/write requests to a location are queued and then serviced one-at-a-time. We present a number of results characterizing the power of the QRQW models with respect of existing PRAM models, describing algorithms for the fundamental problems of computing the OR, leader election, compaction, integer sorting, and CRCW simulation. These algorithms improve upon the best known CREW and the EREW algorithms for these problems, and reveal important technical issues that arise in designing algorithms for the QRQW models. Some of the algorithms presented are quite involved and use several novel ideas and techniques, that are interesting on their own.