Title: Conditions for Strong Synchronization in Concurrent Algorithms
Speaker: Dr. Maged Michael, IBM Thomas J. Watson Research Center
Concurrent algorithm designers often find it difficult to avoid expensive synchronization, in particular store-load ordering and atomic operations. This talk presents conditions under which, it is impossible to design algorithms that avoid such strong synchronization patterns. The identified conditions impact operations on many common data types and problems, such as FIFO queues, LIFO stacks, counters, sets, work queues, mutual exclusion. The identification of conditions for strong synchronization open the door for tradeoffs between synchronization overheads and the strength of specification of abstract data types. Strong synchronization may be avoided by specification relaxations such as limiting concurrency, limiting the API, and relaxing determinism.