Models of Computation References
Last updated at 12:38 pm UTC on 17 January 2006
This page is designed to capture reading material on parallel and distributed programming constructs, which permit people to run a collaborative application on many computers at once, often separated by non-trivial network delays. Please upload or link any references you find.
Synchronous/Reactive Programming
A reactive programming language is designed (mostly) for hardware or embedded software. The fundamental idea is that computation takes zero time, and all message sends take time 1. This means that messages are delivered between clock ticks, and so no message reception can interrupt computation. In other words, no race conditions...well, mostly. If global variables are permitted we can get race conditions on updates to global variables.
Security, Safety, and Event Ordering
The E programming language focussed on providing a safe and useable distributed programming environment. See http://www.erights.org for a discussion. There are two fundamentally new structures in E:
- Promise pipelining http://www.skyhunter.com/marcs/ewalnut.html#SEC20 which creates a data structure representing the eventual return from a remote message. This can be used to pipeline computations based on the result of a send
- Object capabilities, which separate authentication from authorization and only permit code to perform actions specifically authorized.
A draft Croquet Security Requirements Suggestions has been created to encourage development of a shared view of Croquet security needs before the meeting. A follow-on Models of Computation References has been added as a discussion element, as it has become apparent that the university applications of Croquet have more severe security requirements than originally appreciated.
Models of Computation
Edward Lee of UC-Berkeley observed that most parallel programming differed in the way in which parallel programs exchanged data, sent messages, blocked and unblocked computation. He created a (by now, voluminous) executable library of such "models of computation", together with editors and debuggers. This impressive piece of work can be found in the Ptolemy II project http://ptolemy.eecs.berkeley.edu/ptolemyII/. The best summary of Ptolemy II comes from its FAQ: The Ptolemy project studies modeling, simulation, and design of concurrent, real-time, embedded systems. The focus is on assembly of concurrent components. The key underlying principle in the project is the use of well-defined models of computation that govern the interactions between components. A major problem area being addressed is the use of heterogeneous mixtures of models of computation.
Distributed Objects and Croquet
Croquet is a programming and user environment for wide-area distributed systems based on David Reed's notion of distributed objects. The summary, copied directly from Alan Kay's attached description (Time_Late-Bound.doc), is:
Croquet's treatment of distributed computation assumes a truly large scale distributed computing platform, con-sisting of heterogeneous computing devices distributed throughout a planet-scale communications network. Ap-plications are expected to span machines and involve many users. In contrast with the more traditional architec-tures we grew up with, Croquet incorporates replication of computation (both objects and activity), and the idea of active shared subspaces in its basic interpreter model. More traditional distributed systems replicate data, but try very hard not to replicate computation. But, it is often easier and more efficient to send the computation to the data, rather than the other way round. Consequently, Croquet is defined so that replication of computations is just as easy as replication of data.
See http://croquetproject.org for more comprehensive information about the Croquet project, including many screenshots
Time_Late-Bound.doc (I don't suppose some kind soul could convert this document into something a bit more accessible for those of us who don't have Word? – Frank Shearar)
Time_Late-Bound.pdf (I happened to be converting several other docs to pdf, so I converted this while I was there – Marc Stiegler)
croquetSecurityRequirements.txt
croquetSecurityRequirementsHigherEd.txt
Presentations:
Habitat Redux: New Lessons from the Virtual Outback
http://www.fudco.com/habitat/HabitatRedux.ppt
Promise Pipelining: Distributed Programming Made Practical
http://www.erights.org/talks/promises/index.html (Powerpoint 2002 or later)
Building a Virus-Safe Platform: Don't add security, remove insecurity
http://www.erights.org/talks/virus-safe/index.html (Powerpoint 2002 or later)
Uni-Tea: Towards a unified, parameterizable model of distributed "object"
http://www.erights.org/talks/uni-tea/index.html (Powerpoint 2002 or later)
Other:
I don't know where else to put this, so here it is: http://www.agorics.com/Library/agoricpapers.html. From the page: "Like all systems involving goals, resources, and actions, computation can be viewed in economic terms. This paper examines markets as a model for computation and proposes a framework–agoric systems–for applying the power of market mechanisms to the software domain. It then explores the consequences of this model and outlines initial market strategies."
I suspect that the inventores of the "agorics" concept have hobbled the whole idea with patents (they state on the main page of the site that "Agorics' employees have authored ten patents fundamental to secure electronic commerce."
