Wait-free linearizable queue implementations.
Published: 2004
Language: eng
Number of pages: 101
Description: We study wait-free linearizable Queue implementations in asynchronous shared-memory systems from other consensus number 2 types, such as Fetch&Add and Swap. It was known that such implementations exist when at most two processes perform dequeue operations. We provide a new implementation, when only one process performs enqueue operations and any number of processes perform dequeue operations. We introduce the BH&AR type, which has two important characteristics: only one BH&AR object simulates countably infinitely many Fetch&Add objects and Registers; and we can exactly quantify the flow of information in a system providing only one BH&AR object. The latter might prove useful in developing an adversarial argument showing that there is no implementation of a Queue from Fetch&Add objects when three processes can fully access the Queue. The B-History and Basic-Id-Queue types are restricted versions of the BH&AR and Queue types, respectively. We show that implementing a Queue from one BH&AR object is equivalent to implementing a Basic-Id-Queue from one B-History object. Preliminary results show that this is impossible for two restricted classes of implementations.
Notes: Adviser:  Faith Fich.

Thesis (M.Sc.)--University of Toronto, 2004.

Electronic version licensed for access by U. of T. users.

Source: Masters Abstracts International, Volume: 42-06, page: 2227.

MICR copy on microfiche (2 microfiches).