非同期最大モデルの収束特性

G = (V, E) を n 頂点の連結有向グラフとする。G の頂点に集合 \1, 2, , n\ から値を割り当て、次のルールに従って値を更新する：ランダムに一つの頂点を選び、その頂点の値を近傍内の値の最大値に更新する。この頂点の値は減少する可能性がある。このランダムプロセスを非同期最大モデルと呼ぶ。このプロセスを繰り返すと、強く連結した有向グラフでは最終的にすべての頂点が同じ値を持ち、モデルは収束したと見なされる。無向の場合、期待される収束時間は漸近的に (n n) および O (n²) であり、これらの境界は厳密である。さらに、G の頂点拡張を用いて O (n n) で収束時間を特徴づける。これは大規模なグラフのクラスに対してより良い上限を提供する。さらに、収束までのラウンド数は高い確率で O ( (n n) g (n) ) であることを示す。ここで g (n) は n のとき 1g² (n) 0 を満たす。強く連結した有向グラフの場合、収束時間は O (nb² + n' n) であり、b は有向サイクルの長さを測定するパラメータ、' は頂点の拡張を測定するパラメータである。