GANGOLLI@SUSHI.STANFORD.EDU (Anil R. Gangolli) (02/01/88)
Office Phone: (415) 723-3605 Message-ID: <12371081437.11.GANGOLLI@Sushi.Stanford.EDU> ReSent-date: Sun 31 Jan 88 20:00:57-PST ReSent-from: Ken Laws <LAWS@IU.AI.SRI.COM> ReSent-to: ailist ReSent-Date: Thu 4 Feb 88 22:15:27-PST ReSent-From: Ken Laws <LAWS@KL.SRI.COM> ReSent-To: post-ailist@UCBVAX.Berkeley.EDU ReSent-Message-ID: <12372216572.14.LAWS@KL.SRI.COM> 4-February-1988: Nir Shavit Toward a Non-Atomic Era: L-Exclusion as a Test Case Most of the research in concurrency control has been based on the existence of strong synchronization primitives such as test and set. Following Lamport, recent research promoting the use of weaker ``safe'' rather then ``atomic'' primitives has resulted in construction of atomic registers from safe ones, in the belief that they would be useful tools for process synchronization. It has been shown that using such atomic registers it is impossible to create strong synchronization primitives such as test and set. We therefore advocate a different approach, to skip the intermediate step of achieving atomicity, and solve problems directly from safe registers. We show how to achieve a fair solution to $\ell$-exclusion, a problem previously solved assuming a very powerful form of test and set. We do so using safe registers alone and without introducing atomicity. The solution is based on the construction of simple novel synchronization primitives that are non-atomic. *** Time and Place: 12:30pm, Th, Feb. 4, Margaret Jacks Hall (MJH), Room 352