Quote: concurrent data is wait-free if any process can complete in a finite number of steps; e.g., compare&swap but not test&set; reduce to consensus

Quotation Skeleton

A wait-free implementation of a concurrent data object … steps, regardless of the execution speeds of the … we introduce a simple and general technique, based … implementation of X by Y." … Moreover, classical synchronization primitives such as test&set and … [atomic] read and write, are also computationally weak, as are the … we show that there do exist simple universal … [p. 135] Theorem 5.A compare&swap register has infinite consensus … [p. 137 so does a FIFO queue with a non-destructive peek (top) operation] … [p. 138 so does an array of registers with move or memory-to-memory swap] … [p. 148] Finally, little is known about practical implementation …   Google-1   Google-2

Copyright clearance needed for quotation.

Related Topics

Topic: critical regions (58 items)
Topic: data flow languages (33 items)
Topic: concurrent operations (22 items)
Topic: synchronized processing (35 items)