Проблема двух генералов

Представим ситуацию: есть 2 генерала, которые планируют напасть на город и находятся на расстоянии друг от друга. Им нужно договориться о совместном нападении так, чтобы они напали одновременно, иначе ничего не получится и армии просто проиграют.

Причём путь гонца лежит через стены этого города. Так что если его заметят, то его убьют, и другая сторона не узнает о сообщении.

Как же им договориться? А дело в том, что ответа на этот вопрос нет. И вот почему:

1) Гонец не дошёл и его убили по пути ко второму генералу

В таком случае первый генерал подумает, что гонец дошёл и нападёт. В то время как второй генерал ничего не узнает о гонце, и останется ждать сообщения. Первый генерал в одиночку не может справиться с осадой города и его армия погибает, а это означает невозможность победить.

Что же надо сделать, чтобы избежать такого исхода? Всё просто с первого взгляда. Давайте пошлём гонца обратно, и пусть он сообщит о том, что доставил своё сообщение, тогда путаницы не будет, верно же?

2) Гонец дошёл до второго генерала успешно, но его убили по пути назад

Хорошо, что же с первым генералом? Он теперь не нападет, т.к. не получил гонца назад, а второй генерал нападает, т.к. теперь уже он думает, что сообщение доставлено. Снова такая же ситуация, нападает только один из них, город успешно обороняется – война проиграна.

Вывод

Что же делать? Отправить назад гонца, который скажет уже второму генералу, что сообщение о доставке первого сообщения доставлено? Будет такая же ситуация. 

Теперь первый генерал знает, что сообщение доставлено, НО он всё равно не знает, будет ли второй генерал атаковать. Почему? Потому что второй генерал будет атаковать только в том случае, если получит наше подтверждение о подтверждении первого сообщения (или просто второе подтверждение). Если гонец снова умер посередине, то второй генерал атаковать не будет, а первый будет, т.к. снова думает, что всё ок.

И на самом деле это не решаемая проблема в том виде, в котором она поставлена! Сколько бы мы сообщений не отправляли, в каком бы формате – хоть одновременно по сто сообщений с двух сторон, У НАС НЕТ ГАРАНТИЙ.

Как это мешает нам в реальной жизни?

Это та проблема, с которой постоянно сталкивается вся электроника.

Мы просто не можем быть уверены, что данные дошли от клиента до сервера. Мобильное приложение должно выполнить свои действия (показ об успешной покупке, и т.п.), когда будет уверенно, что сервер получил данные, а сервер же в свою очередь как-то должен надёжно оповестить устройство о том, что данные были приняты.

Это поведение заложено в протоколе TCP, который потом используется в HTTP. 

Давайте подумаем как. Что если просто перепосылать запрос, если мы не получили ack (ответ от сервера)?

Двойное выполнение запроса

Запрос просто выполнится несколько раз. А это может быть важная операция, например, списание денег! 

И вот как решили эту проблему. Запросы действительно перепосылаются клиентом, если не было получено подтверждение, НО к запросу добавляется специальный айдишник, который сервер кеширует.  И если пришёл запрос с айдишником, который уже был замечен ранее, сервер просто отдаёт закешированный ответ, не делая никакой реальной работы. 

На самом деле, нет никаких айдишников в самих запросах, они есть на более низком уровне – на уровне отправки пакетов, но суть работы примерно такая же. 

И айдишник этот генерируется не случайно – так можно было бы сделать коллизию, используется так называемый nonce. Number only used once – обычно он начинается с ноля при соединении с сервером и к нему при каждой новой отправке добавляют по единице.