Вопрос у меня вот в чем. Если я перевожу средства со счета в одном банке на счет в другом банке (очевидно у них разные СУБД и нельзя использовать локальную транзакцию). Канал передачи не надежен на 100% — очевидно — это глобальная сеть и сбои могут быть.
Но существует же алгоритм, благодаря которому имеем 100% достоверность, что действия будут согласованы и на 100% деньги не исчезнут одновременно с двух счетов а так же не удвоятся, не смотря на то что канал связи не надежен?
По идее так. Даю команду перевести 100 руб. на другой счет. Банк 1 сначала создает запись о переводе, уменьшает сумму на счете на 100 руб. Потом пытается связаться с внешним сервисом (пусть там другого банка или нац. банка — не важно) и при успешном ответе от него — уже фиксирует транзакцию. Если ответа нет — то делает запросы до победного конца (деньги будет блокировать, пока не внесется ясность).
Но тут какая проблема. Откуда банк 2 знает что банк 1 получил успешный ответ? Вдруг не получил? Значит банк 2 должен сделать запрос к банку 1. Но это очень похоже на задачу двух генералов этих, которая вроде как неразрешима.
Или же наличие ответственного в принятии решений как бы делает задачу разрешимой?
Вопрос вот в чем. Можно ли как-то таки эту задачу генералов решить не вероятностно (что согласованность получена с большой вероятностью) а точно? Поможет ли введение ответственного в принятии решений? И таки перевод средств из одной системы в другую (когда нет локальных транзакций, скажем так) по ненадежному каналу связи — решен вероятностно или же существует точное решение?
Не считается. Доказано, что она неразрешима. Или есть вопросы к доказательству?
S>Вопрос у меня вот в чем. Если я перевожу средства со счета в одном банке на счет в другом банке (очевидно у них разные СУБД и нельзя использовать локальную транзакцию). Канал передачи не надежен на 100% — очевидно — это глобальная сеть и сбои могут быть.
S>Но существует же алгоритм, благодаря которому имеем 100% достоверность, что действия будут согласованы и на 100% деньги не исчезнут одновременно с двух счетов а так же не удвоятся, не смотря на то что канал связи не надежен?
Ответ кроется в том, что именно подразумевается под "согласованы". Деньги не исчезнут и не удвоятся, но каждый банк не может доверять информации в своей базе, т.к. требуются подтверждения извне, хотя бы в какие-то эпизоды времени.
S>По идее так. Даю команду перевести 100 руб. на другой счет. Банк 1 сначала создает запись о переводе, уменьшает сумму на счете на 100 руб. Потом пытается связаться с внешним сервисом (пусть там другого банка или нац. банка — не важно) и при успешном ответе от него — уже фиксирует транзакцию. Если ответа нет — то делает запросы до победного конца (деньги будет блокировать, пока не внесется ясность).
S>Но тут какая проблема. Откуда банк 2 знает что банк 1 получил успешный ответ? Вдруг не получил? Значит банк 2 должен сделать запрос к банку 1. Но это очень похоже на задачу двух генералов этих, которая вроде как неразрешима.
очень, но не вполне. Перевод денег не требует синхронности. Поэтому, списать можно сегодня, а обнаружить переведенное — через 3 банковских дня. Лаг в 3 рабочих дня не обеспечивает гарантию, но дает очень-очень надежный статистический результат. Если что пойдет не так, запись о переводе можно доставить хоть на оленях.
S>Или же наличие ответственного в принятии решений как бы делает задачу разрешимой?
задачу о двух генералах — нет, не делает. Банковский перевод может быть при этом достаточно надежным.
S>Вопрос вот в чем. Можно ли как-то таки эту задачу генералов решить не вероятностно (что согласованность получена с большой вероятностью) а точно? Поможет ли введение ответственного в принятии решений? И таки перевод средств из одной системы в другую (когда нет локальных транзакций, скажем так) по ненадежному каналу связи — решен вероятностно или же существует точное решение?
Еще раз, см. доказательство неразрешимости задачи о двух генералах. При любом кол-ве посредников будет минимальный набор сообщений между ними, обеспечивающий синхронную атаку генералов. И отсутствие гарантии доставить минимальный набор сообщений.
На деле же, хотя банки и гарантируют перевод в 3 дня, вполне могут деньги потерять и найти через месяц-другой, а то и пол года.
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, Sharov, Вы писали:
S>>На 5-й день все будет ходить в обе стороны.
S>Получается, что если канал связи не стабилен, но все же имеет точную вероятностную оценку доступности (не менее чем...) — мы можем вычислить время, в течение которого системы будут согласованы на 100%? Так почему же задача не имеет решения?
Потому что решение (вернее его отсутствие) формулируется в дискретных величинах — да или нет.
Мы прекрасно понимаем, что в реальности есть величины непрерывные. И задача в целом решается, ибо можно перевести деньги из одного банка в другой.
Здравствуйте, Shmj, Вы писали:
S>1. Определяем главного генерала. S>2. Главный генерал передает сообщение с указанием даты/времени. S>3. Второй генерал подтверждает и так же понимает, что первый генерал если не получит его подтверждение — пошлет посыльного/сообщение еще раз. S>4. Второй генерал больше не получает посыльных и знает что канал работает 99.95% времени — а значит не может такого быть, чтобы целый день при работающем канале посыльные больше не приходили. Значит первый генерал на 100% получил его одобрение. S>В чем подвох?
В том, что если мы хотим что-то решить синхронно, за фиксированный интервал времени, то вынужденны
оперировать вероятностями. Нету дискретных да\нет. В асинхронном случае мы по времени не ограничены
(т.е. ограничены, конечно, но никак в синх. случае).
Кодом людям нужно помогать!
Re[13]: Про задачу 2 генералов в реальной жизни...
Здравствуйте, 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% доставки когда-либо?
Зависит от гарантий. Если гарантия в условии задачи, то мы исходим из этой гарантии. Если как в банке или аптеке — то цена гарантии невелика и мы вместо пакета можем получить зуб того, кто гарантию давал. В лучшем случае. И потом отдать этот зуб генералам в качестве компенсации за проигранную войну. Даже если мы по иску слупим компенсацию за недоставленный пакет, вряд ли это поможет генералам.
Здравствуйте, 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>Вопрос вот в чем. Можно ли как-то таки эту задачу генералов решить не вероятностно (что согласованность получена с большой вероятностью) а точно? Поможет ли введение ответственного в принятии решений? И таки перевод средств из одной системы в другую (когда нет локальных транзакций, скажем так) по ненадежному каналу связи — решен вероятностно или же существует точное решение?
Здравствуйте, samius, Вы писали:
S>На деле же, хотя банки и гарантируют перевод в 3 дня, вполне могут деньги потерять и найти через месяц-другой, а то и пол года.
Ну, из-за проблем канала связи — не будет пол года. Это что, за пол года так и не восстановили канал связи? Что если исходить из гарантии 99.5% доступности канала связи на каждой из сторон — можно ли сказать, что в течение 5 дней при любом раскладе транзакция будет завершена?
99.5% гарантия доступности — это значит что максимум 2 дня в год не будет связи. Даже в худшем варианте — 2 дня один банк сидел без канала, потом сразу 2 дня другой — совпал худший сценарий. Но потом на 5 день 100% проведена будет — при самом худшем раскладе.
Здравствуйте, Shmj, Вы писали:
S>Ну, из-за проблем канала связи — не будет пол года. Это что, за пол года так и не восстановили канал связи? Что если исходить из гарантии 99.5% доступности канала связи на каждой из сторон — можно ли сказать, что в течение 5 дней при любом раскладе транзакция будет завершена? S>99.5% гарантия доступности — это значит что максимум 2 дня в год не будет связи. Даже в худшем варианте — 2 дня один банк сидел без канала, потом сразу 2 дня другой — совпал худший сценарий. Но потом на 5 день 100% проведена будет — при самом худшем раскладе.
Сами ответили на свой вопрос
Но тут какая проблема. Откуда банк 2 знает что банк 1 получил успешный ответ? Вдруг не получил? Значит банк 2 должен сделать запрос к банку 1. Но это очень похоже на задачу двух генералов этих, которая вроде как неразрешима.
Здравствуйте, Sharov, Вы писали:
S>На 5-й день все будет ходить в обе стороны.
Получается, что если канал связи не стабилен, но все же имеет точную вероятностную оценку доступности (не менее чем...) — мы можем вычислить время, в течение которого системы будут согласованы на 100%? Так почему же задача не имеет решения?
В случае с генералами это можно рассматривать так.
Выбираем ответственного — того, у которого армия больше на момент начала. Далее лишь он диктует условия — присылает посыльного, который сообщает время и затем возвращается. Если не вернулся — то посылает второго. И т.д.
Второй генерал знает что если новый посыльный не пришел — значит первый добрался — значит время согласовано.
Тут можно рассматривать вариант, что первый генерал посылает посылает посыльных и никто из них так и не смог проделать цикл.
Если рассматривать что вероятность успеха посыльного — 50% и можно посылать посыльного 1 раз в час — то каждый час вероятность согласования (если новый посыльный не пришел) — удваивается. Т.е. вероятность что посыльный не дошел — падает в 2 раза каждый час.
Однако же в случае с банками — у нас иного рода гарантии. Мы имеем максимально возможное время недоступности канала в год — 2 дня. Не больше точно. Если бы эту гарантию перенести на генералов, что при худшем раскладе лишь 1% времени в год посыльный не дойдет — тогда как бы уже задача разрешима.
Здравствуйте, Shmj, Вы писали:
S>Получается, что если канал связи не стабилен, но все же имеет точную вероятностную оценку доступности (не менее чем...) — мы можем вычислить время, в течение которого системы будут согласованы на 100%? Так почему же задача не имеет решения?
Потому что она имеет стохастическую природу. Вы уже оперируете вероятностями -- может так,а может не так.
Поэтому получить точное конкретное решение не возможно. Т.е. возможно с некоторой вероятностью.
S>Однако же в случае с банками — у нас иного рода гарантии. Мы имеем максимально возможное время недоступности канала в год — 2 дня. Не больше точно. Если бы эту гарантию перенести на генералов, что при худшем раскладе лишь 1% времени в год посыльный не дойдет — тогда как бы уже задача разрешима.
Выше уже писали про синхронность (в случае генералов) и асинхронность( в случае банков). В асинхронном случае
все заработает при доступности каналов, в синхронном не так.
Здравствуйте, gandjustas, Вы писали:
G>Потому что решение (вернее его отсутствие) формулируется в дискретных величинах — да или нет. G>Мы прекрасно понимаем, что в реальности есть величины непрерывные. И задача в целом решается, ибо можно перевести деньги из одного банка в другой.
Тут еще как рассматривать вероятность. Если рассматривать что вероятность доставки сообщения 99.5% — это одно. В таком раскладе возможен вариант, что даже 1 млрд. раз подряд сообщение не доставлено, пусть и маловероятно. Если же рассматривать вероятность доступности канала не менее 99.5% времени в год — то ситуация сильно меняется — в худшем раскладе лишь 2 дня в году канал не доступен, а значит имеем гарантию.
Здравствуйте, Sharov, Вы писали:
S>Выше уже писали про синхронность (в случае генералов) и асинхронность( в случае банков). В асинхронном случае S>все заработает при доступности каналов, в синхронном не так.
А если генералы заранее договорились об асинхронном варианте? Можно ли так?
К примеру, назначали 1 генерала — только он отправляет посыльного. Второй лишь ждет. Посыльный пройдет путь туда-обратно максимум за 1 час. Если пришел первый посыльный и через 1.5 часа не пришел новый, значит:
1. 1 успешно дошел назад и время согласовано, нового посылать нет смысла.
2. Новый посыльный не дошел.
И далее как мы рассматриваем вероятности. Если рассматривать, что вероятность доставки сообщения 99.5% — это одно. В таком раскладе возможен вариант, что даже 1 млрд. раз подряд сообщение не доставлено, пусть и маловероятно. Если же рассматривать вероятность доступности канала не менее 99.5% времени в год — то ситуация сильно меняется — в худшем раскладе лишь 2 дня в году канал не доступен, а значит имеем гарантию.
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, gandjustas, Вы писали:
G>>Потому что решение (вернее его отсутствие) формулируется в дискретных величинах — да или нет. G>>Мы прекрасно понимаем, что в реальности есть величины непрерывные. И задача в целом решается, ибо можно перевести деньги из одного банка в другой.
S>Немного напомнило задачи Зенона.
S>Тут еще как рассматривать вероятность. Если рассматривать что вероятность доставки сообщения 99.5% — это одно. В таком раскладе возможен вариант, что даже 1 млрд. раз подряд сообщение не доставлено, пусть и маловероятно.
Как обычно есть правило трех-шести-десяти сигм.
S>Если же рассматривать вероятность доступности канала не менее 99.5% времени в год — то ситуация сильно меняется — в худшем раскладе лишь 3 дня в году канал не доступен, а значит имеем гарантию.
Процент доступности это не время когда доступен, а когда нет, это вероятность доставки пакетов.
Тут наступает архитектура:
1) А надо ли нам вообще сразу давать ответ или мы можем повторять сообщение пока оно не доставится? Ведь даже при доступности в 80% надо совсем немного повторений, чтобы получить вероятность единичной доставки в 99.99% (помним что банковские переводы несинхронны)
2) Может у нас есть другой канал, более медленный, но более надежный (сверки по бухгалтерии)
3) А может есть посредник который возьмет на себя функцию согласования, которому мы достаточно доверяем? (цетробанк\swift\visa\СБП) А он уже организует достаточно надежные каналы, повторения, сети доверия итд.
А потом наступает экономика: если всетаки случится ошибка, то сколько нам будет стоить её исправление? Имеет ли смысл повышать надежность канала или будет слишком дорого?
Здравствуйте, gandjustas, Вы писали:
G>Процент доступности это не время когда доступен, а когда нет, это вероятность доставки пакетов.
Разве? Вроде в SLA гарантируется именно время в месяц или в год — с компенсацией деньгами в случае нарушения.
G>Тут наступает архитектура: G>1) А надо ли нам вообще сразу давать ответ или мы можем повторять сообщение пока оно не доставится? Ведь даже при доступности в 80% надо совсем немного повторений, чтобы получить вероятность единичной доставки в 99.99% (помним что банковские переводы несинхронны)
И тут вопрос — если договориться что будем повторять бесконечно, если не получили ответ — то это значит, что если дятел не стучит — значит ответ получен. Так же выгоднее?
G>3) А может есть посредник который возьмет на себя функцию согласования, которому мы достаточно доверяем? (цетробанк\swift\visa\СБП) А он уже организует достаточно надежные каналы, повторения, сети доверия итд.
Тут важна принципиальная разрешимость — ведь 100% надежных каналов не бывает.
Здравствуйте, Shmj, Вы писали:
S>>Выше уже писали про синхронность (в случае генералов) и асинхронность( в случае банков). В асинхронном случае S>>все заработает при доступности каналов, в синхронном не так. S>А если генералы заранее договорились об асинхронном варианте? Можно ли так?
Задача как формулируется? Они же оба хотят напасть одновременно, т.е. есть ограничение на верхнюю границу.
Асинхронный вариант по сути никаких временных гарантий и ограничений не дает.
Здравствуйте, Shmj, Вы писали:
S>Но существует же алгоритм, благодаря которому имеем 100% достоверность, что действия будут согласованы и на 100% деньги не исчезнут одновременно с двух счетов а так же не удвоятся, не смотря на то что канал связи не надежен?
Это работает "с некоторой вероятностью". И "не удвоятся" — это более сложное условие. Там внутренних счетов/состояний больше. На исходной стороне в процессе отправки сумма может быть "захолдирована" (с целью перевода). И этой записи могут соответствовать два состояния целевого банка: когда перевод не получен и когда перевод получен. В первом у вас есть "пропавшие" деньги, во втором — "дублированные" (до того, как первый банк получит подтверждение и закроет траназкцию).
S>Но тут какая проблема. Откуда банк 2 знает что банк 1 получил успешный ответ? Вдруг не получил? Значит банк 2 должен сделать запрос к банку 1. Но это очень похоже на задачу двух генералов этих, которая вроде как неразрешима.
А зачем ему это? Транзакция пришла — записали, деньги можно использовать. Получение ответа нужно банку 1 для закрытия холдированных средств. Закрытие может быть как успешный перевод (подтверждение получено) и как возврат средств на исходный счет (получена ошибка). До получения понятного ответа деньги так и будут "зависшими".
S>Или же наличие ответственного в принятии решений как бы делает задачу разрешимой?
Это другая задача. И, как уже в теме сказали, есть резервные механизмы. Транзакция может синхронизироваться через выписки или вручную. Т.е. "гарантии" решаются использованием альтернативных каналов. В случае, если они все вышли из строя — синхронизации не будет.
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, samius, Вы писали:
S>>На деле же, хотя банки и гарантируют перевод в 3 дня, вполне могут деньги потерять и найти через месяц-другой, а то и пол года.
S>Ну, из-за проблем канала связи — не будет пол года. Это что, за пол года так и не восстановили канал связи? Что если исходить из гарантии 99.5% доступности канала связи на каждой из сторон — можно ли сказать, что в течение 5 дней при любом раскладе транзакция будет завершена?
Вот я сейчас обслуживаюсь в банке, где скорость (валютного) перевода зависит в основном от того, настучала ли одна клава в головном офисе другой в доп офисе по аське, или забыла. Меня в принципе устраивает в этом лишь тариф. В другом банке, где все автоматизировано, услуга на голову дороже. Т.е. потерять могут даже при 100% канале связи, т.к. включен человеческий фактор. Был случай, когда деньги мне приходили уже в тот день, когда они должны были бы отправиться обратно, если бы валютный контроль не получил от меня документов по этим деньгам в тот же день. А на это дается 2 недели (вроде бы даже банковских).
Пол года — дается как раз на расследование. Т.е., допустим, если я уверен что отправитель деньги отправил, а я их не получил, начинаю заводить телегу по поиску денег. Пишу заявление, везу его в банк, они его читают, кладут в стопку, там оно лежит с месяц, пока до него не дойдет очередь. Ну т.е. пол года на расследование, куда дели деньги — вполне себе.
S>99.5% гарантия доступности — это значит что максимум 2 дня в год не будет связи. Даже в худшем варианте — 2 дня один банк сидел без канала, потом сразу 2 дня другой — совпал худший сценарий. Но потом на 5 день 100% проведена будет — при самом худшем раскладе.
Если бы в банках только лишь от связи все зависело... Прихожу однажды, а там нет всего отдела по борьбе с юрлицами, вместо отдела один стажер весь в соплях и заваленный бумагами и звонками.
Здравствуйте, Sharov, Вы писали:
S>Задача как формулируется? Они же оба хотят напасть одновременно, т.е. есть ограничение на верхнюю границу. S>Асинхронный вариант по сути никаких временных гарантий и ограничений не дает.
В чем разница — согласовать сумму денег или согласовать время?
Тут смотрите как. Если мы знаем что канал работает не менее чем 99.95% времени в день, скажем. Имеем такую гарантию. Это что-то меняет?
Такая схема:
1. Определяем главного генерала.
2. Главный генерал передает сообщение с указанием даты/времени.
3. Второй генерал подтверждает и так же понимает, что первый генерал если не получит его подтверждение — пошлет посыльного/сообщение еще раз.
4. Второй генерал больше не получает посыльных и знает что канал работает 99.95% времени — а значит не может такого быть, чтобы целый день при работающем канале посыльные больше не приходили. Значит первый генерал на 100% получил его одобрение.
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, gandjustas, Вы писали:
G>>Процент доступности это не время когда доступен, а когда нет, это вероятность доставки пакетов. S>Разве? Вроде в SLA гарантируется именно время в месяц или в год — с компенсацией деньгами в случае нарушения.
Это SLA, чтобы его посчитать можно было. А при проектировании проценты доступности стоит принимать как вероятность успешной передачи сообщения.
G>>Тут наступает архитектура: G>>1) А надо ли нам вообще сразу давать ответ или мы можем повторять сообщение пока оно не доставится? Ведь даже при доступности в 80% надо совсем немного повторений, чтобы получить вероятность единичной доставки в 99.99% (помним что банковские переводы несинхронны) S>И тут вопрос — если договориться что будем повторять бесконечно, если не получили ответ — то это значит, что если дятел не стучит — значит ответ получен. Так же выгоднее?
Спроси у разработчиков TCP (они предпочитают получать подтверждение доставки)
G>>3) А может есть посредник который возьмет на себя функцию согласования, которому мы достаточно доверяем? (цетробанк\swift\visa\СБП) А он уже организует достаточно надежные каналы, повторения, сети доверия итд. S>Тут важна принципиальная разрешимость — ведь 100% надежных каналов не бывает.
Не бывает, но бывает достаточно много ресурсов чтобы сделать вероятность потери сообщения настолько низкой, что она на практике не встретится.
Здравствуйте, maxkar, Вы писали:
S>>Или же наличие ответственного в принятии решений как бы делает задачу разрешимой? M>Это другая задача. И, как уже в теме сказали, есть резервные механизмы. Транзакция может синхронизироваться через выписки или вручную. Т.е. "гарантии" решаются использованием альтернативных каналов. В случае, если они все вышли из строя — синхронизации не будет.
Можно ли решить средствами 1 канала, который доступен 99.95% времени гарантированно за определенный срок (гарантировать что синхронизация пройдет не позже чем n времени в худшем случае)?
Здравствуйте, samius, Вы писали:
S>Пол года — дается как раз на расследование. Т.е., допустим, если я уверен что отправитель деньги отправил, а я их не получил, начинаю заводить телегу по поиску денег. Пишу заявление, везу его в банк, они его читают, кладут в стопку, там оно лежит с месяц, пока до него не дойдет очередь. Ну т.е. пол года на расследование, куда дели деньги — вполне себе.
Ну это уже не проблема канала связи. Канал связи то никак не может не работать пол года, верно?
Re[10]: Про задачу 2 генералов в реальной жизни...
Здравствуйте, Sharov, Вы писали:
S>В том, что если мы хотим что-то решить синхронно, за фиксированный интервал времени, то вынужденны S>оперировать вероятностями. Нету дискретных да\нет. В асинхронном случае мы по времени не ограничены S>(т.е. ограничены, конечно, но никак в синх. случае).
Что мешает увеличить время в синхронном варианте до такой же величины, как в асинхронном?
Тут вопрос ставить иначе. Если мы гарантируем, что в месяц канал работает минимум 99.95% времени — это что-то изменит? Или по прежнему останется вероятностное согласование? Или же произойдет сходимость рядов?
Re[10]: Про задачу 2 генералов в реальной жизни...
Здравствуйте, gandjustas, Вы писали:
G>Это SLA, чтобы его посчитать можно было. А при проектировании проценты доступности стоит принимать как вероятность успешной передачи сообщения.
А если имеем гарантию доступности по времени именно — это что-то меняет?
G>Спроси у разработчиков TCP (они предпочитают получать подтверждение доставки)
Но не получают подтверждение доставки подтверждения доставки.
G>Не бывает, но бывает достаточно много ресурсов чтобы сделать вероятность потери сообщения настолько низкой, что она на практике не встретится.
А не произойдет ли сходимость рядов и 100% гарантия доставки, если гарантируем работоспособность определенный процент времени? Ведь на практике мы даем такую гарантию каналу — если канал навернется — то подключим другой, но точно не будем месяц сидеть оффлайн.
Здравствуйте, Shmj, Вы писали:
S>>Пол года — дается как раз на расследование. Т.е., допустим, если я уверен что отправитель деньги отправил, а я их не получил, начинаю заводить телегу по поиску денег. Пишу заявление, везу его в банк, они его читают, кладут в стопку, там оно лежит с месяц, пока до него не дойдет очередь. Ну т.е. пол года на расследование, куда дели деньги — вполне себе.
S>Ну это уже не проблема канала связи. Канал связи то никак не может не работать пол года, верно?
И да и нет. Я о том, откуда берутся пол года при гарантии перевода в 3 дня. А вот проблема ли это канала связи, зависит от того, что мы включаем в понятие "канал связи". Если рассмотреть непосредственно все, что находится между отправлением и получением перевода, то кажанные мешки вполне могут быть частью этого канала. В случае валютного перевода и ВК — неотэемлемая часть.
Re[11]: Про задачу 2 генералов в реальной жизни...
Здравствуйте, Shmj, Вы писали:
S>Тут вопрос ставить иначе. Если мы гарантируем, что в месяц канал работает минимум 99.95% времени — это что-то изменит? Или по прежнему останется вероятностное согласование? Или же произойдет сходимость рядов?
Это меняет условие задачи. Здесь уже можно говорить о гарантированной доставке (за некоторое ненулевое время). А с гарантированной доставкой и задачи о генералах нет, т.е. она решена по условию.
Re[12]: Про задачу 2 генералов в реальной жизни...
Здравствуйте, samius, Вы писали:
S>Это меняет условие задачи. Здесь уже можно говорить о гарантированной доставке (за некоторое ненулевое время). А с гарантированной доставкой и задачи о генералах нет, т.е. она решена по условию.
Но ведь когда на практике говорят, что канал доступен не менее пусть даже 95% времени в месяц (это низкий показатель — но правдивый) — это есть гарантированная доставка?
Если действовать по моей схеме, то точно можно вычислить срок, после которого состояние на 100% согласовано. Делаем так:
1. Генерал 1 отправляет данные.
2. Генерал 2 получает и подтверждает в ответ (не зная доставлен ли его ответ).
3. Генерал 2 ждет n времени и если не было повторных отправок данных — имеет 100% гарантию согласованности. Его уверенность основана на том, что всего 5% времени в месяц канал не работает — а уже прошло больше этого времени в худшем раскладе.
Все верно?
И далее — если канал доступен всего 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% времени в месяц — это уже иная ситуация.
Re[15]: Про задачу 2 генералов в реальной жизни...
Здравствуйте, 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 часам. С таким условием обоим генералам достаточно всего одного сообщения. Ряд не нужен.
Но если ставить в зависимость вероятность доствки от даты и времени (откладывать от начала месяца), то нам придется отслеживать время недоступности канала в течение месяца, а для этого надо посылать запросы и получать ответы каждую дельту времени всего лишь для того, что бы оценить вероятность доставки очередного сообщения.
Я не специалист в области банковских транзакций, но интуиция подсказывает следующее.
Есть координатор распределенных транзакцией.
Если он увидел, что какой-то из банков не выполнил свою часть транзакции,
он даёт другому банку (который часть транзакции выполнил) команду на откат транзакции.
Если переводить это на язык задачи про двух генералов, то получается
если генерал видит что атакует в одиночку,
то без потерь отступает,
возвращается на свою исходную позицию
и начинает согласование атаки заново,
если не отпала необходимость в штурме.
Да, можем потерять время, но при банковских переводах это случается редко и поэтому допустимо.
Отвечайте на это сообщение, только если у Вас хорошее настроение и в Вашем ответе планируются только конструктивные вопросы и замечания http://rsdn.ru/Info/rules.xml
Здравствуйте, 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>Но тут какая проблема. Откуда банк 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>Как видно из примера приведённого выше не важно было ли доставлено последнее сообщение или нет, так как оно не влияет на решение второго генерала. Это было достигнуто за счёт избыточности сообщений: условие согласованности действий выполнится, так как минимальное подмножество сообщений включает в себя последнее сообщение не обязательное к доставке.
Итак, существует подмножество сообщений, меньше заявленного минимального. Отсюда следует, что заявленное минимальное подмножество не является минимальным.
Доказательство неразрешимости строится на существовании минимального подмножества. Очевидно, что заявленные минимальные подмножества с избыточностью не имеют к нему отношения.
