ALOHA and Slotted ALOHA — Computer Networks

Summary#

ALOHA is the protocol that started stochastic medium access. Designed by Norm Abramson at the University of Hawaii in 1970 to link terminals on different islands to a central computer over a shared radio channel, it answered the question “how do many stations share one medium without a central scheduler?” with the simplest possible idea: just transmit; if your frame collides with someone else’s, wait a random interval and try again. No listening, no slots, no coordination.

That recklessness has a famous cost. The maximum throughput of pure ALOHA is 1/(2e), about 18% of the channel — for every byte successfully delivered, four bytes’ worth of capacity is lost to collisions. Slotted ALOHA, a small change introduced in 1972 that forces every transmission to start at the boundary of a global time slot, doubles the maximum to 1/e, about 37%. The slotting math is the cleanest illustration in networking of how a tiny coordination primitive can double a system’s capacity.

Why it matters#

ALOHA is the ancestor of every random-access MAC protocol that followed: CSMA, CSMA/CD (classic Ethernet), CSMA/CA (Wi-Fi), and the backoff algorithms inside LoRaWAN, satellite IoT uplinks, and RFID inventory rounds. You cannot understand why Ethernet does what it does without first understanding what ALOHA got wrong and what each successor fixed. The 18%-and-37% throughput numbers are foundational interview material — anyone working on networking is expected to know them and the assumption set behind them (Poisson arrivals, infinite users, fixed frame size).

The protocol also stands as a worked example of a wider design pattern: when central coordination is impossible or expensive, accept collisions and recover. The same idea shows up in optimistic concurrency control in databases, lock-free data structures (compare-and-swap-and-retry), and even modern transactional protocols. ALOHA was first.

How it works#

Pure ALOHA#

The algorithm in three lines:

When a station has a frame to send, send it immediately.
Listen for an acknowledgement (from the central receiver) for some bounded time.
If no ACK arrives, assume collision. Wait a random interval and retry.

That’s it. No carrier sensing. No coordination. A station does not know whether anyone else is transmitting until the absence of an ACK tells it so.

   Station A:  ──[ frame A ]──────────────────────[ retry ]──
   Station B:  ────────[ frame B ]─────────────────────────
                       ◄── collision ──►
   Channel:    ─────[overlapping garbage]──────────────────

The vulnerable period for a frame of length T is 2T. Any other frame that starts within T before or T after will collide — before, because it will still be transmitting when ours starts; after, because ours is still transmitting when theirs starts. With Poisson-distributed frame arrivals at total rate G frames per T interval, the probability of no collision is e^(-2G), and throughput S = G · e^(-2G). Maximising gives G = 0.5 and S_max = 1/(2e) ≈ 0.184.

Slotted ALOHA#

The fix in one sentence: a global clock divides time into slots equal to one frame length, and every station may only start a transmission at a slot boundary.

                 |◄slot►|◄slot►|◄slot►|◄slot►|◄slot►|
   Station A:    │[frame A]   │            │[retry A] │
   Station B:    │            │[frame B]   │          │
   Station C:    │[frame C]   │            │[retry C] │
   Channel:      │  A and C collide        │   B ok   │
                 (collisions are full-frame or zero)

The vulnerable period shrinks from 2T to T — a collision happens only if another station picks the same slot, not the neighbouring ones. The math becomes S = G · e^(-G), peaking at G = 1 with S_max = 1/e ≈ 0.368. Exactly double.

The cost is global time synchronisation across all stations — modest by modern standards (GPS, NTP, or even a clock broadcast from the central station) but a genuine deployment requirement that pure ALOHA does not have.

Why those exact numbers#

The derivation is short enough to remember. Let frame arrivals be Poisson with mean G arrivals per slot. The probability of zero arrivals in a given window of length L slots is e^(-GL). For pure ALOHA the window is two slots (frame is vulnerable to anything starting one frame before or one frame after), so success probability is e^(-2G), throughput G · e^(-2G). For slotted ALOHA the window is one slot, success probability e^(-G), throughput G · e^(-G). Differentiate, set to zero — pure peaks at G = 0.5, slotted at G = 1.

The assumptions matter: infinite users (so individual back-offs don’t change the aggregate Poisson rate), fixed frame size, all-or-nothing collisions, and stations that retry blindly. Drop any of those and the math changes; CSMA’s improvement over ALOHA comes precisely from dropping the “transmit blindly” assumption (it adds carrier sensing).

Variants and trade-offs#

Pure ALOHA. Transmit when ready, retry on collision. Zero coordination cost. Maximum throughput 1/(2e) ≈ 18%. Works on any medium where carrier sensing is impossible or impractical (some satellite uplinks, where round-trip propagation delay exceeds frame length so sensing is useless anyway).

Slotted ALOHA. Same retry-on-collision idea, but transmissions start only on slot boundaries. Requires a global clock. Maximum throughput 1/e ≈ 37% — exactly double. The price for the doubling is one shared timing primitive.

Where ALOHA-family protocols live today:

Satellite IoT (Iridium, Inmarsat). Long propagation delay makes carrier sensing useless; slotted ALOHA or one of its descendants (CRDSA, IRSA) is the actual MAC for the random-access uplink channel.
LoRaWAN. Class A devices use pure ALOHA on the uplink — they transmit when they have data and don’t sense the channel. Network density caps are derived directly from ALOHA’s 18% throughput limit.
Cellular random-access channel. When a handset first connects to a base station (before it has a dedicated time/frequency assignment), it uses a slotted-ALOHA-style preamble on the RACH. Once associated, the base station’s scheduler takes over.
RFID inventory. Tag-collision arbitration in ISO/IEC 18000 and EPC Gen2 is slotted ALOHA with frame-size adaptation.

CSMA replaced ALOHA on wired and short-range wireless networks — listening before transmitting reduces the collision window dramatically. CSMA/CD added “stop if you detect a collision while transmitting” for classic Ethernet; CSMA/CA added “wait a random back-off plus a virtual carrier sense” for Wi-Fi, where collision detection during transmission is impossible.

Why does slotting only double throughput, not more?

The bottleneck under heavy load is the same in both protocols: too many stations want to transmit at the same time, and every collision wastes a full frame’s worth of channel time. Slotting eliminates partial-overlap collisions but not full-overlap collisions; the latter is still bounded only by how many independent retransmitting stations the channel sees. To do better than 1/e, you need a different primitive — carrier sensing (CSMA gets to about 50% on busy channels), exponential back-off (BEB shapes the arrival rate dynamically), or central scheduling (TDMA hits 100% if you can afford the coordination). Slotted ALOHA is the ceiling for “blind retransmit at slot boundaries.”

When this is asked in interviews#

ALOHA is a foundational question on any networking screen — expect “what’s the difference between pure ALOHA and slotted ALOHA?” or “what’s the maximum throughput of ALOHA and why?” early in a 60-minute loop. Strong answers carry the numbers (1/(2e) and 1/e), the assumption set (Poisson arrivals, infinite users), and the geographic motivation (radio across the Hawaiian islands, 1970).

Common follow-ups:

“Where do those throughput numbers come from?” — Poisson arrivals at total rate G per slot; vulnerable period is 2 slots for pure, 1 slot for slotted; throughput is G · e^(-2G) or G · e^(-G); peak at G = 0.5 or G = 1.
“Why was ALOHA designed for radio specifically?” — Carrier sensing across the Hawaiian islands was impractical (one station can’t hear another across the channel), so a transmit-and-pray protocol was easier than coordinating. The same constraint shows up on satellite links.
“What does CSMA add over ALOHA?” — Listen before you transmit. If the channel is busy, defer. The vulnerable period shrinks to the propagation-delay window, not the full frame length. Doubles or triples throughput depending on a = propagation / transmission.
“Where does slotted ALOHA still ship today?” — Cellular RACH preambles, LoRaWAN (Class A is actually pure ALOHA), RFID inventory rounds, satellite IoT uplinks. Anywhere central scheduling is too expensive or carrier sensing is physically impossible.