Visual walkthrough — Bus topologies and arbitration

The parent note dropped a clean-looking result on you:

$T_{\text{latency}}\le (N-1)\cdot T_{\max }$

for round-robin arbitration. But where does that number $N-1$ come from? Why not $N$, or $N+1$? And what is $T_{\max }$ really measuring? This page rebuilds that inequality from the very first idea — no symbol used before it is drawn.

---

Step 0 — The words before the symbols

Before any formula, we agree on plain-language meanings and pin each to a picture.

We will call the number of masters $N$. So $N$ is just how many devices are in the circle — a plain counting number like $N=4$.

In the figure: four rounded boxes ($M_0,M_1,M_2,M_3$) all reach for one horizontal bar — the bus. The referee (the small circle in the middle) can only wave one of them through at a time. Everyone else waits. That "waiting" is the whole subject of this page.

---

Step 1 — Turning "circular order" into a pointer

WHAT. Round-robin means: after a master finishes, the next master in a fixed circle gets the first chance. We encode "whose turn it is" with a single number $C$, a pointer.

WHY a pointer and not a priority list? Because the rule is positional, not importance-based. Nobody is permanently first. The only thing that matters is "where the pointer is standing right now." One integer captures that completely.

PICTURE.

The four masters sit on a clock face. The arrow is $C$, the pointer, currently aimed at $M_1$. The tiny curved arrow shows the only motion allowed: after a turn, $C$ steps one seat clockwise.

Why do we need the modulo? Because there is no "seat $N$." Seats are numbered $0,1,\dots ,N-1$ — that's $N$ seats total. $\mathrm{mod}N$ guarantees the pointer only ever names a real seat.

---

Step 2 — What "one turn costs" — defining $T_{\max }$

WHAT. Each transaction takes some time. Different transactions take different times, but there is a longest possible one. We name that ceiling $T_{\max }$.

WHY a maximum and not an average? We are asking a worst-case question ("how long can I be forced to wait?"). Worst case means: assume every master ahead of you took the slowest legal transaction. Averages would answer a different question (typical wait). For real-time guarantees, only the ceiling is safe.

PICTURE.

Three transactions of different lengths sit on a timeline. A dashed line marks $T_{\max }$ — the tallest one. Every real transaction fits under that line:

$T_{\text{transaction}}\le T_{\max }.$

• $T_{\text{transaction}}$ — the actual length of some real turn.
• $T_{\max }$ — the promise: no single turn ever runs longer than this.

This ceiling is what lets us later multiply instead of adding a messy list of different times.

---

Step 3 — The unlucky moment: "I just missed my turn"

WHAT. To find the worst wait for a chosen master — call it $M_i$ — we place it in the unluckiest possible situation.

WHY this exact moment? The pointer just passed seat $i$ one tick ago, at the very instant $M_i$ decided it wanted the bus. So $M_i$ must now wait for the pointer to travel the entire rest of the circle and come all the way back around to seat $i$.

PICTURE.

The pointer (red) sits just past $M_i$ (shaded). The green arc shows the journey the pointer must still make before it points at $M_i$ again. That arc is the full waiting time we are about to measure.

---

Step 4 — Counting exactly how many masters go ahead

WHAT. List the seats the pointer visits before returning to $M_i$.

WHY count them explicitly? Because the answer $N-1$ is earned by counting, not guessed. We literally enumerate the queue.

PICTURE.

Starting just past $M_i$, the pointer visits, in order:

$M_{(i+1)\mathrm{mod}N},M_{(i+2)\mathrm{mod}N},\dots ,M_{(i+N-1)\mathrm{mod}N}$

• $(i+1)\mathrm{mod}N$ — the seat right after $M_i$.
• $(i+N-1)\mathrm{mod}N$ — the seat right before $M_i$ (the last one ahead of us). Check: $(i+N-1)\mathrm{mod}N=(i-1)\mathrm{mod}N$, exactly the seat behind $M_i$. Good — that's the last competitor.

Count the list: the offsets run $1,2,\dots ,N-1$. That is exactly $N-1$ masters. This is where the $N-1$ comes from — it is the number of other seats in the circle. ($N$ seats total, minus your own = $N-1$ others.)

---

Step 5 — Replacing the sum with the ceiling: the bound appears

WHAT. Swap every unknown $T_{\text{transaction}}$ for the ceiling $T_{\max }$ from Step 2.

WHY are we allowed to? Because in Step 2 we proved every term is $\le T_{\max }$. Replacing each term in a sum by something at least as big can only make the sum bigger or equal — never smaller. So the result is a safe upper bound.

PICTURE.

The uneven bars of the true sum are all "lifted" to the same height $T_{\max }$. The total area only grows. Now every one of the $N-1$ bars has identical height, so adding them is just multiplication:

${\sum }_{j=1}^{N-1}{T}_{\text{transaction},(i+j)\mathrm{mod}N}\le \underset{\text{how many}}{\underbrace{(N-1)}}\times \underset{\text{each, at most}}{\underbrace{T_{\max }}}$

---

Step 6 — The edge cases (never leave a scenario unshown)

WHAT. Check the boundary values of $N$ and the "nobody else is asking" case.

PICTURE.

Case	What happens	Formula check
$N=1$	One master, alone. No competition.	$(1-1)\cdot T_{\max }=0$. Wait is zero — correct.
$N=2$	You and one rival.	$(2-1)\cdot T_{\max }=T_{\max }$ — wait for at most one other turn. Sensible.
Idle skip	Some seats ahead don't actually want the bus.	Arbiter skips silent seats immediately, so real wait is often far below the bound. The $\le$ still holds — it's a worst case, not the typical case.
Large $N$	Many masters.	Wait grows linearly: $O(N)$. This is round-robin's cost — fairness gets slow when the circle is big. Compare a [[Crossbar

---

The one-picture summary

The single figure threads the whole story: the pointer just passed $M_i$ (Step 3) → it must visit the $N-1$ seats ahead (Step 4) → each visit is capped at $T_{\max }$ (Step 2) → stacking $N-1$ caps gives the total (Step 5) → and the $N=1$ corner collapses the whole thing to zero (Step 6).

Recall Feynman retelling — say it like a story

Picture four friends sharing one swing. There's a rule: after you swing, the next friend in the circle gets the swing — a pointer just steps around the ring. Now suppose you just missed the pointer the moment you wanted a turn. How long, at worst, do you wait? You must let the pointer walk past everyone else first — that's the three other friends, i.e. $N-1$ of them. Each of them might take the longest allowed turn, $T_{\max }$. So your worst wait is three long turns: $(N-1)$ friends times $T_{\max }$ each. And if you were alone on the swing? $N=1$, so $(1-1)=0$ — no wait, which is obviously right. That's the entire formula, and it can never let you wait longer than it says.

Recall Quick self-check

Where does the $N-1$ come from? ::: It is the count of other masters ahead of you in the worst case — all $N$ seats minus your own. Why $T_{\max }$ and not the average transaction time? ::: We want a worst-case guarantee; only the ceiling is safe for real-time deadlines. What does $\mathrm{mod}N$ do in $(C+1)\mathrm{mod}N$? ::: It wraps the pointer from the last seat back to seat 0, closing the line into a circle. Why doesn't your own turn count in the wait? ::: Your turn is the reward at the end of the wait, not part of it. What does the formula give at $N=1$, and why is that the correct sanity check? ::: Zero — a lone master waits for nobody, so any correct formula must vanish here.

See also: Bus protocols and signals · Cache coherence · PCIe architecture · 6.3.01 Bus topologies and arbitration (Hinglish)