/ talks

Concurrency Among Strangers Programming in E as Plan Coordination

Superseded by Robust Composition.

by Mark S. Miller,
E. Dean Tribble, and
Jonathan Shapiro

Programmers write programs, expressing plans machines to execute. When composed so that they may cooperate, plans may instead interfere with each other in unanticipated ways. Plan coordination is the art of simultaneously enabling plans to cooperate, while avoiding hazards of destructive plan interference. For sequential computation within a single machine, object programming supports plan coordination well. For concurrent computation, this paper shows how hard it is to use locking to prevent plans from interfering without also destroying their ability to cooperate.

In Internet-scale computing, machines proceed concurrently, interact across barriers of large latencies and partial failure, and encounter each other???s misbehavior. Each dimension presents new plan coordination challenges. This paper explains how the E language addresses these joint challenges by changing only a few concepts of conventional sequential object programming. Several projects are adapting these insights to existing platforms.

PDF

Talk Abstract

The conventional concurrency control model -- shared memory multithreading with fine-grained locking -- is deceptively hard. Although many people have learned this model, few have learned -- or could learn -- how to write complex correct programs in this model. A correct program must maintain consistency while avoiding deadlock. Further, when extended to distributed systems, threads lead one into inefficient synchronous communication patterns.

Promise pipelining is the concurrency and distributed computation model of the E language, and made available to Java programs through the ELib library. Starting from any sequential object oriented programming language, promise pipelining adds only two operators -- the "eventual send" and the "when-catch" -- to support deadlock-free, latency-tolerant, transactional, communicating event loops. We demonstrate how Causeway, our distributed debugger, by shifting our view from "follow the process" to "follow the messages", shows us causal paths of interest independent of machine boundaries.

Complex yet robust distributed systems have been created rapidly in E, including a decentralized secure social virtual reality system, a toy stock market, and a distributed secure desktop and file manager.

Talk slides

• Powerpoint 2002 or later
• ugly PDF, in which each animation has been crushed together into an unintelligble graphic

Alternate version, as given to the Mozart/Oz group

• Powerpoint 2002 or later

Bio

Mark S. Miller is the Chief Architect of the Virus Safe Computing Initiative, a skunkworks project at Hewlett-Packard Laboratories, and is the Open Source Coordinator of the E Project at http://www.erights.org. He is a designer of several distributed secure programming languages including Vulcan for Xerox PARC, Trusty Scheme for AutoDesk, Joule for Agorics and Fujitsu, Tclio for Sun Labs, and E for Electric Communities, ERights.org, and Combex. As founder and CTO of Combex, Mark fashioned E into the platform used for CapDesk -- a Darpa-sponsored prototype of a virus-safe distributed desktop and application launching framework.

Mark was drawn into concurrency control by pursuit of another dream. He is a co-creator of the agoric paradigm of market-based adaptive distributed secure computation. He is also a founder of Agorics, a company started to capitalize on agoric computing ideas.