"I have a mind like a steel... uh... thingy." Patrick Logan's weblog.

Search This Blog

Wednesday, September 05, 2007

Naming and Synchronization in a Decentralized Computer System

This is David Reed's dissertation from 1978. Croquet, developed in Squeak Smalltalk, is based on this mechanism.

3 comments:

Duncan said...

I printed out a copy of David Reed's NAMOS paper earlier this summer and tried to read it. Not knowing much about distributed systems, I didn't get very far.

Some people say the relative obscurity of the NAMOS paper is a reason why Croquet's approach is radical (then they lament that people don't read old papers anymore, etc etc). But it seems like the concepts described in NAMOS are quite similar to Leslie Lamport's super-famous paper, which according to the Wikipedia, it won the PODC Influential Paper Award in 2000 and is well-cited.

So here's something that I'd like to find out: how is the NAMOS paper different from Lamport's Time, Clocks, and the Ordering of Events in a Distributed System paper?

Patrick Logan said...

I am not the expert to give you a detailed analysis. They're both concerned with achieving a reasonable ordering of changes from multiple sources, allowing for the network's ability to foul things up.

Reed's approach seems more focused on performance of synchronization and the representation of changes.

Lamport's approach seems more focused on the algorithm for a reasonable partial ordering based on a representation of "time" on the network itself. He seems less concerned with pragmatic synchronization issues. I would assume he is interested in that, but would base that on the information in the events he is being careful to order.

Erik Onnen said...

Ok, I'm completely intrigued by the fact that you blogged about this around the same time I was reading about Google's Chubby Lock. Aside from loving the name, I think my small brain can see some similarities between the two, although as I understand it, Google seems to be using Chubby Lock for more than simple synchronization and naming - i.e. master escalation among peers per Paxos-like behavior.

Haven't given it due diligence to be sure, but I'm amazed that we keep ending up in the same place though different roads :)

Blog Archive

About Me

Portland, Oregon, United States
I'm usually writing from my favorite location on the planet, the pacific northwest of the u.s. I write for myself only and unless otherwise specified my posts here should not be taken as representing an official position of my employer. Contact me at my gee mail account, username patrickdlogan.