After writing about wanting a replicated versioned database for storing host configuration information the other day, I found out about ZooKeeper, from Yahoo! Research. I'm fairly sure that it's what I was looking for. I've been playing with it today and all looks good so far.
Here's a blog post about it with some more details. Basically it's a distributed versioned object store with a few tricks (the ability to set 'ephemeral' nodes, which disappear when you disconnect, and nodes with serial numbers) that let you implement locks, barriers and queues.
The Java process that's been running it all afternoon has used 7 s of CPU time so far and is showing an RSZ of 16704 kB, so it looks like it scales down well - that's comparable to a Python or Ruby process.