分散計算における全順序保証プロトコルの適応的選択

情報処理学会 Web Site 参考文献16件

書誌事項

タイトル別名
  • ブンサン ケイサン ニ オケル ゼンジュンジョ ホショウ プロトコル ノ テキオウテキ センタク
  • Adaptive Selection of Total Ordering Protocols in Distributed Computation
  • 分散処理

この論文をさがす

抄録

分散環境では複数のプロセスが通信をするため，メッセージの全順序保証を利用した通信は不可欠である．また，さまざまな実行環境が存在し，環境はたえず変化するため，最適な全順序保証プロトコルをあらかじめ選択することは困難である．そこで，環境変化へ動的に適応する全順序保証プロトコルが求められる．従来の適応的全順序保証プロトコルは悲観的全順序保証プロトコルを基盤にしている．そこで本論文では悲観的手法に加えて楽観的手法も対象とした適応方法を提案する．適応方法を楽観的手法にまで広げたことにより，異なる手法のプロトコルを動的に選択し環境変化に適応することが可能である．2 つの手法のコストを比較した場合，楽観的手法はメッセージの送信頻度に影響を受けやすく，悲観的手法は通信遅延の影響を受けやすい．適応的選択は，時々刻々変化する実行環境に対して，順序付けコストが最小の手法を選択することになり，これを実現するために，それぞれの手法に対して順序付けコストを評価し比較する方法を提案する．また，メッセージの全順序保証を維持するため，楽観的手法を考慮したプロトコルの切替え方法を提案する．例としてTime Warp とABCAST を対象としたコスト評価・比較，切替えについて具体的に述べ，本方式の有効性をシミュレーションにより検証する．

In distributed systems, the communication among group members often needs ordered messages to guarantee that every member receives the messages in the same order. Oftentimes, changes in distributed computing environment occur and this undermines the assumption of any ordering algorithm. Therefore, it is difficult to presume a suitable ordering algorithm and apply a single algorithm throughout the lifetime of the system. In this paper, we present a protocol to dynamically select a suitable ordering protocol from the optimistic and pessimistic protocols. With optimistic protocol, it is possible to reduce the affect of the network latency which is not negligible in the pessimistic protocol, because the optimistic protocol delivers messages immediately after receiving them. The optimistic protocol though incurs high ordering cost during rollback, and so in this case, it is worth using the pessimistic algorithm instead. We propose the estimation, evaluation, and switching methods to be used in selecting the appropriate ordering protocol. To verify the validity of our proposed protocol, we simulate the protocol using Time Warp and ABCAST.

収録刊行物

参考文献 (16)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ