1 Exam Paper Distribution: Serial Column-Chain vs. Radial Broadcast-Tree

Classroom: 50 students, arranged 10 rows × 5 columns Timing rules (realistic model): - Take own paper: 1 second - Hand stack to one neighbor (one direction): 1 second - A person can only do one action per second — you cannot take your paper and hand off in the same second, and you cannot hand off to two neighbors simultaneously (one pair of hands). - All students who are free to act do so in parallel, every second (synchronous rounds).

1.1 Algorithm 1: Serial Column-Chain Distribution (traditional method)

1.1.1 Pseudocode

for col in 1..C:                      # teacher works one column at a time
    teacher hands stack to front student of col      # 1 sec

for each column, in parallel:
    student = front of column
    while student has a stack:
        student takes own paper                        # 1 sec
        if not last student in column:
            student hands remaining stack to next       # 1 sec
        student = next student in column

1.1.2 Diagram — how the stack moves

Teacher
  │ 1s  2s  3s  4s  5s   (teacher hands off columns one at a time)
  ▼   ▼   ▼   ▼   ▼
 [S] [S] [S] [S] [S]   ← row 1 (front)
  ↓   ↓   ↓   ↓   ↓     take own paper (1s) → hand back (1s), repeated
 [S] [S] [S] [S] [S]   ← row 2
  ↓   ↓   ↓   ↓   ↓
  ⋮   ⋮   ⋮   ⋮   ⋮
  ↓   ↓   ↓   ↓   ↓
 [S] [S] [S] [S] [S]   ← row 10 (back)

1.1.3 Timing

Teacher hands off to C = 5 column fronts, one at a time → 5 sec
Within a column of R = 10 students: everyone but the last does take (1s) + hand (1s), the last student only takes (1s) → 2(R−1) + 1 = 2R − 1 = 19 sec (runs in parallel across all 5 columns)
Columns start staggered (teacher reaches column 5 last), so the last column finishes at:

Column	Receives stack at	Finishes at
1	t = 1	t = 20
2	t = 2	t = 21
3	t = 3	t = 22
4	t = 4	t = 23
5	t = 5	t = 24

1.1.4 Total: 24 seconds

1.2 Algorithm 2: Radial Broadcast-Tree Distribution

1.2.1 Pseudocode

teacher hands stack to center student                  # 1 sec

function distribute(student, stack):
    directions = neighbors(student) not already served (front/back/left/right)
    sort directions by size of the subtree they still need to reach,
        largest/farthest subtree FIRST                  # greedy scheduling
    for d in directions:
        hand a stack to neighbor in direction d          # 1 sec each, sequential
        distribute(neighbor_d, that sub-stack)           # recurses in parallel
    student takes own paper                              # 1 sec (done last,
                                                           #  since it doesn't
                                                           #  block anyone else)

Each student who receives a stack becomes a new local “hub”: they hand off to whichever of their still-unserved neighbors (up to 3, or up to 4 for the very first/center student) remain, one per second, then take their own paper. To finish as fast as possible, each hub sends toward its most distant/largest remaining branch first — this is the standard optimal strategy for minimizing broadcast time in a tree network.

1.2.2 Diagram — wavefront expanding from the center

Numbers = the second each student receives the stack (center student = seat (row 5, col 3)):

 9  8  6  7  8
 9  8  5  7  8
 8  7  4  6  7
 7  6  3  5  6
 6  5  1  4  5   ← center receives at t = 1
 6  5  2  4  5
 7  6  3  5  6
 8  7  4  6  7
 9  8  5  7  8
 9  8  6  7  8

Numbers = the second each student has finished taking their own paper (fully done):

10 10  9  9  9
10 10  9  9  9
 9  9  8  8  8
 8  8  7  7  7
 7  7  6  6  6
 7  7  6  6  6
 8  8  7  7  7
 9  9  8  8  8
10 10  9  9  9
10 10  9  9  9

1.2.3 Broadcast tree (levels, from center)

flowchart TD
    T[Teacher] -->|1s| C0["Center (t=1)"]
    C0 -->|1s| L1a["Right (t=2)"]
    C0 -->|1s| L1b["Left (t=3)"]
    C0 -->|1s| L1c["Front (t=4)"]
    C0 -->|1s| L1d["Back (t=5)"]
    L1a --> L2a["3 further neighbors (t=3..5)"]
    L1b --> L2b["3 further neighbors (t=4..6)"]
    L1c --> L2c["3 further neighbors (t=5..7)"]
    L1d --> L2d["3 further neighbors (t=6..8)"]
    L2a --> Ln["... wavefront continues outward ..."]
    L2b --> Ln
    L2c --> Ln
    L2d --> Ln
    Ln --> Corner["Farthest corner student finishes: t=10"]

1.2.4 Total: 10 seconds

1.3 Comparison & Time Saved

	Serial Column-Chain (traditional)	Radial Broadcast-Tree
Total time	24 sec	10 sec
Bottleneck	Last column, last row	Farthest corner from center
Parallelism used	Across columns only	Across all 4 directions, every hub

1.3.1 Time saved: 24 − 10 = 14 seconds (≈ 58% faster)

1.3.2 Why the gap is so large

Traditional distribution only parallelizes between columns; within a column it’s a strict 1-D chain of 19 seconds.
The Radial Broadcast-Tree method parallelizes in all 4 directions simultaneously and keeps splitting the workload at every hub, so the deepest chain any single paper travels is only 9 hops from center to the farthest corner (10×5 grid), instead of up to 13 hops (5 across + 9 down) in the worst traditional path.
The gain would be even larger in a bigger or more “square” classroom, since the broadcast-tree’s finish time grows roughly with the grid’s radius, while the column-chain’s grows with columns + rows.