`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

BEST CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Игровой алгоритм гарантирует доставку данных в децентрализованных сетях

+33
голоса

Игровой алгоритм гарантирует доставку данных в децентрализованных сетях

Новый алгоритм распространения информации в децентрализованных сетях обеспечивает большее быстродействие, чем его предшественники, и, при этом, в отличие от них, гарантирует доставку.

Бернард Хойплер (Bernhard Haeupler) из Массачусетского технологического института (MIT), представивший свою работу на симпозиуме по дискретным алгоритмам ACM-SIAM, называет свой вариант пересылки сообщений детерминистическим, в отличие от всех прочих — вероятностных. Независимо от длительности их выполнения, по его словам, всегда остается незначительный, но реальный шанс, что информация не достигнет какого-то узла сети.

Довольно просто реализовать надежный на 100% метод передачи данных в случае, если один из узлов хранит карту всей сети. Но подобная централизация не всегда практична: многие сети, например, объединяющие автомобили с беспроводным подключением в потоке дорожного движения или солдат на поле боя, постоянно меняют свою конфигурацию и их карты быстро теряют актуальность. Кроме того, обновление информации о компонентах такой сети увеличивает расход энергии, уменьшая ресурс автономности подключенных устройств, работающих от батарей.

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

Каждый раунд это время, требуемое для обмена информацией между двумя смежными узлами. В базовой версии нового алгоритма каждый узел начинает с выбора соседа и обмена с ним данными за один раунд. Затем, он находит второй узел и выполняет по два раунда обмена уже с двумя соседями. На третьем этапе, уже обладая сведениями от двух других узлов, он выбирает третий, о котором ничего не «слышал» ни прямо, ни опосредованно. После этого информация рассылается за три раунда уже в три узла. Алгоритм продолжает работу пока — прямо или косвенно — не обеспечивается охват абсолютно всех узлов сети.

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

Дізнайтесь більше про мікро-ЦОД EcoStruxure висотою 6U

+33
голоса

Напечатать Отправить другу

Читайте также

 
 

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT