March 31, 2007

Updates from ILC


March 29, 2007

Going to the ILC

All arrangements have been made and I'm flying out to London tomorrow. I plan to blog from the conference. If you're there on Saturday, drop by Tishka's cafe (where Nick Levine is planning to host a breakfast) - I'll be there for brunch, possibly late breakfast, and maybe I'll drop by for lunch as well. I'll also be attending the afternoon tour.

March 17, 2007

ILC 2007!

After Nick Levine sent me an email stating that the ILC 2007 programming contest judges would like to give me a prize, only too bad I can't come to Cambridge (nice marketing tactic :)), I finally broke down and booked a flight. I'm going to ILC 2007! I'm going to be totally broke!

March 10, 2007

Complete computing system in 20,000 lines of code

I just finished watching Ian Piumarta's talk on the project at Viewpoints Research Institute to build a complete (metal up) personal computer system in 20,000 lines of code. While the easy way to do this would be to use APL, Ian, Alan Kay, Dan Ingalls, and the others working on the project have instead opted to go for building metacircular/self-describing systems instead. Of course, in modern parlance this is called "reflection," a very crappy version of which can be found in the Java language and runtime system. Among fascinating programming language and compiler topics, Ian discusses Schorre's Meta-II compiler compiler (developed in 1962), which had a self-describing grammar. Fascinating stuff, and in my opinion critically important, since the only proven way to reduce software complexity has been, to, well, reduce software complexity - less lines of source code written in a simpler way makes for better, more maintainable software, and this is exactly what the project aims to do.

Here is the link to the video:

March 8, 2007

Upcoming Lisp user's group meeting

The next Calgary Lisp user's group meeting will take place at 6:30pm on Wednesday, March 14th, at the Saigon Y2K restaurant at 2110 Crowchild Trail NW in the strip mall on Crowchild Trail right near the Banff Trail C-Train station and across from McMahon Stadium.

March 6, 2007

Nested Transactions

Here is another post in my series about distributed systems.

This one is about J. Eliot B. Moss's 1985 PhD dissertation on nested transactions, Nested Transactions: An Approach to Reliable Distributed Computing, published by the MIT Press. In it, Moss explains the design of his distributed transaction system supporting nested transactions.

Although Moss's is not the first distributed system to support nested transactions, the dissertations introduces the novel mechanism of two-phase locking and deadlock detection as the mechanism for guaranteeing serializability as a correctness condition.

A contrasting approach to implementing nested transactions is to use multi-version timestamping (introduced in David P. Reed's 1978 PhD dissertation, mentioned in a previous post). This approach is free of deadlock as a result of object timestamping, however it is vulnereable to livelock (slow, long-running transactions retrying repeatedly due to changes committed by quickly running ones). For the same reason, multi-version timestamping does not work well in the presence of a high degree of contention over an object by many transactions. Aspnes et alia's 1988 paper on applying multi-version timestamping to nested transactions provides an extension of Reed's original algorithm that somewhat alleviates this problem.

Nested transactions, while not strictly necessary for many systems, become critical when nondeterminism, such as the 'orElse' construct introduced in Harris et alia's 2005 paper on composable memory transactions and implemented in the GHC software transactional memory system (to be discussed in an upcoming post), is needed.