分散アルゴリズム：ワイヤレスモバイルネットワークの大きさを調べたい！
この投稿は、 FOLIO Advent Calendar 2024 の19 日目の記事になります。 このブログを更新するのもとても久々ですね。いくつかの書きかけのブログの残骸を見て、数年間公開を放置していることを実感します。。。 概要 前回の投稿では、論理時間について書きました。論理時間自体はとても古く、分散アルゴリズムの基本中の基本のひとつになっています。今回は少し新しい話を書こうかと思います（そう思っていました）。今回紹介するアルゴリズムは、モバイルノード群がある一定の大きさの空間に存在する際に、その空間内にいくつのモバイルノードが存在するのかを、モバイルノード群が自律的に検出するアルゴリズムです。何か最新のアルゴリズムでも紹介しようと新しいものを探していた時に、偶然見つけた論文のさらに基礎になっているアルゴリズムがあったので、それを紹介します。（その結果、全然新しくなくなりました。）2010年に公開された少し古いアルゴリズムではありますが、簡単でわかりやすいものです。環境は、自律的に移動可能なモバイルノードがたくさん（数千や数万）存在するような環境でも、システム内にいくつのモバイルノードが存在するのかを検知可能なアルゴリズムです。 出典は、Kuhn, Fabian, Nancy Lynch, and Rotem Oshman. “Distributed Computation in Dynamic Networks.” Proceedings of the 42nd ACM Symposium on Theory of Computing - STOC ’10. Cambridge, Massachusetts, USA, 2010. 513. Copyright 2010 ACM こちらになります。 Distributed Computation in Dynamic Networks この論文では、主に3つのアルゴリズムを紹介しています。 ネットワーク内に存在するノードの数を検出する問題 リーダー選出問題 噂の伝搬を使ったグループメンバーシップ問題 これらのアルゴリズムを実現するためには、いくつかの前提を置く必要があります。まず、ノードは無線通信等を利用する可動式のノードで構成され、ネットワークの形状（トポロジ）が動的に変化することがで...