Здравствуйте, Sharov, Вы писали:

S>В том, что если мы хотим что-то решить синхронно, за фиксированный интервал времени, то вынужденны
S>оперировать вероятностями. Нету дискретных да\нет. В асинхронном случае мы по времени не ограничены
S>(т.е. ограничены, конечно, но никак в синх. случае).

Что мешает увеличить время в синхронном варианте до такой же величины, как в асинхронном?

Тут вопрос ставить иначе. Если мы гарантируем, что в месяц канал работает минимум 99.95% времени — это что-то изменит? Или по прежнему останется вероятностное согласование? Или же произойдет сходимость рядов?

Здравствуйте, gandjustas, Вы писали:

G>Это SLA, чтобы его посчитать можно было. А при проектировании проценты доступности стоит принимать как вероятность успешной передачи сообщения.

А если имеем гарантию доступности по времени именно — это что-то меняет?

G>Спроси у разработчиков TCP (они предпочитают получать подтверждение доставки)

Но не получают подтверждение доставки подтверждения доставки.

G>Не бывает, но бывает достаточно много ресурсов чтобы сделать вероятность потери сообщения настолько низкой, что она на практике не встретится.

А не произойдет ли сходимость рядов и 100% гарантия доставки, если гарантируем работоспособность определенный процент времени? Ведь на практике мы даем такую гарантию каналу — если канал навернется — то подключим другой, но точно не будем месяц сидеть оффлайн.

Здравствуйте, Shmj, Вы писали:

S>>Пол года — дается как раз на расследование. Т.е., допустим, если я уверен что отправитель деньги отправил, а я их не получил, начинаю заводить телегу по поиску денег. Пишу заявление, везу его в банк, они его читают, кладут в стопку, там оно лежит с месяц, пока до него не дойдет очередь. Ну т.е. пол года на расследование, куда дели деньги — вполне себе.

S>Ну это уже не проблема канала связи. Канал связи то никак не может не работать пол года, верно?
И да и нет. Я о том, откуда берутся пол года при гарантии перевода в 3 дня. А вот проблема ли это канала связи, зависит от того, что мы включаем в понятие "канал связи". Если рассмотреть непосредственно все, что находится между отправлением и получением перевода, то кажанные мешки вполне могут быть частью этого канала. В случае валютного перевода и ВК — неотэемлемая часть.

Здравствуйте, Shmj, Вы писали:

S>Тут вопрос ставить иначе. Если мы гарантируем, что в месяц канал работает минимум 99.95% времени — это что-то изменит? Или по прежнему останется вероятностное согласование? Или же произойдет сходимость рядов?

Это меняет условие задачи. Здесь уже можно говорить о гарантированной доставке (за некоторое ненулевое время). А с гарантированной доставкой и задачи о генералах нет, т.е. она решена по условию.

Здравствуйте, samius, Вы писали:

S>Это меняет условие задачи. Здесь уже можно говорить о гарантированной доставке (за некоторое ненулевое время). А с гарантированной доставкой и задачи о генералах нет, т.е. она решена по условию.

Но ведь когда на практике говорят, что канал доступен не менее пусть даже 95% времени в месяц (это низкий показатель — но правдивый) — это есть гарантированная доставка?

Если действовать по моей схеме, то точно можно вычислить срок, после которого состояние на 100% согласовано. Делаем так:

1. Генерал 1 отправляет данные.
2. Генерал 2 получает и подтверждает в ответ (не зная доставлен ли его ответ).
3. Генерал 2 ждет n времени и если не было повторных отправок данных — имеет 100% гарантию согласованности. Его уверенность основана на том, что всего 5% времени в месяц канал не работает — а уже прошло больше этого времени в худшем раскладе.

Все верно?

И далее — если канал доступен всего 1% в месяц/год — то сойдется ли ряд и получим ли мы гарантию 100% доставки когда-либо?

Здравствуйте, Shmj, Вы писали:

S>Здравствуйте, samius, Вы писали:

S>>Это меняет условие задачи. Здесь уже можно говорить о гарантированной доставке (за некоторое ненулевое время). А с гарантированной доставкой и задачи о генералах нет, т.е. она решена по условию.

S>Но ведь когда на практике говорят, что канал доступен не менее пусть даже 95% времени в месяц (это низкий показатель — но правдивый) — это есть гарантированная доставка?
Конечно. Но это не значит, что пакет будет доставлен, это значит, что тот, кто гарантировал доступность, ответит за недоступность в некоторой форме. Или сделает вид, что ничего не было. Как в банке. Перевод 3 дня. Но если не переведем — пишите заявление, рассмотрим за пол года.

S>Если действовать по моей схеме, то точно можно вычислить срок, после которого состояние на 100% согласовано. Делаем так:

S>1. Генерал 1 отправляет данные.
S>2. Генерал 2 получает и подтверждает в ответ (не зная доставлен ли его ответ).
S>3. Генерал 2 ждет n времени и если не было повторных отправок данных — имеет 100% гарантию согласованности. Его уверенность основана на том, что всего 5% времени в месяц канал не работает — а уже прошло больше этого времени в худшем раскладе.

S>Все верно?
Верно, но избыточно. Если мы закладываем в условие гарантированную доставку за некоторый период времени (пусть это будет одно сообщение в месяц, не важно), то минимальный набор сообщений для решения задачи о генералах становится равен одному сообщению с отсрочкой атаки на время, превышающее период гарантированной доставки.

S>И далее — если канал доступен всего 1% в месяц/год — то сойдется ли ряд и получим ли мы гарантию 100% доставки когда-либо?
Зависит от гарантий. Если гарантия в условии задачи, то мы исходим из этой гарантии. Если как в банке или аптеке — то цена гарантии невелика и мы вместо пакета можем получить зуб того, кто гарантию давал. В лучшем случае. И потом отдать этот зуб генералам в качестве компенсации за проигранную войну. Даже если мы по иску слупим компенсацию за недоставленный пакет, вряд ли это поможет генералам.

Здравствуйте, samius, Вы писали:

S>Конечно. Но это не значит, что пакет будет доставлен, это значит, что тот, кто гарантировал доступность, ответит за недоступность в некоторой форме. Или сделает вид, что ничего не было. Как в банке. Перевод 3 дня. Но если не переведем — пишите заявление, рассмотрим за пол года.

Вопрос такой — сходится ли ряд?

Если по моему алгоритму, который описал выше:

1. Генерал 1 отправляет данные.
2. Генерал 2 получает и подтверждает что получил в ответ (не зная доставлен ли его ответ).
3. Генерал 2 ждет n времени и если не было повторных отправок данных — имеет 100% гарантию согласованности. Его уверенность основана на том, что всего 5% времени в месяц канал не работает — а уже прошло больше этого времени в худшем раскладе.

Давайте так. Пусть даже теряется 5% пакетов. Запрос имеем возможность делать раз в 1 сек.

Если на шаге 3 прошла 1 сек. — значит, с вероятностью 5% — пакет потерялся. Но с вероятностью 95% — генерал 1 получил подтверждение. Дальше — на второй секунде как изменяется вероятности? По-моему тут сходимость ряда происходит?

Похоже на Ахиллес и черепаха.

Здравствуйте, Shmj, Вы писали:

S>Здравствуйте, samius, Вы писали:

S>>Конечно. Но это не значит, что пакет будет доставлен, это значит, что тот, кто гарантировал доступность, ответит за недоступность в некоторой форме. Или сделает вид, что ничего не было. Как в банке. Перевод 3 дня. Но если не переведем — пишите заявление, рассмотрим за пол года.

S>Вопрос такой — сходится ли ряд?

S>Если по моему алгоритму, который описал выше:

S>

S>1. Генерал 1 отправляет данные.
S>2. Генерал 2 получает и подтверждает что получил в ответ (не зная доставлен ли его ответ).
S>3. Генерал 2 ждет n времени и если не было повторных отправок данных — имеет 100% гарантию согласованности. Его уверенность основана на том, что всего 5% времени в месяц канал не работает — а уже прошло больше этого времени в худшем раскладе.

S>Давайте так. Пусть даже теряется 5% пакетов. Запрос имеем возможность делать раз в 1 сек.

S>Если на шаге 3 прошла 1 сек. — значит, с вероятностью 5% — пакет потерялся. Но с вероятностью 95% — генерал 1 получил подтверждение. Дальше — на второй секунде как изменяется вероятности? По-моему тут сходимость ряда происходит?

S>Похоже на Ахиллес и черепаха.

Ну и главное — если таки имеем гарантию, что не 95% пактов доходит а что канал доступен минимум 95% времени в месяц — это уже иная ситуация.

Здравствуйте, Shmj, Вы писали:

S>Вопрос такой — сходится ли ряд?

S>Если по моему алгоритму, который описал выше:

S>

S>1. Генерал 1 отправляет данные.
S>2. Генерал 2 получает и подтверждает что получил в ответ (не зная доставлен ли его ответ).
S>3. Генерал 2 ждет n времени и если не было повторных отправок данных — имеет 100% гарантию согласованности. Его уверенность основана на том, что всего 5% времени в месяц канал не работает — а уже прошло больше этого времени в худшем раскладе.

S>Давайте так. Пусть даже теряется 5% пакетов. Запрос имеем возможность делать раз в 1 сек.

S>Если на шаге 3 прошла 1 сек. — значит, с вероятностью 5% — пакет потерялся. Но с вероятностью 95% — генерал 1 получил подтверждение. Дальше — на второй секунде как изменяется вероятности? По-моему тут сходимость ряда происходит?

S>Похоже на Ахиллес и черепаха.

Эти рассуждения избыточны, т.к. на уверенности о том, что канал не работает не более 5% времени в месяц, можно построить другой канал, время гарантированной доставки которого будет известно и примерно равно 35 часам. С таким условием обоим генералам достаточно всего одного сообщения. Ряд не нужен.

Но если ставить в зависимость вероятность доствки от даты и времени (откладывать от начала месяца), то нам придется отслеживать время недоступности канала в течение месяца, а для этого надо посылать запросы и получать ответы каждую дельту времени всего лишь для того, что бы оценить вероятность доставки очередного сообщения.

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

Здравствуйте, igor-booch, Вы писали:

IB>Я не специалист в области банковских транзакций, но интуиция подсказывает следующее.
IB>Есть координатор распределенных транзакцией.
IB>Если он увидел, что какой-то из банков не выполнил свою часть транзакции,
IB>он даёт другому банку (который часть транзакции выполнил) команду на откат транзакции.
Что команда на откат, что команда на фиксацию, обе команды требуют доставки сообщения, что возвращает нас к новой итерации задачи о генералах.

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

IB>Да, можем потерять время, но при банковских переводах это случается редко и поэтому допустимо.
Просто банковская гарантия — не абсолютная величина. Речь всего лишь о том, что 99.9% переводов происходят за первые 3 дня. А если что-то пойдет не так, то даже репутация банка не пострадает.

Здравствуйте, Shmj, Вы писали:
S>Можно ли решить средствами 1 канала, который доступен 99.95% времени гарантированно за определенный срок (гарантировать что синхронизация пройдет не позже чем n времени в худшем случае)?
Очевидно, что нет.
Можно нарисовать график вероятности синхронизации от количества попыток.
Он будет очень быстро стремиться к 100%. Даже если канал теряет половину сообщений, десят попыток уже дадут 98.9% шансов успеха.
Для канала, который теряет 1% сообщений, за три повтора мы получаем шансы 99.9999, что превышает любые практически используемые SLA.
С точки зрения математиков, мы имеем всё ещё негарантированную доставку. Даже после бесконечного количества попыток.
С точки зрения инженеров, у нас есть алгоритм, который быстро снижает шансы провала.

Здравствуйте, Sinclair, Вы писали:

S>>Можно ли решить средствами 1 канала, который доступен 99.95% времени гарантированно за определенный срок (гарантировать что синхронизация пройдет не позже чем n времени в худшем случае)?
S>Очевидно, что нет.
S>Можно нарисовать график вероятности синхронизации от количества попыток.

Если мы имеем не вероятность доставки пакета а гарантию доступности по времени — тогда другая оценка. А это ближе к практике.

Здравствуйте, Shmj, Вы писали:

S>Вопрос у меня вот в чем. Если я перевожу средства со счета в одном банке на счет в другом банке (очевидно у них разные СУБД и нельзя использовать локальную транзакцию). Канал передачи не надежен на 100% — очевидно — это глобальная сеть и сбои могут быть.

Эти задачи не эквивалентны.
Я не специалист в межбанковских переводах, но если очень упрощенно:
Клиент переводит деньги из банка A в банк B:
1. Сумма перевода блокируется на счету банка А
2. Банк A посылает сообщение банку B
3а. Банк B не получает сообщение от банка А: ничего не происходит, клиент страдает, goto 6
3b. Банк B получает сообщение от банка А: банк B кредитует счет клиента, клиент доволен, может тратить деньги со счета в банке B
4. Банк B посылает сообщение банку A
5a. Банк A не получает сообщение от банка B: ничего не происходит, деньги остаются заблокированы, клиенту пофиг, goto 6
5b. Банк A получает сообщение от банка B: банк А дебетует счет клиента на заблокированную сумму

6. Reconciliation procedure: банк А всеми способами пытается достучаться до банка B, в предельном случае в ход идут факсы, звонки, курьеры. Пока банк А не получит от банка B тот или иной ответ деньги остаются заблокированы. В совсем предельном случае банк B идет к регулятору. Ну и, конечно, банк страхует свои операционные риски. Поэтому есть еще запасное войско на всякий случай, если один из генералов со всем войском забухал и укатил на курорт.

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

Здравствуйте, Shmj, Вы писали:

S>Но тут какая проблема. Откуда банк 2 знает что банк 1 получил успешный ответ? Вдруг не получил? Значит банк 2 должен сделать запрос к банку 1. Но это очень похоже на задачу двух генералов этих, которая вроде как неразрешима.

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

Пример:
1) Клиент в банке А хочет перевести деньги клиенту в банке Б
2) банк А резервирует на счету клиента эту сумму и отправляет сообщение банку Б с ключом К1
3) банк Б получает это сообщение и резервирует на счету получателя заявленную сумму, проводит какие-то другие операции (других клиентов) в назначенное время отправляет сообщение банку А, подписанное ключом К1 и своим ключом К2
4) Банк А получает сообщение, видит что оно подписано K1, а значит все операции посланные в предыдущем сообщении проведены. Он закрывает резерв на счёте-отправителе. Когда приходит время следующего обмена информацией он отправляет пакет подписанный К2 и ключом К3
5) Банк Б получает сообщение, видит что оно подписано ключом К2 и завершает транзакцию.

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

Здравствуйте, samius, Вы писали:

S>>По идее эта задача считается неразрешимой.
S>Не считается. Доказано, что она неразрешима. Или есть вопросы к доказательству?

Да, есть вопросы.

Допустим вы — генерал N1.
Вы отослали гонца с сообщением: "Атакуем завтра в девять часов утра".
Получили ответ: "Я получил Ваше сообщение и атакую завтра в девять часов утра".

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

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

Послали четвёртого гонца с сообщением: "Окончательно подтверждаю: атакуем завтра в девять часов утра".


С точки зрения генерала N2 ситуация выглядит так: получено три сообщения:
"Атакуем завтра в девять часов утра".
"Подтверждаю: атакуем завтра в девять часов утра".
"Вторично подтверждаю: атакуем завтра в девять часов утра".
Сообщение "Окончательно подтверждаю: атакуем завтра в девять часов утра" не получено.

>>----------------------------------------------------------------------------------------------------------------------------------------------------
Есть ли причина у генерала N2 не начинать атаку? С его точки зрения (с точки зрения генерала N2) известно, что генерал N1 получил следующие сообщения:
(Т.е. генералу N2 известно, что генерал N1 получил следующие сообщения):
"Я получил Ваше сообщение и атакую завтра в девять часов утра".
"В ответ на ваше подтверждение, я со свой стороны подтверждаю, что атакую завтра в девять часов утра".

У генерала N2 нет оснований думать, что у генерала N1 есть основания для того, чтобы отложить атаку. => генерал N2 атакует.

>>----------------------------------------------------------------------------------------------------------------------------------------------------
Есть ли причина у генерала N1 не начинать атаку? С его точки зрения (с точки зрения генерала N1) известно, что генерал N2 получил следующие сообщения:
(Т.е. генералу N1 известно, что генерал N2 получил следующие сообщения):
"Атакуем завтра в девять часов утра".
"Подтверждаю: атакуем завтра в девять часов утра".
"Вторично подтверждаю: атакуем завтра в девять часов утра".

У генерала N1 нет оснований думать, что у генерала N2 есть основания для того, чтобы отложить атаку. => генерал N1 атакует.

Итог: генералы договорились и атакуют.

=========================================================================================================================================================

Теперь, что не так с доказательством:

Предположим, что есть некоторая последовательность сообщений, доставленных или перехваченных, которая позволяет обоим генералам гарантированно согласовать время начала штурма. В таком случае существует некоторое минимальное подмножество таких сообщений. Рассмотрим последнее сообщение в этой минимальной последовательности. Так же, как и любое другое сообщение, оно может быть перехвачено. Если оно не будет доставлено, то условие согласованности действий не выполнится, и один из генералов (вероятнее всего, получатель) отложит свою атаку. С точки зрения другого генерала, алгоритм обмена будет соблюден, и он начнет штурм в полной уверенности, что будет поддержан. Таким образом, при использовании заведомо правильного алгоритма, создается ситуация, в которой один генерал штурмует город, а другой — нет. Это противоречит нашему допущению о существовании алгоритма решения задачи.

Как видно из примера приведённого выше не важно было ли доставлено последнее сообщение или нет, так как оно не влияет на решение второго генерала. Это было достигнуто за счёт избыточности сообщений: условие согласованности действий выполнится, так как минимальное подмножество сообщений включает в себя последнее сообщение не обязательное к доставке.

Здравствуйте, B0FEE664, Вы писали:

BFE>Как видно из примера приведённого выше не важно было ли доставлено последнее сообщение или нет, так как оно не влияет на решение второго генерала. Это было достигнуто за счёт избыточности сообщений: условие согласованности действий выполнится, так как минимальное подмножество сообщений включает в себя последнее сообщение не обязательное к доставке.

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

Двухфазный протокол и блокчейн.

Двухфазный протокол именно потому двухфазный, что трёх фаз не нужно.

А блокчейн всегда рекламировался как решение задачи о генералах.

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>Двухфазный протокол и блокчейн.
Бегемоты и крокодилы!

ЭФ>Двухфазный протокол именно потому двухфазный, что трёх фаз не нужно.
трёх фаз не нужно для чего?

ЭФ>А блокчейн всегда рекламировался как решение задачи о генералах.
И вы поверили рекламе?

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

И вообще, причём тут блокчейн? Блокчейн очень чувствителен к количеству нод, а количество нод при плохой связи вообще никогда не будет подсчитано корректно.