Чисто практическая задача

[PavelM]

Жил-был князь. Напал на его княжество враг.
Собрался князь на битву, но сил маловато.
Решил позвать в подмогу пару соседних князей.
Всем троим нужно придти на место битвы в одно время, иначе разобьют.
Послал гонцов. Однако по дороге гонцов могут поймать.

Сможет ли князь разбить врага и при каких условиях?

[Snafu]

Предствить гонца в виде IP-пакета и использовать протокол TCP вместо UDP
В смысле - озаботиться квитанцией о доставке. Если гонец не вернулся к заданному времени - отправить другого, желательно по другой дороге. "И так дэсять раз"(с)

[Hamster]

Гарантировать ничего нельзя. Допустим, враги устроят засаду и будут убивать всех гонцов. Что делать князю? Гонцы не возвращаются - информации о том, достигли ли они назначения, у него нет - отправляться в путь нельзя.

[FireFox]

Предствить гонца в виде IP-пакета и использовать протокол TCP вместо UDP
В смысле - озаботиться квитанцией о доставке. Если гонец не вернулся к заданному времени - отправить другого, желательно по другой дороге. "И так дэсять раз"(с)

Не, так не пойдет

Представьте, что почти всех гонцов князя А к князю Б перехватили на дороге туда, последнему гонцу все-таки удалось добраться до князя Б, но его перехватили на обратной дороге. Что будет делать князь Б? а князь А?

Нужно провести атомарную транзакцию по ненадежному каналу. Если просто тупо обмениваться гонцами, то последний пославший гонца не знает гарантированно результат.

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

[PavelM]

Гарантировать ничего нельзя. Допустим, враги устроят засаду и будут убивать всех гонцов. Что делать князю? Гонцы не возвращаются - информации о том, достигли ли они назначения, у него нет - отправляться в путь нельзя.

Хорошо.
Рассмотрим случаи когда перехватывают 1-го или 2-х гонцов случайным образом.

[Hamster]

Хорошо.
Рассмотрим случаи когда перехватывают 1-го или 2-х гонцов случайным образом.

Послать 3-х.

[Snafu]

Представьте, что почти всех гонцов князя А к князю Б перехватили на дороге туда, последнему гонцу все-таки удалось добраться до князя Б, но его перехватили на обратной дороге. Что будет делать князь Б? а князь А?

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

[FireFox]

Представьте, что почти всех гонцов князя А к князю Б перехватили на дороге туда, последнему гонцу все-таки удалось добраться до князя Б, но его перехватили на обратной дороге. Что будет делать князь Б? а князь А?

А ничего Оба соседа тупо выполняют последнюю полученную команду. Доскакал ли гонец взад - им по камертону и по барабану.

Ну тогда в описанной ситуации Князь Б припрется один как лох на стрелку

он же получил команду выдвигаться, а Князь А будет дома сидеть -- ни один гонец-то не вернулся

Гонец скачет по кругу - сосед А, сосед Б - и домой. Если по истечении таймаута не вернулся - князь шлет следующего, с новым приказом, отбивающим предыдущий. И так, пока кто-нибудь не вернется.

А если никто не вернется? Тогда тому Князю может быть подстава.
Время стрелки-то уже назначено я так понимаю

[Snafu]

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

[vm__]

Сможет ли князь разбить врага и при каких условиях?

Если у князя есть ядрена бомба, и соседние страны поддерживают демократизацию - то запросто!
(Иракский гонец спрашивал Великого Большого Брата перед вторжением в маленьнкую нефтеносную страну - и оказалось, что зря. )

[PavelM]

Хорошо.
Рассмотрим случаи когда перехватывают 1-го или 2-х гонцов случайным образом.

Послать 3-х.

Не, троих нельзя.
В каждом царстве гонец один.

[PavelM]

Предствить гонца в виде IP-пакета и использовать протокол TCP вместо UDP
В смысле - озаботиться квитанцией о доставке.

Ну вобщем-то сама задача и возникла в контексте синхронизации распределенных БД через ненадежные каналы.

[Hamster]

Хорошо.
Рассмотрим случаи когда перехватывают 1-го или 2-х гонцов случайным образом.

Послать 3-х.

Не, троих нельзя.
В каждом царстве гонец один.

Даже так?

Посылаем гонца к князю А.
Князь А делает копию письма и дает своему гонцу. Два гонца посылаются к князю Б разными дорогами.
Князь Б делает копию письма и дает своему гонцу. Все три посылаются к Великому князю.
Если к Великому князю не возвращается ни одного гонца, он никуда не идет.

Если на дорогах в случайном месте одна засада: вероятность 1/6 что стрелка отменяется, 5/6 что все соберутся вместе.

Если две засады: 1/6 что стрелка отменяется, 1/15 что князь А придет на стрелку один, 23/30 что соберутся.

[Dory]

Сможет ли князь разбить врага и при каких условиях?

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

[Abappy]

Ну вобщем-то сама задача и возникла в контексте синхронизации распределенных БД через ненадежные каналы.

И каково было решение реальной задачи?

Решение предложенной довольно легко - формулировать действия так, что подтверждения не нужны для самих действий, но нужны для прекращения запросов на действие .

Приблизительно так

1. Глубокоуважаемые соседи DB.1 и DB.2 пожалуйста, соберитесь с дружиной у DB.1 и двигайтесь оттуда ко мне. Прошу подтвердить получение просьбы . Искренне Ваш DB.MAIN

гонцы с письмом этого вида шлются либо пока не придёт подтверждение либо пока не придут соседи в DB.MAIN ... ну а уже оттуда все втроём к месту боя