マルチトライアルテクニック

シュナイダーらによるマルチトライアル手法は分散アルゴリズムに使用され、対称性の破壊を効率的に行うことができます。対称性の破壊は、たとえば、多くのエンティティが同じリソースに同時にアクセスしたいリソース割り当て問題で必要です。多くのメッセージパッシングアルゴリズムでは、通常、メッセージ交換ごとに対称性の破壊を 1 回試行します。マルチトライアル手法は、メッセージ交換ごとにより多くの試行を行うことで、このアプローチを超えています。^[1]

たとえば、O(Δ)頂点彩色を計算するための単純なアルゴリズムでは、Δ はグラフの最大次数を表しますが、彩色されていないすべてのノードは利用可能な色をランダムに選択し、隣接するノードが（同時に）同じ色を選択しない場合はその色を保持します。マルチトライアル技法では、ノードは通信ラウンドごとに選択する色の数を徐々に増やします。この技法により、必要な通信ラウンドを指数関数的に削減できます。ただし、最大次数 Δ が小さい場合は、より効率的な技法、たとえば Richard Cole とUzi Vishkinによる（拡張）コイントス技法が存在します。^[2]

• Schneider, J. (2010)、「分散対称性破壊のための新しい手法」(PDF)、分散コンピューティングの原理に関するシンポジウムの議事録
• Schneider, J. (2008)、「成長制限グラフのためのログスター分散最大独立集合アルゴリズム」(PDF)、分散コンピューティングの原理に関するシンポジウムの議事録