Distributed Algorithm for Constructing Minimal Spanning Trees in Networks (1976) [pdf]

i.stanford.edu

66 points·kick··6 comments

Hacker News's character limit is too short for the full, unminced title, which is:

A Distributed Algorithm for Constructing Minimal Spanning Trees in Computer-Communication Networks

I think it's worth sharing because (aside from the technical merits of the paper) it highlights how, despite the field not being that old, it has the memory of a rodent: a lot of the vocabulary found within is opaque without further inspection, even though a lot of problems described within are still relevant today.

What exactly did you find interesting in the paper? It's a pretty bad paper. The kind of paper you would expect from pre Lamport "distributed algorithms".

It seems that that work didn't make much impact because it sat as a tech report and wasn't published until 1987, by which time Perlman had published her algorithm that received more exposure in SIGCOMM in 1985.

Interesting I was wondering why.

why is spanning tree gaining so much interest recently?

No idea. It is old as shit and equally annoying. There are many reasons why we (architects) minimize L2 domains - namely because we can achieve re-route / convergence quicker with other protocols, with STP being the long pole. Hell, containers are just L3-L3 forwarding in a lot of cases - no L2 domain, conceptually.

TLDR: Spanning-Tree is the previous war. E-VPN + Modern L3 segmentation is the new way.

Reply on news.ycombinator.com