A few people asked me to pass this announcement along to the PSAS lists.
This coming Monday, I will present and defend my PhD proposal.

- Josh Triplett

----- Forwarded message from Graduate Coordinator <g...@cecs.pdx.edu> -----

Date: Thu, 09 Dec 2010 15:30:07 -0800
From: Graduate Coordinator <g...@cecs.pdx.edu>
To: cs-g...@cs.pdx.edu, cs-underg...@cs.pdx.edu, pt-facu...@cs.pdx.edu,
        ft-facu...@cs.pdx.edu, Staff <st...@cs.pdx.edu>
Subject: [CS Department] PhD Proposal Defense: Relativistic Programming
User-Agent: Thunderbird (Windows/20100228)
List-Id: <cs-grad.cecs.pdx.edu>

All are invited to the dissertation proposal defense presentation by
Josh Triplett, a doctoral student in the Department of Computer

"Relativistic Programming"

Dissertation Proposal Defense by Josh Triplett
Monday, December 13th at 10am
FAB 150
Advisor: Jonathan Walpole

Abstract below.

Relativistic Programming offers the promise of linearly scalable read
algorithms even in the presence of concurrent writes.  This scalable
concurrency will become a necessity as CPUs grow more numerous and
communication latency becomes the critical path.  However, thus far
the adoption of Relativistic Programming has suffered due to a lack of
two key components available with mutual exclusion: a clear practical
reasoning model with which to think about algorithms, and a general
solution for constructing writers for arbitrary data structures.  I
outline research leading to solutions to both problems.

As a promising demonstration of the potential generality of
Relativistic Programming, I will present two new algorithms on hash
tables: a move operation to change the hash key associated with a node
(designed to support renames), and a resize operation to maintain the
hash table's load factor.  Each of these operations supports scalable,
concurrent, deterministic readers.  Both algorithms go beyond the
existing relativistic data structure models.

To address the first shortcoming of relativistic programing, a lack of
a clear reasoning model, I will propose and document a new approach to
modeling data structures as graphs and reader algorithms as traversals
of these graphs.  This model will support reasoning about how and when
readers observe writer changes.  To test this new reasoning model, I
will use it to show the correctness of existing algorithms from
previous literature and my own hash-table research.

I will then provide a general construction technique supporting any
acyclic data structure storable in shared memory, and use this
technique both to recreate algorithms for existing relativistic data
structures and to create new algorithms for two previously unsupported
data structures.  Benchmarks of the constructed algorithms for both
the recreated and new data structures will show that the general
construction technique produces the same linearly scalable behavior
expected of relativistic techniques.

Together, these contributions will provide a rigorous treatment of the
relativistic programming methodology, sufficient to support and defend
its use in a broad class of concurrent algorithms.


Ms. Kelley Gardiner
Graduate Coordinator
Computer Science
Portland State University
(503) 725-3218

Cs-grad mailing list

----- End forwarded message -----

psas-avionics mailing list

Reply via email to