THE QUEUE-READ QUEUE-WRITE ASYNCHRONOUS PRAM MODEL

This paper presents results for the queue-read, queue-write asynchrono us parallel random access machine (QRQW ASYNCHRONOUS PRAM) model, whic h is the asynchronous variant of the QRQW PRAM model. The QRQW PRAM fa mily of models, which was introduced earlier by the authors, permit co ncurrent reading and writing to shared memory locations, but each memo ry location is viewed as having a queue which can service at most one request at a time. In the basic QRQW PRAM model each processor execute s a series of reads to shared memory locations, a series of local comp utation steps, and a series of writes to shared memory locations, and then synchronizes with all other processors; thus this can be viewed a s a bulk-synchronous model. In contrast, in the QRQW ASYNCHRONOUS PRAM model discussed in this paper, there is no imposed bulk-synchronizati on between processors, and each processor proceeds at its own pace. Th us, the QRQW ASYNCHRONOUS PRAM serves as a better model for designing and analyzing truly asynchronous parallel algorithms than the original QRQW PRAM. In this paper we elaborate on the QRQW ASYNCHRONOUS PRAM m odel, and we demonstrate the power of asynchrony over bulk-synchrony b y presenting a work and time optimal deterministic algorithm on the QR QW ASYNCHRONOUS PRAM for the leader election problem and a simple rand omized work and time optimal algorithm on the QRQW ASYNCHRONOUS PRAM f or sorting. in contrast, no tight bounds are known on the QRQW PRAM fo r either deterministic or randomized parallel algorithms for leader el ection and the only work and time optimal algorithms for sorting known on the QRQW PRAM are those inherited from the EREW PRAM, which are co nsiderably more complicated. Our sorting algorithm is an asynchronous version of an earlier sorting algorithm we developed for the QRQW PRAM , for which we use an interesting analysis to bound the running time t o be O(log n). We also present a randomized algorithm to simulate one step of a CRCW PRAM on a QRQW ASYNCHRONOUS PRAM in sublogarithmic time if the maximum contention in the step is relatively small. (C) 1998-E lsevier Science B.V. All rights reserved.