A hug for Digg’s Scribe tree. ▪
The key algorithm that makes FeedTree possible is the Scribe peer-to-peer multicast system. Scribe trees are each organized around a topic, in this case, the URL of a feed; each subscriber in the Pastry network routes a message incrementally toward the node nearest the topic, and the union of all those routes (with arrows reversed!) becomes an effective multicast tree.
An example of a lovely Scribe tree, taken from current network statistics, is the current multicast tree for Digg’s main feed:
It’s not exactly a balanced tree, because it’s constructed organically from Pastry routes. But it’s effective: it’s cheap to maintain given the Pastry infrastructure, and it fans out quickly, so updates propagate rapidly from the root down to every subscriber. And because there are at least 3 nodes polling Digg’s feed at the moment, there are new stories for all FeedTree proxy users once every 10 minutes or so. (That’s a lot to digg!)
Key:
- rectangle = Scribe topic (SHA-1 hash of feed URL)
- oval = subscriber
- dotted oval = helper (non-subscribing member of tree)