分散アルゴリズム：ワイヤレスモバイルネットワークの大きさを調べたい！

　この投稿は、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つのアルゴリズムを紹介しています。

1. ネットワーク内に存在するノードの数を検出する問題
2. リーダー選出問題
3. 噂の伝搬を使ったグループメンバーシップ問題

　これらのアルゴリズムを実現するためには、いくつかの前提を置く必要があります。まず、ノードは無線通信等を利用する可動式のノードで構成され、ネットワークの形状（トポロジ）が動的に変化することができます。また、ノードは各々を識別可能なIDを保有しており、自ノードのIDは最初から知っていますが、他のノードのIDについては初期状態では知っている必要がありません。そのIDは外部から観測できるものではなく、通信を用いたメッセージの交換でのみ、メッセージの受信時に知ることができます。また、システム全体を見渡すことができるシステムは存在しません。

　ノード数の決定問題は、ネットワークを構成するノードの数をアルゴリズムの実行時に時間の変化とともにメッセージを交換し合うことで数え上げていくアルゴリズムです。分散アルゴリズムの中には、システム内にリーダーがある前提で問題を解くものが少なくありません。多数のノード群からひとつのノードをリーダーとする際には、ノードの総数が決定しないとリーダーが選べたのかどうかわかりません。また、リーダーを検出することで結果的にグループメンバーシップ問題を解くことができます。グループメンバーシップとは、そのネットワーク内に存在するノードのリストを生成することです。

　これらの分散アルゴリズムを利用することで、様々なアプリケーションを実現することが可能となります。例えば、アグリテックなどを考えてみましょう。ある農園の敷地内に、農業用のドローンが数百台から数万台存在するとします。このドローンはすべて農業用の処理を自律的に協調し合いながら処理しています。このようなアプリケーションでは、ドローンの作成時に他のドローンのことを考えながら作りたくない場合も多いと思います。また、環境内にネットワークインフラを用意しても良いですが、インフラの用意には小さくないコストがかかる可能性が高く、可能な限りコストを抑えたいと考える場面も多いです。また、インフラにつながるメインフレームなどの大きいコンピュータやクラウドシステムにつなげると、それはそれでコストがかかります。もちろん、それでもそっちの方が良いという決定をすることも十分ありえますが、ひとつの選択肢としては、コストを抑えてドローンを設置したら自律的にシステムを初期化して動作してくれたら嬉しいです。一方で、このようなシステムでは、起動してから時間を要する場合も多いですが、農業では秒の単位や分の単位の誤差が大きな影響を与えることは少ないです。このような背景で、少し時間がかかってもいいけども初期化などの面倒を減らしたい場合には、このような分散アルゴリズムは大きなインパクトがあるかと思います。

　また、日常生活でよく聞くようなクラウドシステムや、ブロックチェーンを使ったビットコインのような仮想通貨システムにも実は分散アルゴリズムがたくさん使われています。

　今回は、上記の論文のうちで最もわかりやすいアルゴリズムである、ネットワーク内に存在するノード数をカウントするアルゴリズムをシンプルなモデルで紹介したいと思います。以下、ノードと言われるものは、前述の農業用ドローンと思っていただければと思います。

　今回のポストでは、まず分散システムって何ですか？という話を簡単にします。その後、時間の考え方である同期・非同期の話やそのハイブリッドシステムの話をしようかと思います。その後、分散システムではとても重要な要素のひとつである故障の話も簡単にします。そして、アルゴリズムが前提としているネットワークモデルの話を少しして、本題のアルゴリズムの振る舞いについて簡単に書きます。あまり詳しい話は書かずに、シンプルな振る舞いの部分だけ説明しようかと思います。

分散システムって何？

　まずは、分散システムって何？というところから書こうかと思います。一般的に、分散システムとは、CPUなどの計算能力とメモリなどの記憶能力、Wi-Fiなどの通信能力を持つコンピュータ群が、通信を用いて協調的に動作することで、ひとつの作業を協調的に処理することが可能なシステムを意味します。また、複数のコンピュータが協調的に動作するため、一部のコンピュータが故障等の理由により処理不能になった場合でも、パフォーマンスなどは落ちるものの継続的に処理が続けられることを目的とすることが多いです。

　分散システムの主な構造には、複数あります。例えば、スーパーコンピュータやメインフレームなどのマスターノードが存在し、多くの子ノードを管理するマスタースレーブ方式や、各ノードに違いがなく、各々が自律的かつ協調的に処理をするノンセントラライズな方式も考えられます。本ブログでは、特に言及しない場合、後者の、特別な機能を持つ指揮ノードは存在せず、各々が独自のアルゴリズムのルールに従って協調的に動作する、ノンセントラライズな方式を前提にしている方式を前提にしているものとします。このようなアルゴリズム群を、自律分散システムと言います。

同期・非同期システムとラウンド

　このアルゴリズムを紹介するうえで、重要な要素のひとつは、ラウンドという概念です。多くのシステムを設計するうえでも同様ですが、分散システムを考えるうえでも、とても重要になる概念の一つに、同期・非同期という概念があります。

　実は、同期・非同期という言葉は、とても厄介で、分野によって意味合いが異なることがあります。ここでは、その中で2つの概念を紹介します。まずは、このブログのコンテキストでもある、多くのプログラミングや計算機科学のアルゴリズムなどで利用される同期・非同期を示します。その後、ネットワーク通信などで主に使われる同期・非同期の紹介をしようかと思います。我々は前者の方の話をしていきますが、その中の概念のひとつにあるラウンドの話もしていこうかと思います。

　分散システムを始めとする計算機科学の分野における同期・非同期に関してです。この分野における同期・非同期とは、

• 同期：処理の順番が定義されており、ひとつの処理が終了するまで他の処理は待機し、処理が終了したら次の処理が実行されます。プログラミングの分野で言えば、関数呼び出しをしたら、呼び出した関数の処理が終わるまでその先は処理されないことを意味します。
• 非同期：処理が並行で実行され、自分の処理が終了すると、お互いの処理が終了することなく次の処理を始めます。プログラミングの分野で言えば、Futureで関数呼び出しをつなげていき、処理の本当に最後の部分でawaitするような感じの処理がこれにあたります。

　一方で、ネットワーク通信などの分野で使われる同期・非同期に関してです。もしかしたら、センサネットワークの一部の通信なんかはこれを使うかもしれません。この分野における同期・非同期とは、

• 同期：通信時に、送信側と受信側がクロックを合わせておき、予め決めておいた一定のタイミングで通信を開始する。
• 非同期：送信側と受信側でクロックを合わせるなどはせず、送信側が自由に送信し、受信側も自由なタイミングで受信または受信処理をする。

　私は、後者の同期・非同期の内容はあまり聞くことはありませんが、分野によってはこのような違いがあるようです。

　では、次にラウンドの話をして行こうかと思います。本ブログでは、前者の同期・非同期モデルの、非同期である処理を並行で行い、自分の処理が終了しても他の処理を待たずに次の処理をする非同期モデルを前提とします。そのうえで、基本的に処理は非同期で行うが、非同期処理をブロック単位で考えた場合には、同期システムのように振る舞う際に、このブロック単位を同期システムのように振る舞うシステムを、semi-synchronous model 何かとも呼びます。日本語でいうと、半同期システムとでも呼ぶのでしょうか？このブロック単位で処理するブロックをラウンドといいます。ラウンドとラウンドの切れ目では、同期システムのように振る舞いますが、そのラウンド内では、完全に非同期処理として振る舞うことが可能になります。この投稿で紹介するアルゴリズムは、このsemi-synchronousモデルを利用したアルゴリズムとなります。

　ちなみに、この同期部分をどのように実現するのか？ということも疑問に思ったりすることが多いと思います。分散アルゴリズムでは、こういったモデルを前提としておくが、どのように実現するかの実装部分に関してはあまり言及されていないことが多いです。ここだけ何故かマスタースレーブ方式に近いようなこと（ノードにラウンド終了フラグのセンサーを付けておき、インフラはそれを読み取りすべてのノードの処理が終わったら次のラウンドに行ける簡単なシグナルを出すような方法とか）をすることも考えられますし、時間や計算のコストはかかりますが、通信でラウンドの終了の合意問題を解くなんてことも（場合によっては）可能かもしれません。（ノード数がわかっていない空間で合意問題を解くのは少し難しい気もしますが。選挙をする際に、投票者数の母数がわかっていないと、勝者が決定できないですよね。）とはいえ、決定方法がまったくないわけではないので、何らかの方法でラウンドの終了を決定します。

故障

　分散システムにおいて、ノードの故障というのはついて回り、逃げられないもののひとつです。故障は、昔から非常によく考えられており、非常に様々な故障が定義されています。ここでは、古典的で代表的な3つの有名な故障を紹介し、下記のアルゴリズムで適応可能な故障について説明します。

　古典的で代表的な分散システムの故障は以下のようなものがあります。

• クラッシュ故障：ノードが完全に故障して機能しないような故障を示します。タイヤがぶっ壊れて動けないのに、通信は生きているとかは、この故障には含めないことが多く、Windowsのブルー画面や、Macのグレー画面などになって、再起動しないと動かないような状態に壊れた場合にクラッシュ故障とします。もしくは、掃除の作業員の方が間違ってPCクラスタの電源を抜いちゃって、掃除機をプラグに刺しちゃったりして、再起動しないと使えないようなときにもクラッシュ故障とします。
• オミッション故障：通信経路が壊れている場合にはオミッション故障といいます。ノード自体は正常に動作しており、Wi-Fiルータが壊れていて通信ができないなどの場合に利用します。これは、分散システム内の通信が前段した場合もそうですが、ある特定のノード間での通信だけが問題がある場合でも、オミッション故障といいます。
• ビザンチン故障：上記では、ノードが壊れている場合、通信経路が壊れている場合の故障に名前がついていることがわかりました。基本的には、残りの故障をまとめてビザンチン故障といいます。例えば、サイバー攻撃を受けて意図しない振る舞いを始めた場合や、ノードは生きているように見えるが、実はタイヤがぶっ壊れていて空転している場合、OSが半分壊れているが実は通信は成功している場合、宇宙線を浴びてノードのメモリ状態に異常を含んでいるが、なんとなく正しそうに動いているが、よく見ると（時間が経っていくと）壊れているように見える場合など、ありとあらゆる問題をビザンチン故障といいます。

　本アルゴリズムでは、攻撃者が1-interval connectivity graphの前提を維持したままで、各ノードの通信を任意にいじることを許容しています。メッセージの伝搬を阻害するために、攻撃者がこのアルゴリズムにおけるネットワークを操作することができます。この様に、攻撃者が要るような故障は、ビゼンタイン故障と呼ぶことが多いです。

ネットワークモデル

　ネットワークが何かは、流石に不要かと思います。インターネットでも良いですし、家庭のWi-Fi環境からオフィス・工場にだってWi-Fi環境はあると思います。ここでは、このアルゴリズムが前提とするネットワークに関して書きます。

　ネットワークには、ノードとエッジが存在します。ノードには、通信機器を積んだようなセンサーであったり、通信機器を積んだ掃除ロボットなどのような、計算能力と記憶能力を持ち、かつ通信能力を持つデバイスのようなものです。ノードは、ある一定エリアの中でのみ動作し、その外に出ることはありません。

　エッジとは、ノード間で通信可能である組を指します。ノードAとノードBの間のエッジといった場合には、ノードAからノードBに対して、通信を用いてメッセージを送信することが可能であることを示します。その上で、このアルゴリズムにおいては、ノード間の通信にはWi-Fi等の無線通信を前提としており（無線通信でなくても理屈上同等の環境は十分にあり得ますが）、全てのノードが他の全てのノードと通信可能なわけではありません。Wi-Fiなどの環境の場合には、せいぜい通信可能範囲は遠くても500mも飛ばないと思います。2000mの距離で通信をするためには、4ノードがメッセージをリレーすることで端から端までメッセージを飛ばすことが可能になります。1辺が2000mの正方形の対角線上にメッセージを飛ばしたければ、6台程度のノードを経由してメッセージを転送することで通信することができます。

　ノードは、近隣ノードにどのようなノードがいるのかは知る必要がありません。ただし、メッセージを受信した際には、送信ノードが通信可能な範囲にいるノードであることを知ることができます。メッセージを送る際にも同様のことが言えます。上記では、ノードAからノードBが通信可能であればエッジがあると書きましたが、実際には、近隣ノードが誰であるかは送信ノードもわかっていません。そのラウンドで、メッセージを通信可能な範囲にいるノードに対してメッセージをブロードキャストするだけで、誰に送信するかは指定することはありません。

　このアルゴリズムでは、各ラウンドで通信可能なノードのセットは変わることができます。一部のノードが変わるかもしれませんし、全てが変わっているかもしれません。このアルゴリズムでは、周りにどのようなノードがいるのかの前提を置きません。

1-interval connected graph

　このアルゴリズムでは、上記のようなネットワークモデルを前提として、1-interval connected graphという概念を利用します。前述で、ある範囲内に存在するノードが無線通信を利用してメッセージを交換すると書きました。また、各ラウンドでメッセージを近隣ノードから受信し、近隣ノードにメッセージをブロードキャストすることで、相手を意識することなくメッセージを送信するとも書きました。この前提をうまく利用するための追加の前提が、1-interval connected graphです。

1-interval connected graphとは、各ラウンドにおいて以下のような状態になります。

• あるラウンドでエッジを全てトレースしてネットワークのトレース情報のスナップショットを作った場合に、そのネットワークに離小島が存在しない（パーティションが存在しないネットワーク）
• 全てのラウンドで、上記の状態が維持できているものとする。しかし、ネットワークの形状（トポロジ）に関しては、毎回全く異なることができる。各ラウンドで、全てのノードが移動して近隣ノードが前ラウンドと全く異なったとしても、上記の前提があることにより成立するアルゴリズムもあります。
  

　実は、紹介している論文内では、1-interval connected graphの拡張でt-interval connected graphというモデルを使ってもっと柔軟なことができるような話も出てきます。今回は、その話を入れるととても長くなる＆複雑になる（かもしれないので、省略します。また今度、元気な時に、そんな話もこのブログで書こうかとは思っています。）

本題のアルゴリズム

　では、本題のネットワークを構成するノード数を特定することができるアルゴリズム本体の話をしようかと思います。このアルゴリズムは本当にシンプルです。

　前提ですが、環境内にあるノード数は、アルゴリズムの実行時点から、一旦ノード数が決定されるまで変わらないものとします。各ノードは、各々がユニークなIDを持っているとして、他のノードと同じIDを共有することはできません。各ノードは、他のノードのIDを外観で識別することはできず、メッセージの交換でのみ認識することができます。また、アルゴリズムの実行中にノードが故障することはないものとします。通信に関しても、誰とも通信できない状態はすべてのラウンドにおいて起きないものとします。さらに、アルゴリズムの実行中に、どのラウンドにおいても、外部からネットワークを観測した時に、ネットワークは常に1つで、通信不能なパーティションが発生しないものとします。また、このアルゴリズムは、実行中に変更されることは無く、終始同じロジックで全てのノード上で実行されている必要があります。

　このアルゴリズムは、何ラウンドも繰り返すことで最終的にノード数を決定できるのですが、まずは各ラウンドで何をするのかを示します。ラウンド内では、4つのフェーズに分割されます。初期化フェーズ、メッセージ送信（ブロードキャスト）フェーズ、メッセージの受信フェーズ、カウントフェーズです。初期化フェーズは、最初のラウンドの最初のフェーズでのみ実行される特別なフェーズです。送信と受信に関しては、論理的に分けられているだけで、時間的に分割されているわけではありません。なお、このアルゴリズムは、対象空間の全てのノード上で実行されている必要があります。また、基本的には、最初のラウンドの初期化フェーズは同じタイミングで行われることが望ましいです。

ラウンド内での処理

1. 初期化：最初のラウンドの一番最初に1回だけ処理する。

   • 各ノードは、自分自身が持っている情報の初期化を行う。

     Node x = {id = x, current_nodes = [ x ]}
     

     x は自然数かつシステム内でユニーク
   • 他のノードから受信するリストを初期化する

     Node x = {id=x, current_nodes = [ x ], received_nodes = [  ]}
     

2. メッセージ送信：各ノードは、隣接ノードに自分が持っている数を送信（ブロードキャスト）する

   • 例: Node1 が送信

     Node1 の送信時の状態 
     Node1 {id = 1, current_nodes = [ 1 ], received_nodes = []}
     Node1 が送信するメッセージ  {id = 1, current_nodes = [ 1 ]}

3. メッセージ受信：各ノードは、受信したメッセージをリストに保存する

   • 例: ノード1 がメッセージを送信して、ノード2が受信したとする

     送信時のメッセージは、メッセージ送信を参照
     メッセージを受信
     Node2 {id = 2, current_nodes = [ 2 ], received_nodes = [{id = 1, current_nodes = [ 1 ]}, ..... ] 
     

     もし、Node1以外にもメッセージがあれば受信セットに登録されます。

4. メッセージをベースに各ノードが各々の状態を更新する：current_nodeを更新する。更新ルールは、受信ノード自身がまだ知らないNodeIDがあれば、current_nodesに追加する。受信ノードリストをリセットする。

   • 例: メッセージ受信のNode2をサンプルに見てみる

     Node2 {id = 2, current_nodes = [ 2 ], received_nodes = [{id = 1, current_nodes = [ 1 ]} ]
     新Node2 = {id = 2, current_nodes [1, 2]} , received_nodes = []}
     

次のラウンドへ続く。

ラウンドの処理

　ループを繰り返すことで、ラウンド内の処理を毎回実行します。現状の出力は、ラウンドの終了時に各ノードが現在の最新の自分の状態を出力します。出力方法は、そのアプリケーションによります。最もシンプルなのは標準出力です。アプリケーションが単にネットワークの全体をモニタリングしたいときなどは、普通に標準出力かもしれません。一般的に、分散アルゴリズムは、もっとアプリケーション側の別の分散アルゴリズムに利用されていることも多いです。その場合は、自分を利用している別の分散アルゴリズムに現在の状態を渡す感じになるかと思います。

動作の例

　以下は、上記のアルゴリズムの振る舞いを簡単に示した図になります。下記の{}内には以下の情報が書かれています。

• {自ノードID, 自分が持っているNode情報, 他ノードから受けたメッセージのセット}
• "他ノードから受けたメッセージのセット"に関しては、情報量が多いのでわかりやすくするために簡単に書いてあります。

　Node1からNode5までのノードが一直線に並んでいる状態を考えます。この際に、エッジは両サイドの1ノードとしかないものとします。また、ノードは動かないものとします。初期状態では、自分が持っているNode情報には自分だけが入っています。最初のメッセージ交換で隣接ノードの情報が"他ノードから受けたメッセージのセット"に入ります。そして、updateフェーズで"自分が持っているNode情報"を更新します。これを繰り返していくことで、すべてのNode情報を全Nodeが取得することができます。

　前述で1-interval connectivity graphを前提としており、ラウンドを繰り返して、すべてのノードが同じ値を取るときには安定したといえます。これを長いスパンで見たとき、たとえば、1日目に安定した。次の日にまた別のノードが追加されたときには、同じアルゴリズムが動いていれば自動的に新しいノードを検出することができるメリットもあります。ただし、このアルゴリズムではノードの故障を前提としていないため、電池切れやその他の理由でノードが故障したとしても、故障ノードを除外することができないデメリットもあります。また、ノード数が大きくなればなるほど安定するまでに時間がかかりますし、例えば、ノード群が一直線に並び、左右1ノードずつとしか通信できないで固定されている場合などトポロジーによっては最大時間が長くなったりします。例えば、1万台が上の図のように横一線に並んだ場合等のメッセージの伝搬に必要なラウンド数や、受信時のメッセージを保存しておくメモリ量は、組み込みシステムのメモリ等を考えた場合には意識が必要な場合もあります。

　もし、もっと確実な解を毎回必ず必要とする場合には、何らかの前提条件を厳しくしたアルゴリズムを探すことが求められます。もしくは、そもそものアーキテクチャを考え直すべきかもしれません。例えば、master-slave方式のアーキテクチャに変え、メインフレームを1台導入して、空間のどこからでも無線通信のインフラが用意されており、任意のタイミングでメインフレームのマスターノードに通信可能な前提であれば、上記のような分散アルゴリズムは不要になります。しかし、もっと安価にシステムを構築したく、特別なノードを用意することなく、設置して時間が経てば安定すればいい場合には、このようなアルゴリズムもありではないでしょうか？

まとめ

今回は、2024のアドベントカレンダーのひとつのネタとして、14年ほど前の論文に面白いネタがあったので、分散アルゴリズムって案外シンプルでしょってのを知ってもらうためにポストを書いてみました。この論文では、自律分散型の可動式のノード群が、自律的にネットワーク内に存在するノード数を検出可能なアルゴリズムを紹介しました。同論文のメインの場所は、このアルゴリズムをベースにして、リーダーを選出したり、そのリーダーのいるグループのメンバーを決定するグループメンバーシップのアルゴリズム、そしてそのグループ内で合意をとる合意問題が紹介されています。今回は省きました。

例えば、上記の合意問題までが実現すると、ある畑では、水を追加で必要なのか、それとも水が多すぎて他の処理をしたほうが良いのかなどをシステムが自律的に決定できるようになると思います。しかし、一般的なサーバなどを置くシステムに比べ、処理（ネットワーク内のノード数を決定するなどのアルゴリズムひとつずつ）にかかる時間は長くなります。なので、どんなアプリケーションにでも簡単に適応させられるわけではありませんが、適応可能なアプリケーションであれば、場合によってはインフラにかけるコストでノードを増やすなんてことも可能な場合もあると考えられます。

実は、最新のネタを紹介したかったのですが、その最新の論文を読んでいる間に、今回紹介した論文にたどりつき、こちらを紹介することにしました。