Multi-trials technique とは

シュナイダー(Schneider)らのマルチトライアル技術は、分散アルゴリズムに採用され、効率的に対称性を破ることができます。例えば、多くのエンティティが同じリソースに同時にアクセスしたいリソース配分の問題では、対称性の崩壊が必要です。多くのメッセージパッシングアルゴリズムは、通常、メッセージ交換ごとに対称性を破る1つの試みを使用する。マルチトライアル技術は、すべてのメッセージ交換でより多くの試みを採用することでこのアプローチを超越しています。
例えば、O(Δ)頂点の色付けを計算するための単純なアルゴリズムにおいて、Δはグラフの最大次数を表し、無色のノードはすべて無作為に利用可能な色を選択し、隣り合わせ(同時に)に同じ色を選択しない限り、マルチトライアル技術では、ノードは、各通信ラウンドにおいて選択された色の数を徐々に増加させる。この技術は、必要な通信ラウンドの指数関数的な減少以上のものをもたらすことができます。しかし、最大次数Δが小さい場合、より効率的な技術が存在する。 Richard ColeとUzi Vishkinによる(延長された)コイン投げ技法。