johnl@iecc.cambridge.ma.us (John R. Levine) (03/21/91)
In the January TOPLAS is an article on "Wait-free synchronization" by Maurice Herlihy of DEC. Wait-free synchronization is the kind you typically do with atomic updates rather than atomic locks. It has the advantage that if one of the users of a resource goes catatonic at an inconvenient time (swapped out, for example) other users won't all stall. He defines the "consensus number" of a synchronization primitive as the maximum number of processes for which the primitive can produce a consensus. (A consensus in this case is all the processes agreeing on the value of a shared object, the value being provided by one of them. It might in practice be who currently owns a shared data structure.) Different locking primitives have very different consensus numbers. Test-and-set and its relatives only have a number of 2, i.e. they can only synchronize two processes in a wait-free way. Simultaneous update of N shared registers has number 2N-2, and compare-and-swap has an infinite consensus number. Queues and stacks with atomic insert and remove operations only have consensus number 2, unless there's an atomic peek operation in which case the consensus number is infinite. The article is quite readable and the proofs easy to follow. Some of these results have been presented before in other forms, but I haven't seen anything on this topic so clear and concises. Regards, John Levine, johnl@iecc.cambridge.ma.us, {spdcc|ima|world}!iecc!johnl -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.