Самым большим препятствием в работе ALOHAnet были помехи. Случалось, что две станции начинали передачу одновременно, непреднамеренно заглушая сигналы друг друга. (Это также нередко происходит и в диалогах между людьми.) Если обе станции будут повторно передавать сигналы, чтобы все-таки доставить свои сообщения, они рискуют навсегда застрять в постоянных взаимных помехах. Ясно, что протокол ALOHAnet должен был урегулировать сообщения конкурирующих сигналов, чтобы они уступали канал друг другу и приносили результат.
Первое, что отправитель в этом случае должен сделать, это «нарушить симметрию». Любому пешеходу знакома ситуация, когда двое идущих навстречу человека, пытаясь разойтись, принимают один вправо, другой влево, в итоге синхронно отклоняются в одну и ту же сторону, а потом, пытаясь исправить дело, столь же синхронно делают шаг в другую. Схожая ситуация возникает, когда оба участника диалога вдруг замолкают, уважительно уступая право голоса другому, а затем одновременно начинают говорить; или когда на перекрестке два автомобиля сперва останавливаются, уступая друг другу, а затем синхронно газуют. Это та сфера, где рандомизация имеет большое значение. Более того, существование сетей было бы невозможным без нее.
Простейший способ нарушить симметрию – заставить каждую станцию работать по принципу подбрасывания монетки: орел – ретрансляция, решка – пропуск хода, а потом ретрансляция. Несомненно, одна из них справится через какое-то время. Но это хорошо работает, если отправителей всего два. А если будет три одновременных сигнала? А четыре? Шанс получить хотя бы один пакет будет в этом случае один к четырем (после чего все равно останутся еще три конфликтующие станции и еще больше конкурирующих сигналов, поступающих в одно и то же время). Число конфликтов будет расти, и рано или поздно пропускная способность сети может просто рухнуть. В отчете по ALOHAnet 1970 года говорится, что едва средний коэффициент загруженности радиоволн превысит границу в 18,6 %, как «канал становится нестабильным… и среднее число повторных передач становится неограниченным». Что не есть хорошо.
Так что же делать? Как создать систему, которая сможет избежать этой участи?
Важным открытием оказалось увеличение средней задержки после каждого следующего провала, в частности удвоение предполагаемой отсрочки перед повторной передачей. Таким образом, после первоначального провала отправитель случайным образом повторит отправку через один или два хода; после второй неудачи он повторит попытку через 1–4 хода; третья подряд ошибка будет означать задержку в 1–8 ходов и т. д. Этот оригинальный подход позволяет сети принимать теоретически любое количество конкурирующих сигналов. Поскольку максимальная длина отсрочки растет в геометрической (экспоненциальной) прогрессии (2, 4, 8, 16…), этот метод получил название «