algorithm - 有向グラフのリーダー選出アルゴリズム

Question

有向グラフが与えられたリーダー選挙アルゴリズムを見つけようとしています。私がこれまでに見つけたのは、ほとんどの LE アルゴリズムがリング ネットワークまたはメッシュ トポロジを持っているということです。誰かが私にいくつかのアルゴリズムを提案できますか?

Answer 1

これについては、Tel による「An Introduction to Distributed Algorithms」の第 7 章で説明しています。「ツリー アルゴリズム」という検索用語になりそうな言及をいくつか示します。これは、ツリーの最小値を見つけるためのかなり単純なアルゴリズムです。Finn のアルゴリズムは、前の章の Wave アルゴリズムへの参照であり、リーダーの選出に使用すると比較的非効率的です。Tel は、任意のネットワークでのリーダー選出の問題はスパニング ツリーの作成と密接に関連していると述べ、Gallager-Humblet-Spira について説明しています。Korach-Kutten-Moran は、一般的なネットワークのトラバーサル アルゴリズムをリーダー選出アルゴリズムに変える方法を説明しているようです。