TOPLAS: Wait-free synchronization

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


--

Return to the comp.compilers page.
Search the comp.compilers archives again.