eduKate Sengkang

Small Group Tutorials

Here to help students catch up, keep up, and move ahead. Book a consultation here.

Chat on WhatsApp

How to Learn the Gallager–Humblet–Spira (GHS) Algorithm: Fragments, Minimum Outgoing Edges, Levels, Message Passing and Distributed MSTs

A network can build a minimum spanning tree without any machine seeing the whole network.

That sentence is the doorway into the Gallager–Humblet–Spira algorithm. At beginner level, GHS is a story about small groups joining into larger groups. At university level, it becomes a message-passing algorithm for constructing a minimum-weight spanning tree in an asynchronous network. At professional level, it becomes a case study in distributed state, invariants, termination, message complexity, partial knowledge and the engineering gap between a mathematical model and a real system.

Quick Read

  • Problem: build a minimum spanning tree when each node initially knows only its incident edges.
  • Core idea: nodes form MST fragments; each fragment repeatedly finds its minimum-weight outgoing edge and merges with another fragment.
  • Main learning objects: fragments, levels, core edges, minimum outgoing edges, FIND/FOUND state, and messages such as CONNECT, INITIATE, TEST, ACCEPT, REJECT, REPORT and CHANGEROOT.
  • Why it matters: GHS teaches how a global structure can emerge from local communication.
  • Professional lesson: correctness depends on assumptions about connectivity, edge-weight ordering, delivery and process behaviour. Never carry the theorem into production without carrying the assumptions too.

1. Start with the ordinary minimum spanning tree

Before learning distributed MST, make sure the ordinary MST problem feels concrete. Imagine five school buildings connected by possible fibre links. Each possible link has an installation cost. We want every building connected, no cycles, and the smallest total cost.

If one computer knows the whole graph, Prim’s or Kruskal’s algorithm is natural. GHS removes that luxury. Each node begins with only a local view. It knows its neighbours and the weights of adjacent edges, but not the entire network. The challenge is therefore not only optimization. It is coordination under partial knowledge.

2. The first mental model: islands joining into continents

Use this picture before touching the message types. Every node begins as a one-node island. An island can join another island using a safe edge. The joined structure is called a fragment. A fragment is always part of some minimum spanning tree.

The fragment’s key question is:

What is the lightest edge leaving us?

That edge is the fragment’s minimum outgoing edge, often shortened to MOE. The cut property of minimum spanning trees tells us why this is safe: the lightest edge crossing a cut belongs to at least one MST, assuming ties are handled consistently.

3. Learn the cut property before the protocol

A common learning mistake is to memorize GHS messages before understanding why the merges are correct. Reverse the order. First prove a small claim: if a fragment is already a subtree of an MST, then choosing its minimum outgoing edge can safely extend that fragment.

Take a sheet of paper. Draw a graph. Circle the vertices already in one fragment. Highlight every edge that crosses the circle. Select the lightest. Repeat this on several graphs until “minimum outgoing edge” feels visual rather than verbal.

4. Why GHS needs levels

If fragments simply merged whenever they met, asynchronous messages could leave nodes disagreeing about which fragment they belong to. GHS gives fragments levels. Levels provide structure to merging.

  • If a lower-level fragment connects to a higher-level fragment, the lower-level fragment is absorbed.
  • If two fragments of the same level connect across their chosen minimum outgoing edge, they merge and form a fragment one level higher.
  • The new fragment has a new identity associated with its core edge.

This is a good place to stop and trace. Do not proceed until you can answer: what happens to the level when 0 meets 0, when 1 meets 1, and when 1 meets 2?

5. The message vocabulary

The original algorithm is famous partly because a surprisingly small vocabulary coordinates a global computation. Different expositions vary slightly in notation, but the classic conceptual roles are these:

  • CONNECT: request a merge across an edge.
  • INITIATE: announce the fragment identity, level and current phase/state.
  • TEST: ask whether an edge leaves the current fragment.
  • ACCEPT: confirm that the tested edge reaches another fragment.
  • REJECT: confirm that the edge stays inside the same fragment.
  • REPORT: send the best candidate outgoing-edge weight upward through the fragment tree.
  • CHANGEROOT: redirect control toward the endpoint of the selected outgoing edge.

Do not treat these as seven isolated definitions. Group them by job: merge, identify, test, aggregate, reroute.

6. Predict → run → investigate → modify → make

A strong way to learn a distributed algorithm is not to start by writing the full implementation. Use a scaffolded progression.

  • Predict: given a fragment and four boundary edges, predict which edge becomes its MOE.
  • Run: trace a prepared six-node execution and follow the messages.
  • Investigate: explain why a TEST can receive REJECT and what changes afterward.
  • Modify: change one edge weight or delay one message and predict the new trace.
  • Make: implement a simulator only after the state transitions are understood.

This sequence deliberately reduces cognitive load early. Programming-education research repeatedly finds that novices benefit from reading, tracing and modifying existing code before being asked to construct a complete solution from a blank screen.

7. A small simulation model

For a first implementation, do not use threads or sockets. Build a deterministic event simulator. Give each node an inbox. A global event queue chooses which message is delivered next. This lets you see the algorithm’s logic without hiding mistakes behind timing noise.

NodeState:
    id
    level
    fragment_id
    mode          # FIND or FOUND
    parent_edge
    best_edge
    best_weight
    pending_reports

Event:
    sender
    receiver
    message_type
    payload

while event_queue not empty:
    event = pop_next_event()
    deliver(event)
    assert_local_invariants()

The point of this simulator is not speed. It is visibility. You want to inspect state after every message and deliberately reorder legal deliveries.

8. The invariants that make the algorithm understandable

Professional algorithm study is less about memorizing procedures and more about identifying what must remain true. Useful GHS invariants include:

  • Every accepted branch edge belongs to the forest being constructed.
  • Every fragment is a tree.
  • A node has one current fragment identity at a time.
  • The fragment’s reported candidate is the minimum among candidates discovered in the relevant subtree.
  • Rejected edges are internal to the fragment at the time they are classified.
  • Fragment levels change only under the merge rules.

When your simulator fails, ask which invariant broke first. That is far more informative than asking which line threw the exception.

9. Complexity: count messages, not only CPU steps

In a distributed algorithm, communication is often the dominant resource. The original GHS paper gives a message bound of at most roughly 5N log₂N + 2E for a graph with N nodes and E edges under its model. The striking lesson is methodological: distributed complexity needs more than one axis.

  • How many messages are sent?
  • How large is each message?
  • How many asynchronous phases or effective rounds are required?
  • How much local state does each node keep?
  • What assumptions are made about delivery and failure?

At professional level, never summarize a distributed algorithm as simply “O(n log n)” without naming the resource being measured.

10. What breaks when assumptions change?

The clean theory assumes a connected undirected graph and a communication model in which messages are eventually delivered correctly. The original presentation also uses distinct edge weights; practical implementations can replace that assumption with a deterministic tie-break rule such as comparing (weight, endpoint IDs).

Now ask the professional questions:

  • What if a node crashes during a merge?
  • What if a link disappears after being selected?
  • What if messages are duplicated?
  • What if a stale TEST arrives after a node has changed fragment?
  • What if a graph is dynamic rather than fixed?
  • What if edge weights change while the algorithm is running?

These questions do not mean GHS is “bad”. They teach an essential engineering habit: a theorem proves behaviour inside a model. Production engineering is the work of deciding whether the model fits reality, and what additional machinery is required when it does not.

11. Common misconceptions

  • “Each node runs Prim’s algorithm.” No. No node has the global view required for ordinary Prim.
  • “The lightest edge seen by a node is always safe.” No. The safe object is the minimum outgoing edge of a fragment, not merely a node’s cheapest incident edge.
  • “A rejected edge is useless forever.” It is internal to the current fragment when classified; reason about the precise state and implementation rules.
  • “Asynchronous means random.” It means there is no shared global timing assumption; correctness must tolerate many legal delivery orders.
  • “Message complexity is the same as time complexity.” It is not.

12. Beginner → intermediate → advanced → professional pathway

Beginner

  • Understand MSTs, trees, cuts and the cut property.
  • Identify an MOE on paper.
  • Explain fragments using the island metaphor.

Intermediate

  • Trace fragment levels and merges.
  • Classify the seven message roles.
  • Run a deterministic event simulation.

Advanced

  • State and test invariants.
  • Explain why minimum outgoing edges are safe.
  • Analyze message complexity.
  • Generate adversarial but legal message schedules.

Professional

  • Separate theorem assumptions from platform guarantees.
  • Design deterministic tie-breaking and stale-message handling.
  • Model failure and recovery explicitly.
  • Compare GHS with later distributed MST results and with centralized MST construction.
  • Use formal specification or model checking for critical state transitions where appropriate.

13. Practice set

  1. Draw a seven-node weighted graph and manually identify the first three fragment merges.
  2. Give two same-level fragments a candidate edge and show why their new level increases.
  3. Create a trace in which an old TEST message arrives after a fragment identity changes. Decide how your simulator should interpret it.
  4. Count every message in a small run by type.
  5. Write a property-based test: after every event, branch edges must remain acyclic.
  6. Compare the information available to one GHS node with the information available to Kruskal’s algorithm.

14. Professional comparison questions

A good engineer should be able to explain not only how GHS works, but when its model is useful. Compare it with centralized Kruskal/Prim, spanning-tree protocols used for different networking goals, later distributed MST algorithms, and modern systems in which topology changes continuously.

The right conclusion is not “GHS is old”. The right conclusion is that GHS is a durable training ground for local knowledge, asynchronous coordination, safe merging, hierarchical state and communication complexity.

Sources and further reading

The learning goal is bigger than one algorithm: learn to see how a global guarantee can be built from local state, carefully chosen messages and invariants that survive asynchronous execution.