Skip to content

Global Minimum on Network

Level: L4-L6 Topics: Distributed Systems, Graph Algorithms, Message Passing

Problem Statement

You are given a connected network of computers modeled as an undirected graph. Each node (computer) can only communicate with its immediate neighbors through ports — there is no global addressing, no broadcast, and no shared memory.

Each node holds a random integer value. The values across nodes are not necessarily unique.

One designated node is the initiator. Design a distributed algorithm so that:

  1. The initiator discovers the global minimum value across all nodes.
  2. Once found, the global minimum is propagated to every node in the network.

You must design the message-passing protocol that each node follows. Nodes only know their own value and their neighbor ports — they have no knowledge of the overall topology.

Background & Constraints

  • The network is a connected undirected graph with N nodes.
  • Each node has a local integer value (not necessarily unique).
  • Nodes communicate exclusively by sending messages through ports to neighbors.
  • There is no global clock — messages may arrive in any order, but delivery is guaranteed (no lost messages).
  • Exactly one node is designated as the initiator.
  • Each node must eventually know the global minimum value.

Examples

Network:

    A(7) --- B(3) --- C(9)
      |               |
    D(5) --- E(1) --- F(4)
  • Initiator: Node A
  • Global minimum: 1 (held by Node E)

Expected behavior:

  1. A starts the algorithm by sending messages to neighbors B and D.
  2. Messages propagate through the network, with each node forwarding the smallest value it has seen.
  3. Eventually, A learns the global minimum is 1.
  4. A (or the protocol itself) propagates the value 1 to all nodes.

Hints & Common Pitfalls

  • Spanning tree approach: A common strategy is to build a spanning tree rooted at the initiator using a flood-based protocol. Leaves report their values upward; internal nodes report the minimum of their children and themselves. The root then broadcasts the result downward.

  • Convergence detection: The initiator needs to know when all nodes have reported. Think about how a parent node waits for all children to reply before forwarding upward.

  • Cycle handling: The network may have cycles. Your protocol must handle the case where a node receives the "explore" message from multiple neighbors. The first sender becomes the parent; subsequent senders get a rejection or are simply ignored.

  • Common mistake: Assuming a tree structure from the start. The network is a general graph — you must build the tree as part of the algorithm.

  • Message format matters: Each message should carry enough information for the receiver to decide what to do (e.g., "explore", "report minimum", "broadcast result").

Follow-Up Questions

  1. Message complexity: How many messages does your algorithm send in the worst case? Can you achieve O(E) messages where E is the number of edges?

  2. Optimization: Can you reduce the number of messages by pruning early — for example, if a node already knows a value smaller than what it would report?

  3. Find the median instead: How would you modify the algorithm to find the median of all values across the network? What additional information must nodes exchange, and how does this change the message complexity?

  4. Fault tolerance: What happens if a node crashes mid-algorithm? How would you modify the protocol to handle node failures gracefully?