同期装置（アルゴリズム）

コンピュータサイエンスにおいて、シンクロナイザーは、非同期プロセッサ ネットワーク上で同期アルゴリズムを実行するために使用できるアルゴリズムであり、これにより、非同期システムを同期ネットワークとして実行できるようになります。

この概念は、もともと (Awerbuch、1985) で、時間とメッセージの複雑さに関して異なるトレードオフを提供するalpha、beta、gammaという 3 つの同期アルゴリズムとともに提案されました。本質的には、これらは、非同期アルゴリズム (グローバル クロックのないネットワークで動作する) が、同等の同期アルゴリズムよりも設計が難しく、効率が劣ることが多いという問題に対するソリューションです。同期を使用することで、アルゴリズム設計者は簡略化された「理想的なネットワーク」を扱い、その後、より現実的な非同期ケースで動作するバージョンを機械的に作成できます。

Awerbuch がオリジナルの論文で提示した 3 つのアルゴリズムは次のとおりです。

• アルファ同期装置: 時間の複雑さは低いですが、メッセージの複雑さは高くなります。
• ベータ同期装置: 時間複雑度は高いが、メッセージの複雑度は低い。
• ガンマ同期装置: 時間とメッセージの複雑さをかなり低く抑えることで、アルファとベータの間の合理的なトレードオフを実現します。

オリジナルの論文以降、他の同期アルゴリズムも文献で提案されてきました。

• Baruch Awerbuch (1985) 「ネットワーク同期の複雑さ」(PDF)。