Matt Gemmell

TOLL is available now!

An action-thriller novel — book 2 in the KESTREL series.

★★★★★ — Amazon

We're building a spanning tree!

tech & university 1 min read

Building a spanning tree of blogs, just for the sheer hell of it.

In a Distributed Algorithms and Systems lecture today, Peter Dickman was talking about using spanning trees as a tool for leader election and such in a distributed system. It got me thinking, and I’m sure we could build a spanning tree of blogs by making using of the pingback functionality of most modern blogging systems. The basic idea is as follows:

  • The initiator links to and in some way pings some other blogs, say for example Derek's and Gary's, telling them that we're building a spanning tree.
  • When a blog, B, receives such a ping, it takes note of the blog which pinged it (its parent), and it itself pings further blogs as its potential immediate children in the tree, waiting for their reply pings to determine whether it is their parent in the tree.
  • When all B's children blogs have replied, B pings its parent, P, to inform P that P is indeed B's parent. Upon B receiving further pings, B replies saying that the sender is not its parent.

The reply pings could just literally say “you are my parent” or “you are not my parent” (or perhaps some more offensive variant with the same essential meaning, in Gary’s case). Thus, upon completion of the tree (i.e. the initiator having received replies from all its children), you could traverse the entire structure from the initiator by clicking the displayed pingback links which indicated that the current blog was the parent of the pinging blog(s).

During traversal, leaf blogs would obviously be indicated by having either no listed pingbacks at all, or only those which said that the current blog was not the ping-sender’s parent.

I’m not sure how you’d ping the root of a blog, or if that’s even possible without creating a dedicated system to receive and distribute tree-construction pings, so for the moment I’ve simply linked to Derek and Gary’s blogs above, being fairly sure they’ll read this post before long. Their hypothetical reply pings would of course target this specific post, as normal.

We’ll see whether or not the idea just dies right here, and indeed whether I’m openly mocked for my sheer Peter Dickman fanboy-ism. In closing, I should note that Gary rightly suggested that this would probably be more successful, and a damn sight faster, if done via instant messaging. Maybe we’ll try that approach out sometime too.