Summary

  • On the shared experimental Ethernet, a collision meant that more than one station had transmitted within the vulnerable interval. It revealed contention, but not the other station’s identity, a centrally chosen winner or a reservation for the next slot.
  • The source controller stopped, updated its collision history and independently selected a random retransmission interval. Repeated collisions widened the mean wait; passing traffic caused further deference before another attempt.
  • Robert Metcalfe and David Boggs described a distributed system that needed cooperation as well as probability. Its lesson is not that randomness guarantees fairness, but that a small common detection rule can support local decisions whose evidence and limits stay separate.

The collision that elected nobody

Picture two source controllers at opposite points on one coaxial cable. Both sense an idle Ether. Both start a packet before the first signal can reach the other. Each then compares what it is sending with what the cable carries and detects interference. The shared fact is clear: this attempt cannot continue as an intact transmission.

Everything that follows is easier to understand if that fact is kept narrow. The collision does not contain the address of the competing source. It does not say which packet arrived first in some universal order. It does not hand the next interval to the station that detected the event earliest. On a distributed medium with propagation delay, there is no referee hiding inside the wire.

The 1976 paper by Robert Metcalfe and David Boggs describes a broadcast, multi-access network with distributed control among stations. “Distributed” did not mean ruleless. A station had to detect interference, terminate the damaged transmission, and enter a retransmission procedure. The common medium supplied evidence of conflict. The controller turned that evidence into its own future decision.

This distinction prevents a familiar reporting error. A collision counter is not a queue of losers waiting in order. Ten collision events do not prove that ten distinct stations competed, and a lower count does not prove preferential service. The counter is evidence about attempts on a particular contention domain under particular timing assumptions. Identity, waiting time and eventual receipt require other observations.

One slot, three possible outcomes

The original analysis bounded a slot by the maximum interval between starting a transmission and discovering a collision: one end-to-end round-trip propagation delay on the shared medium. Under load, a contention slot has three useful outcomes. Nobody transmits and the slot is empty. More than one station transmits and the slot collides. Exactly one transmits and acquires the Ether for its packet.

The third result is successful acquisition, not ownership of a future schedule. Once the packet ends, other stations contend again. Nor is acquisition proof of end-to-end delivery. The paper explicitly treats Ethernet as probabilistic and notes that packets can be lost through interference, noise, an inactive receiver or purposeful discard. Higher-level protocols must therefore work with high-probability reception, not a link-layer certificate of application processing.

The boundary matters operationally. A source can record carrier sense, collision detection and completion of its own transmission. A receiver can record frame validation and local delivery. An application can acknowledge work. Those are three different receipts. Promoting the first into the third creates confidence without evidence.

The distributed retry

After a collision, the source controller generates a new random retransmission interval from its updated collision count. Metcalfe and Boggs describe doubling the mean delay after each collision, then deferring to any passing packet before retrying. Their paper calls the procedure a heuristic approximation to Binary Exponential Backoff.

The important action is not simply “wait longer.” It is to enlarge the space from which separate stations make independent choices. If both stations always waited the same fixed interval, they could remain synchronized and collide again. Random choice breaks that correlation most of the time. Increasing the range under repeated contention reduces the chance that a crowded set keeps selecting the same moment.

Later IEEE 802.3 text makes a particular truncated binary form explicit: after collision and the jam sequence, a station chooses a uniformly distributed integer number of slot times; the exponent grows with the attempt number up to a cap, and transmission eventually succeeds or reaches the attempt limit. The interpretation also asks implementations to minimize correlation between stations’ random numbers. These later parameters clarify the standardized mechanism, but should not be projected backwards as though every constant appeared unchanged in the 1973 prototype.

Metcalfe’s oral history locates collision detection partly in hardware and the backoff logic in microcode with hardware assistance. That recollection helps explain where the decision lived. It remains first-person testimony, not a neutral benchmark and not a substitute for the published algorithm.

Cooperation was part of the protocol

Probability alone did not secure equitable use. The 1976 paper says a degree of cooperation was required. A station could usurp the Ether by refusing to enlarge its retransmission interval under load, or by sending packets so large that others rarely received an opportunity. The experimental system prohibited both practices.

That observation is more consequential than the comforting phrase “the network sorts itself out.” Every station owns a local timer, but every station also has the ability to violate the shared expectation. The cable can expose overlapping signals; it cannot inspect a controller’s motive or compel honest randomness. Fairness is therefore partly a property of conformance, packet rules and observed outcomes—not an automatic gift from decentralization.

The patent record also resists a single-hero story. It names Robert M. Metcalfe, David R. Boggs, Charles P. Thacker and Butler W. Lampson as inventors, and describes interference detection followed by a randomly chosen delay weighted by repeated collisions. The historical lineage also includes ALOHAnet, PARC builders and the standards community. ACM’s Turing Award citation recognizes Metcalfe’s invention, standardization and commercialization of Ethernet while identifying Boggs as a co-inventor of the PARC system. Accurate attribution strengthens the mechanism; it does not diminish it.

What the evidence can and cannot prove

A defensible reconstruction needs a sequence rather than one counter. First establish the topology: was this actually one shared half-duplex collision domain, and what was its propagation bound? Then establish the attempt: which source started, what carrier state did it observe and when? Next record collision detection, abort or jam behavior, the updated attempt count, the random slot selection and any deference to intervening traffic. Finally separate the outcome of medium acquisition from receiver acceptance and higher-layer acknowledgement.

This chain can show that a station followed the contention procedure. It cannot prove that every peer used an independent random generator, that waiting time was equal, that no station starved, or that the application received the payload. Statistical observation across stations and time is needed for distributional claims. Receiver and application receipts are needed for delivery claims.

The historical boundary is equally important. Modern Ethernet usually connects point-to-point links through switches and runs full duplex. Such a link has no shared coaxial collision contest of the kind analysed here. A rising collision counter on equipment believed to be full duplex is more likely a prompt to inspect media, counters, mode assumptions or duplex mismatch than evidence that classic contention is working as designed.

Sources