Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

Когда что-то в этой словесной баталии идет не так, мы нередко недоумеваем. Как говорит блогер и разработчик программного обеспечения Тайлер Трит:

В задаче, с которой сталкиваются византийские генералы, напоминает он нам, «дело не в сложности разработки, а в невозможности результата».

Ранние сетевые исследования, замечает Винт Серф, основывались на предположении, что «мы можем построить надежную сеть». Но, с другой стороны, «интернет был основан на предположении, что сеть вовсе не обязательно должна быть надежной, и приходилось осуществлять непрерывные повторные передачи для возобновления соединения».

По иронии судьбы, одно из немногих исключений – это передача человеческого голоса. Голосовые коммуникации в режиме реального времени, такие как Skype, например, обычно не используют протокол TCP, который лежит в основе большей части интернета. На заре сетевых коммуникаций исследователи обнаружили, что передавать человеческий голос, используя надежные, устойчивые протоколы со всеми их АСК и повторными передачами утерянных данных, убийственно. Люди сами обеспечивают «ошибкоустойчивость». Как объясняет Серф, «в случае с речью, если пакет теряется, вы просто говорите: "Повтори еще раз, пожалуйста, я что-то пропустил"».

По этой причине услуги телефонной связи, которые автоматически снижают фоновые помехи до тишины, оказывают своим абонентам медвежью услугу. Фоновые помехи являются свидетельством того, что звонок еще не прерван, и любое молчание – это осознанный выбор другой стороны. Когда их нет, приходится учитывать возможность прерывания соединения и постоянно просить подтверждения, что связь еще есть. Поводом для беспокойства во всех протоколах пакетной коммутации также служит тот факт, что любое средство передачи основывается на асинхронном режиме очередности – будь то написание писем, текстовых сообщений или пробные переписки на сайтах знакомств. Каждое сообщение может быть последним, и зачастую невозможно определить, взял ли собеседник паузу для ответа или давно уже закончил разговор.

Так как же обращаться с человеком (или с компьютером), если общение столь ненадежно?

Первый вопрос заключается в том, сколько времени должно пройти в ожидании ответа, прежде чем мы можем смело констатировать сбой. Отчасти это зависит от вида самой сети: в телефонном разговоре наше волнение – вопрос нескольких секунд, в переписке по электронной почте – нескольких дней, а в обычном почтовом сообщении – нескольких недель. Чем длиннее путь от отправителя к получателю и обратно, тем дольше можно не обращать внимания на молчание – и тем больше информации может потенциально находиться в стадии доставки, прежде чем отправитель понимает, что что-то не так. В сетевой работе тот факт, что стороны могут должным образом корректировать свои ожидания с учетом своевременности реагирования, является ключевым моментом правильного функционирования системы.

Второй же вопрос, разумеется, заключается в том, что нам нужно делать, когда мы обнаруживаем сбой.

Мы рассчитываем, что все современные устройства будут беспроводными, даже если в этом нет необходимости: мышка и клавиатура, например, подключены к компьютеру по беспроводному соединению, хотя находятся в паре дюймов друг от друга. Но изначально беспроводные сети возникли именно по необходимости, там, где провода не могли бы справиться с задачей: на Гавайях. В конце 60-х – начале 70-х годов Норман Абрамсон в Гавайском университете в Гонолулу пытался связать между собой семь университетских кампусов и несколько научно-исследовательских институтов, расположенных на четырех островах за сотни миль друг от друга. Он додумался до реализации пакетной коммутации с помощью радио, а не телефонной системы, соединив острова цепью приемников и передатчиков. Эта сеть впоследствии получила название ALOHAnet.

Самым большим препятствием в работе ALOHAnet были помехи. Случалось, что две станции начинали передачу одновременно, непреднамеренно заглушая сигналы друг друга. (Это также нередко происходит и в диалогах между людьми.) Если обе станции будут повторно передавать сигналы, чтобы все-таки доставить свои сообщения, они рискуют навсегда застрять в постоянных взаимных помехах. Ясно, что протокол ALOHAnet должен был урегулировать сообщения конкурирующих сигналов, чтобы они уступали канал друг другу и приносили результат.

Первое, что отправитель в этом случае должен сделать, это «нарушить симметрию». Любому пешеходу знакома ситуация, когда двое идущих навстречу человека, пытаясь разойтись, принимают один вправо, другой влево, в итоге синхронно отклоняются в одну и ту же сторону, а потом, пытаясь исправить дело, столь же синхронно делают шаг в другую. Схожая ситуация возникает, когда оба участника диалога вдруг замолкают, уважительно уступая право голоса другому, а затем одновременно начинают говорить; или когда на перекрестке два автомобиля сперва останавливаются, уступая друг другу, а затем синхронно газуют. Это та сфера, где рандомизация имеет большое значение. Более того, существование сетей было бы невозможным без нее.

Простейший способ нарушить симметрию – заставить каждую станцию работать по принципу подбрасывания монетки: орел – ретрансляция, решка – пропуск хода, а потом ретрансляция. Несомненно, одна из них справится через какое-то время. Но это хорошо работает, если отправителей всего два. А если будет три одновременных сигнала? А четыре? Шанс получить хотя бы один пакет будет в этом случае один к четырем (после чего все равно останутся еще три конфликтующие станции и еще больше конкурирующих сигналов, поступающих в одно и то же время). Число конфликтов будет расти, и рано или поздно пропускная способность сети может просто рухнуть. В отчете по ALOHAnet 1970 года говорится, что едва средний коэффициент загруженности радиоволн превысит границу в 18,6 %, как «канал становится нестабильным… и среднее число повторных передач становится неограниченным». Что не есть хорошо.

Так что же делать? Как создать систему, которая сможет избежать этой участи?

Важным открытием оказалось увеличение средней задержки после каждого следующего провала, в частности удвоение предполагаемой отсрочки перед повторной передачей. Таким образом, после первоначального провала отправитель случайным образом повторит отправку через один или два хода; после второй неудачи он повторит попытку через 1–4 хода; третья подряд ошибка будет означать задержку в 1–8 ходов и т. д. Этот оригинальный подход позволяет сети принимать теоретически любое количество конкурирующих сигналов. Поскольку максимальная длина отсрочки растет в геометрической (экспоненциальной) прогрессии (2, 4, 8, 16…), этот метод получил название «экспоненциальная задержка».