Амнезовое наводнение

В распределенных вычислительных наводнениях Амнезическое наводнение находится в бессмысленном распределенном алгоритме наводнения , который может быть реализован в качестве протокола вещания в синхронных распределенных сетях без необходимости хранить сообщения или флаги между раундами связи. ^{[ 1 ]} Алгоритм прост:

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

Было показано, что алгоритм прекращается, когда сообщение начинается в любом подмножестве сетевых узлов ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]} или любая его последовательность. ^{[ 4 ]}

Для $I\subseteq V$ подмножество узлов графика $G$ , затем $t(I)$ время до затопления амнезии, когда начинается с начала $I$ Известно, что подчиняется следующим границам: $t(I)=e(I)$ если $G$ является $I$ -Bipartite и $e(I)<t(I)\leq e(I)+d(G)+1$ Если это не так, где $e(I)$ является эксцентриситетом $I$ и $d(G)$ диаметр . ^{[ 1 ]} График есть $I$ -Bipartite, если коэффициент графика $G$ с $I$ Сокращенный на один узел двухпартий . ^{[ 1 ]} Это время завершения оптимально для $I$ -Bipartite Графики и асимптотически оптимально для инициализации отдельного узла на небитартских графиках.

Это прекращение является устойчивым в отношении потери краев и узлов, однако оно не удается с задержками по краям или с добавлением новых краев. ^{[ 1 ]}^{[ 2 ]}

Варианты наводнения амнезии

С момента его введения было изучено несколько вариантов и связанных с ними проблем с наводнением амнезии. Например, модифицированный вариант, требующий первоначального набора, чтобы сохранить свои знания об этом членстве и сообщение для одного раунда, но всегда требуя $e(I)+1$ Раунды были предложены. ^{[ 5 ]}

Была введена динамическая версия наводнения амнезии ^{[ 4 ]} Учитывая случай, когда в системе есть несколько разных сообщений и где каждый узел может отправлять только одно сообщение за раунд. Это было показано, что прекращается в случае частичной отправки ( $v$ Отправляет произвольное сообщение своим соседям, которое не отправило ему никакого сообщения в последнем раунде), и походное дело ( $v$ Отправляет сообщение с наибольшим ранжированием $m$ всем своим соседям, которые не послали его $m$ последний раунд). ^{[ 4 ]} Тем не менее, нельзя погасить ( $v$ отправляет произвольное сообщение $m$ всем своим соседям, которые не послали его $m$ Последний раунд) не обязательно завершается без дополнительной сохраненной информации (например, диаметр графика ^{[ 6 ]}).

Ссылки

^ Подпрыгнуть до: ^а ^{беременный} ^в ^{дюймовый} ^и Хуссак, Уолтер; Трехан, Амитабх (2023-06-01). «Прекращение наводнения амнезии» . Распределенные вычисления . 36 (2): 193–207. doi : 10.1007/s00446-023-00448-y . ISSN 1432-0452 .
^ Подпрыгнуть до: ^а ^{беременный} Хуссак, Уолтер; Чем, Амитабх (2020). «О прекращении наводнения». В Павле Кристоф; Bläser, Markus (Eds.). 37-й Международный симпозиум по теоретическим аспектам информатики, Stacs 2020, 10-13 марта, 2020, Монпелье, Франция . Липки. Том. С. 17: 1–17: 13. Doi : 10.4230/lipics.stacs.2020.17 .
^ Туру, Волкер (2021). «Амнезовое наводнение: синхронное распространение информации без гражданства». В Буреше, Томаш; Донди, Риккардо; Гампер, Иоганн; Геррини, Джованна; Юрдзински, Томаш; Пахл, Клаус; Сикора, Флориан; Вонг, благоразумия WH (ред.). 47-я Международная конференция по текущим тенденциям в теории и практике компьютерных наук, SOFSEM 2021, Bolzano-Bozen, Италия, 25–29 января 2021 года, Tractings . Заметки лекции в информатике. Тол. 12607. Cham: Springer International Publishing. С. 59–73. doi : 10.1007/978-3-030-67731-2_5 . ISBN 978-3-030-67731-2 Полем S2CID 231705141 .
^ Подпрыгнуть до: ^а ^{беременный} ^в Хуссак, Уолтер; Трехан, Амитабх (2020-09-12), прекращение случаев наводнения , arxiv : 2009.05776
^ Туру, Волкер (2020). «Алгоритмы распространения информации без гражданства» . В Риче Андреа Внек; Scheideler, Christian (Eds.). Структурная информация и сложность связи . Заметки лекции в информатике. Тол. 12156. Cham: Springer International Publishing. С. 183–199. doi : 10.1007/978-3-030-54921-3_11 . ISBN 978-3-030-54921-3 .
^ Байрамзаде, Захра; Kshemkalyani, Ajay D.; Молла, Анисур Рахаман; Шарма, Гокарна (2021). «Слабое наводнение амнезии множества сообщений». В Echihabi, Карима; Мейер, Роланд (ред.). Сетевые системы: 9 -я Международная конференция, Netys 2021, Виртуальное событие, 19–21 мая 2021 года, Труды . Заметки лекции в информатике. Cham: Springer International Publishing. С. 88–94. doi : 10.1007/978-3-030-91014-3_6 . ISBN 978-3-030-91014-3 Полем S2CID 244818918 .

[:1-1] Подпрыгнуть до: ^а ^{беременный} ^в ^{дюймовый} ^и Хуссак, Уолтер; Трехан, Амитабх (2023-06-01). «Прекращение наводнения амнезии» . Распределенные вычисления . 36 (2): 193–207. doi : 10.1007/s00446-023-00448-y . ISSN 1432-0452 .

[:0-2] Подпрыгнуть до: ^а ^{беременный} Хуссак, Уолтер; Чем, Амитабх (2020). «О прекращении наводнения». В Павле Кристоф; Bläser, Markus (Eds.). 37-й Международный симпозиум по теоретическим аспектам информатики, Stacs 2020, 10-13 марта, 2020, Монпелье, Франция . Липки. Том. С. 17: 1–17: 13. Doi : 10.4230/lipics.stacs.2020.17 .

[3] Туру, Волкер (2021). «Амнезовое наводнение: синхронное распространение информации без гражданства». В Буреше, Томаш; Донди, Риккардо; Гампер, Иоганн; Геррини, Джованна; Юрдзински, Томаш; Пахл, Клаус; Сикора, Флориан; Вонг, благоразумия WH (ред.). 47-я Международная конференция по текущим тенденциям в теории и практике компьютерных наук, SOFSEM 2021, Bolzano-Bozen, Италия, 25–29 января 2021 года, Tractings . Заметки лекции в информатике. Тол. 12607. Cham: Springer International Publishing. С. 59–73. doi : 10.1007/978-3-030-67731-2_5 . ISBN 978-3-030-67731-2 Полем S2CID 231705141 .

[:2-4] Подпрыгнуть до: ^а ^{беременный} ^в Хуссак, Уолтер; Трехан, Амитабх (2020-09-12), прекращение случаев наводнения , arxiv : 2009.05776

[5] Туру, Волкер (2020). «Алгоритмы распространения информации без гражданства» . В Риче Андреа Внек; Scheideler, Christian (Eds.). Структурная информация и сложность связи . Заметки лекции в информатике. Тол. 12156. Cham: Springer International Publishing. С. 183–199. doi : 10.1007/978-3-030-54921-3_11 . ISBN 978-3-030-54921-3 .

[6] Байрамзаде, Захра; Kshemkalyani, Ajay D.; Молла, Анисур Рахаман; Шарма, Гокарна (2021). «Слабое наводнение амнезии множества сообщений». В Echihabi, Карима; Мейер, Роланд (ред.). Сетевые системы: 9 -я Международная конференция, Netys 2021, Виртуальное событие, 19–21 мая 2021 года, Труды . Заметки лекции в информатике. Cham: Springer International Publishing. С. 88–94. doi : 10.1007/978-3-030-91014-3_6 . ISBN 978-3-030-91014-3 Полем S2CID 244818918 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]