Process coordination with fetch-and-increment

The fetch-and-add (F&A) operation has been used effectively in a number of process coordination algorithms. In this paper we assess the power of fetch-and-increment (F&I) and fetch-anddecrement (F&D), which weview asrestricted forms of F&A in which the only addends permitted are ±1. F&A-based algorithms that use only unit addends are thus trivially expressed with just F&I and F&D. Our primary contributions are new F&I/F&D algorithms for readers/writers coordination including a proof of its correctness and algorithms for barrier synchronization for dynamically-sized groups. We also restructure anexisting F&A-based algorithm for queueswith-multiplicity to obtain an algorithm using just F&I and F&D. When executed on certain hardware arc hitectures, most of these algorithms are free ofserial bottlenecks. We also discuss a general technique for implementing F&A using F&I/F&D at a cost logarithmic in the number of processors