The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.5 / (2000))
Contention Resolution in Hashing Based Shared Memory Simulations
Artur Czumaj, Friedhelm Meyer auf der Heide, Volker Stemann,
Pages. 1703-1739
Abstract
Contents 1. Introduction 2. Outline of techniques 3. Preliminaries 4. The access graph 5. A simulation with delay $O(\log \log n / \log \log \log n)$ 6. Faster simulations 7. Reduction from CRCW PRAM to EREW PRAM 8. All-but-linear routing 9. Time-processor optimal EREW PRAM simulations 10. A lower bound for the topological game
Key words PRAM, distributed memory machine, randomized shared memory simulations, hashing
Mathmatical Subject Classification 68Q05, 68Q10, 68Q25