My Projects Jp

　この投稿は、 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.  この記事で書くことは何？ 　この投稿では、2021 年のアドベントカレンダー用に書くので、前後の投稿とは関係なく前後のコンテキストがわからなくても読めるように書こうかと思っています。もしかしたら、この投稿がこのBlog の初投稿になっているかもしれません。 　本投稿では、分散システムはそんなに詳しくないけど、ちょっと興味があるって人が、分散システムに入門できればと思って書いています。分散アルゴリズムの基本は案外簡単でもある事を知ってもらい、その応用アルゴリズムの理解に役立てばと思います。入門にあたり、重要となる考えに時間の概念があります。この記事内では、特に分散システムの時間に関して書いていこうかと思います。分散アルゴリズムの基本的な概念はとてもシンプルですので、分散アルゴリズムを難しそうに思わなくなる人が増えればと思います。 2.  背景 　分散システムは、我々の社会で至って普通に利用されているシステムの一つです。 　分散システムという分野は、コンピュータの歴史では比較的歴史の古いものひとつです。コンピュータは、単一の巨大な大型でパワフルな計算機に集中的に計算する時代を経験したり、それらを低価格で実現できるように等の理由により並行処理ができるようにしてみる様な時代を経験してみたりを繰り返しながら進化を続けています。計算機を複数利用することで、システムを機能単位でモジュールを分割することができたり、大きい計算量のある処理を分割・並行処理を行い計算時間の短縮が得られるメリットがあります。 　一方で、複数の機能群や計算機群の中で一つでも故障する事で、全てが利用できない様な状態は困ります。分散システム内の一部が故障しないようにする・故障してもシステム全体としてはサービス可能な構造を作る方法も様々なアプローチがあります。故障を管理するための計算機を用意するのもひとつの方法です。しかし、故障を管理するためのシステムが故障すると故障が管理できないなどのSinglePointOfFailure があります。自律分散システムでは、この様に単一の故障管理機構を利用することなく、システムが自律的に故障とうまく共存ししながら、目的とするサービスを提供し続けることを目的とします。もちろん、システム内の一部が故障した場合には、パフォーマンスの低下や一部の機能が利用で...