Dartmouth Events

Jake Leichtling Senior Honors Thesis Presentation

Constant RMR Transformations to Augment Reader-WriterSynchronization Algorithms with Upgrade and Downgrade Support

Wednesday, May 28, 2014
114 Sudikoff
Intended Audience(s): Public
Categories: Lectures & Seminars

Consider a distributed system in which multiple processes are computing concurrently and communicating with each other using atomic shared variables. These processes are asynchronous, meaning that the rate at which each process executes its code is variable and unrelated to the rate of execution of other processes. In such a system, there are frequently resources that have constraints on how they are accessed. For example, a printer must only be used by one process at a time. This type of resource gave rise to the mutual exclusion problem, which, first introduced by Dijkstra (1965), is a well-studied and fundamental problem in the realm of distributed systems. The problem seeks a lock that protects some critical section of code such that only one process has access to it at a given time.

The reader-writer problem is a variation of the mutual exclusion problem that protects the critical section for two classes of processes: readers and writers. Multiple readers can have access to the critical section simultaneously, but only one writer can have access to the critical section to the exclusion of all other processes. The difficulties in solving the reader-writer problem lie not only in developing a correct and efficient algorithm, but also in rigorously formulating the desirable properties for such an algorithm to have. Bhatt and Jayanti (2010) accomplished both of these tasks for several priority variants of the standard reader-writer problem.

Diamond and Jayanti (2011) subsequently formulated the notions of upgrading and downgrading, in which a reader can attempt to become a writer or a writer can become a reader, respectively, while in the critical section of the lock. They presented an algorithm for a reader-writer lock that supports upgrade/downgrade while giving readers priority over writers in accessing the critical section (the reader-priority variant). In this paper, we formulate the desirable properties of a reader-writer lock which supports upgrade/downgrade as atomic primitives. Furthermore, we present an algorithm that transforms a standard reader-writer lock of one of several priority variants into a reader-writer lock of the same priority variant that supports upgrade/downgrade as atomic primitives.

For more information, contact:
Shannon Stearne

Events are free and open to the public unless otherwise noted.