Thesis Proposal: Type Theory for Mobility and Locality

Details

Date (Mon) Jan 26, 2004
Time 1:30pm
Place Wean 4623

Abstract

In this proposal, I present a calculus for distributed programming with types corresponding to necessity ([]A) and possibility (<>A) of constructive modal logic. Distributed computation has been described and studied in many ways. This work should be understood as a reconsideration of distributed programming from a new perspective --- that of modal logic and type theory.

Through a Curry-Howard interpretation of proof terms as programs and propositions as types, I show that logical necessity is connected to mobility, and possibility to (remote) locality. I give an operational interpretation based on process configurations, where each process serves as an abstract location. This semantics is type-safe, and under certain restrictions, strong normalization and confluence hold.

The notions of mobility and locality derived from modal logic are general and open-ended. I present some extensions and examples, including examples of mobile and localized values. Finally, I discuss plans to implement the calculus for execution in the the ConCert grid computing framework and characteristics of S4 modal logic (among other logics) which involve trade-offs between expressive power and feasibility of implementation.

Documents

Proposal (Feb 13, 2004) [.ps.gz]

Proposal (Jan 19, 2004)

Proposal (Dec 2, 2003)

Background TR: Modal Logic as a Basis for Distributed Computation (Oct 2003)

Presentation

Slides


Valid HTML 4.01!