 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/concurrent-programming/2/a/ii/solution

 Top articles  Latest articles New article in topic

Past exam of the computer science course of the University of Oxford / 2015 / Concurrent programming / 2 / a / ii / Solution by

Codex  0 2026-10-31

Use one logical traversal token carrying the discovered vertex set and the active LIFO stack of vertices. The current vertex either discovers its first still-unvisited outgoing graph neighbour, or returns to its preceding stack entry. The former records both the child's parent in a rooted tree and the parent's child. Unlike concurrent flooding discovery, this visits one entire branch before the next, giving an actual depth-first search.

The important directed-graph detail is that a child's parent need not be an outgoing graph neighbour. Return the token by routing it through the original directed graph; a routing hop does not count as a traversal visit. The following duplicate-suppressed flooding route requires no previously known topology and sends only to immediate outgoing graph neighbours.

final case class Token(visited: Set[NodeId], stack: List[NodeId], serial: Int)
sealed trait Msg
final case class Route(serial: Int, target: NodeId, token: Token) extends Msg
case object Finished extends Msg

Here stack.head is the current vertex. Use the same paired toNode and fromNode ports as in (i), now with the new Msg type. Set mailbox capacity to

B = N (2 N + 1)

, normalize neighbours with distinct, and again leave the mailboxes open until all processes have joined. The following helpers are local functions inside each node's generated process.

def span: PROC = proc {
  val adj = neighbours.distinct
  val routed = scala.collection.mutable.Set[Int]()
  var entered = false
  var done = false

  def flood(message: Msg): Unit =
    for (w <- adj) toNode(w) ! message

  def move(target: NodeId, state: Token): Unit = {
    val s = state.serial + 1
    routed += s
    flood(Route(s, target, state.copy(serial = s)))
  }

  def step(t: Token): Unit = {
    assert(t.stack.head == me)
    if (!entered) {
      entered = true
      parent = if (t.stack.tail.isEmpty) me else t.stack.tail.head
      children = Nil
    }
    adj.find(w => !t.visited(w)) match {
      case Some(w) =>
        children = children :+ w
        move(w, Token(t.visited + w, w :: t.stack, t.serial))
      case None =>
        t.stack.tail match {
          case p :: rest => move(p, t.copy(stack = p :: rest))
          case Nil => flood(Finished); done = true
        }
    }
  }

  if (me == 0) step(Token(Set(0), List(0), 0))
  while (!done) {
    fromNode(me) ? () match {
      case r @ Route(s, target, t) =>
        if (!routed(s)) {
          routed += s
          if (target == me) step(t) else flood(r)
        }
      case Finished => flood(Finished); done = true
    }
  }
}

Every route number is globally unique: there is one logical token, and its serial increases at every move. The sender inserts that serial in its own routed set before flooding; this stops a returning copy from circulating again. Intermediate vertices forward the first copy of an envelope and ignore later copies. Its target consumes exactly one copy without forwarding it. Because the directed graph is strongly connected, a simple directed path from sender to target exists; its intermediate vertices eventually relay the envelope. Thus each move eventually finishes.

A routed return can pass through a vertex not yet discovered by the depth-first search. That vertex only forwards the envelope: it does not run step, change entered, or assign a parent. This distinction is essential. For the directed cycle

0 \to 1 \to 2 \to 0

, returning from two to one uses

2 \to 0 \to 1

, while the logical traversal stack changes from

(2, 1, 0)

(1, 0)

Figure 1.
A depth-first search return follows a routed directed path when the child has no reverse directed edge
. **Details**.

The discovered vertex set only grows. Each newly discovered vertex is pushed once and later popped once; an exhausted vertex can never acquire a new unvisited neighbour as this set grows. Consequently there are exactly

N - 1

downward moves and

N - 1

return moves. When the root exhausts its outgoing graph neighbours, every vertex has been visited, by the standard reachability argument for depth-first search. Each nonroot parent was recorded along the actual downward directed edge, and children records exactly those assignments in discovery order.

There are

2 (N - 1)

route envelopes, each forwarded at most once per outgoing directed edge, and one final Finished flood. Each node forwards Finished before exiting; strong connectivity therefore delivers it everywhere. There are at most

N (2 N - 1)

total messages into any mailbox, below the proposed capacity. Even a mailbox whose process has already exited cannot block later sends. All processes terminate with

the parent and ordered children of a depth-first spanning tree rooted at 0.

(1)

This deliberately trades communication efficiency for a simple valid solution on a genuinely directed graph. A direct parent acknowledgement would instead require an additional bidirectional-edge assumption, which the question does not supply.

 Read the full article

 New to topics? Read the docs here!