リングネットワークにおける一様な自己安定 k-相互排除システム
スポンサーリンク
概要
- 論文の詳細を見る
分散システムにおけるフォールトトレランスを実現するために,自己安定の概念が1974年Dijkstraによって提案された.自己安定システムとは,システムの初期状況に関係なく,有限時間内にシステムが正しい(安定な)状況に遷移するシステムである.すなわち,自己安定システムは,一過性のエラーが生じても有限時間内にシステムが(自動的に)再び正しく動作するシステムである.このため,自己安定の概念はフォールトトレランスの理論的基盤と考えられる.分散k-相互排除問題は,同時に臨界領域に存在するプロセスの数がk以下であることを保証する問題である.本論文では,自己安定k-相互排除問題を考え,自己安定k-相互排除システムを提案し,その正当性を示す.提案するシステムは,一様なリングネットワーク上で実行される.本稿では単方向リングネットワークと双方向リングネットワークを検討する.さらに,任意のk個のプロセスが同時に臨界領域に入ることができる,という自然な要請を加えた自己安定k-相互排除問題は単方向リングでは解くことができないことも示す.われわれの提案する双方向リングネットワーク上の自己安定k-相互排除システムはこの要請を満たしている.
- 一般社団法人情報処理学会の論文
- 1994-06-15
著者
関連論文
- 全二分木の簡潔な表現 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 任意のカバー時間を持つ木の構成法 (アルゴリズムと計算機科学の数理的基盤とその応用)
- Multiple Random WalkのCover Timeについて (アルゴリズムと計算機科学の数理的基盤とその応用)
- 高速復元可能な接尾辞配列圧縮法(FIT推薦論文)(情報・システム基礎)
- メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界
- 連続確率分布枝重み付きDAGに対する最長路長さ分布の計算 (理論計算機科学の深化と応用)
- Metropolis Walkのcover timeにおけるタイトな上界 (理論計算機科学の深化と応用)
- 2点連結な直並列グラフ上の高速なランダムウォーク (理論計算機科学の深化と応用)
- DS-1-8 Computing the Exact Distribution Function of the Longest Path Length in Directed Acyclic Graphs with Exponentially Distributed Edge Lengths
- RA-003 A Counting-Based Approximation the Distribution Function of the Longest Path Length in Directed Acyclic Graphs
- グラフ上の線形Cover Timeランダムウォーク実現の必要条件
- 辺上を移動するロボット1台による最適な多角形探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 確率的な枝重みをもつ有向非巡回グラフにおける最長路長さの分布関数の解析的な計算に関する考察 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比とその解析 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 局所的な次数情報を用いた無向グラフの探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- グラフ上の線形Cover Timeランダムウォーク実現の必要条件 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 重み付きグラフ上の枝被覆に対する次数均等化と重み最小化 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 局所探索法による熱力学的DNA配列設計の改良 (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 移動ロボットによる長尺物運搬問題に対する分散アルゴリズム (計算モデルとアルゴリズム)
- A Dynamic Reconfiguration Tolerant Self-stabilizing Token Circulation Algorithm in Ad-Hoc Networks (Evolutionary Advancement in Fundamental Theories of Computer Science)
- アドホックネットワーク向けトークン巡回自己安定分散アルゴリズム
- A Universal Self-Stabilizing Mutual Exclusion Algorithm (New Developments of Theory of Computation and Algorithms)
- 単方向リングネットワークでの一様なランダム化自己安定相互排除
- 分散システムにおける資源割り当てアルゴリズム(計算量理論)
- 双方向リングネットワーク上での自己安定2:相互排除(計算機構とアルゴリズム)
- DS-1-10 Approximating Distribution of Optimization Problems with Normally Distributed Edge Weights by Approximate Counting
- 拡張された分散$k$-相互排除(計算量理論)
- 拡張された分散κ-相互排除
- P2Pシステムにおけるブルームフィルタを利用したオーバレイネットワークの構築(セッションB-1:P2P・オーバーレイネットワーク(1))
- 負荷分散枝被覆問題に対する最適性とアルゴリズム
- 局所情報を用いたスケールフリーネットワークの探索
- 目的関数調整法を用いたスケジューリング問題の一解法(アルゴリズム理論)
- 自己安定リーダー選挙MPPにおける領域複雑度の上下界について
- 構造化オーバレイネットワークにおける故障耐性向上のための経路多重化法(ディペンダブルコンピューティング)
- 白板を利用したモバイルエージェントによる効率的なグラフ探索
- 全二分木の簡潔な表現
- 高頻度なフレーズの検索が高速な索引
- トポロジ変化に対して出力の変化数を最小化する全域木構成分散アルゴリズム
- 体験的な分散アルゴリズム協調学習を支援するシステムの提案
- ET2009-86 アルゴリズム学習向け誤り発見型演習のためのカスタマイズ可能な問題自動生成システム(学習データの蓄積・分析・共有/一般)
- 複数グループのオンライン議論を同時にサポートする自動助言システムの構築(セッション議論支援)
- アルゴリズム学習における間違い探し形式の演習課題を自動生成する手法の提案と評価
- アドホックネットワークの経路構築における非協調行動の抑制手法について(アドホックネットワーク,無線ネットワーク,有線/無線シームレスネットワーク,ネットワーク制御,無線通信一般)
- モバイルP2Pにおけるレーン構造を用いた資源探索手法(セッションB-8:P2P・オーバーレイネットワーク(2))
- P2Pシステムにおける動的ランダムオーバーレイの構築手法(セッションB-1:P2P・オーバーレイネットワーク(1))
- モバイルP2Pにおけるレーン構造を用いた資源探索手法(セッションB-8:P2P・オーバーレイネットワーク(2))
- P2Pシステムにおける動的ランダムオーバーレイの構築手法(セッションB-1:P2P・オーバーレイネットワーク(1))
- P2Pシステムにおけるブルームフィルタを利用したオーバレイネットワークの構築(セッションB-1:P2P・オーバーレイネットワーク(1))
- 議論活動における調査資料の活用を支援するシステムHAKASEの構築
- 正規分布に従う枝重みをもつグラフにおける最小全域木コストの分布関数の近似手法
- A-028 ある種の不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- The Distributed Anonymous Resource Conflict Resolution Problem
- A-023 接尾辞木に対する二分木化と簡潔データ構造による圧縮(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- A-022 圧縮された接尾辞配列を用いた近似文字列照合(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- RA-007 高速復元可能な接尾辞配列圧縮法(モデル・アルゴリズム・プログラミング,査読付き論文)
- Distributed Motion Generation for Carrying a Ladder by Two Omni-Directional Robots (Algorithm Engineering as a New Paradigm)
- 守備特訓に喘ぐ外野手のための捕球経路問題 (計算機科学基礎理論の新展開)
- Web上の学習ナビゲータの作成法について(e-Learning教育システムの成果と目指すべきもの/一般)
- 匿名ネットワーク上のリーダー選出問題の空間計算量 (計算機科学基礎理論の新展開)
- 同期型交代動作を行うカウンタ機械と有限オートマトン
- データの論理的解析における正関数発見の並列化 (計算機科学基礎理論の新展開)
- 分解可能なしきい関数を用いたデータ解析 (計算機科学基礎理論の新展開)
- ハウ・ツー・ランデブー
- 移動物体回収問題 : ロボットに効率良く物体を回収させるアルゴリズムの設計のために(学生/教養のページ)
- k-集合合意問題を解く故障検知器
- 移動物体回収問題
- 動的近傍操作を用いたDNA塩基配列設計
- 隠れマルコフモデルを用いたDNA配列設計
- 負荷分散セミマッチングにおける最適性について
- DS-1-10 DNA構造変化の特徴解析(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- 故障数制限付きリーダー選挙問題に対する故障検知器
- DNA形態変化におけるエネルギー障壁値の高速近似計算 (計算機科学基礎理論とその応用)
- 世界規模分散ファイルシステムSKINNY
- リングネットワークにおける一様な自己安定 k-相互排除システム
- リングネットワークにおける一様な自己安定k-相互排除システム
- 自己安定相互排除アルゴリズムの実験的評価とその改良
- Minimum Universal Evaluation Tree for Boolean Circuits (Evolutionary Advancement in Fundamental Theories of Computer Science)
- リングの方向付け問題を有限状態数で解く自己安定アルゴリズム(アルゴリズムと計算量理論)
- 量子アルゴリズムによる近似文字列出現頻度問い合わせ (計算機科学基礎理論とその応用)
- 文法圧縮に基づいた圧縮データの自己索引構造化の提案 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 大規模分散フレームワーク Hadoop を用いた接尾辞配列構築 (計算機科学とアルゴリズムの数理的基礎とその応用)
- DS-1-6 MPPモデルにおけるリーダー選挙問題の容量複雑性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- ストリーミング中の頻出アイテム発見アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- 非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- マッチングを用いたパターン形成アルゴリズム
- 枝の重みが確率的なグラフにおける最長路の長さの分布 (計算理論とアルゴリズムの新展開)
- 有向グラフ上の確率的局所多数決ゲーム (新しいパラダイムとしてのアルゴリズム工学)
- グラフ上の局所多数決問題の確率的アプローチ (計算モデルとアルゴリズム)
- ストリーム中の頻出アイテム発見に対するO(loglogN) 領域乱択アルゴリズム
- 1-D-3 グラフ上のランダムウォークとその高速化(特別セッション 若手によるOR横断研究)
- Pattern Formation by Fully Asynchronous Mobile Robots (New Trends in Algorithms and Theory of Computation)
- ストリーム中の頻出アイテム発見に対するO(loglog$N$)領域乱択アルゴリズム (アルゴリズムと計算理論の新展開)
- ランダムグラフ上の多種ランダムウォークの全訪問時間 (アルゴリズムと計算理論の新展開)
- Probabilistic Stabilization under Probabilistic Schedulers (New Trends in Algorithms and Theory of Computation)
- DS-1-16 完全非同期ロボットによるパターン形成(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-15 ストリーム中の頻出アイテム発見に対するO(loglogN)領域乱択アルゴリズム(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 無理数遷移確率ランダムウォークの脱乱択化
- 一般のネットワーク上の移動ビザンチン合意問題について
- 分散システムでの剛性グラフに対する局所交換可能性 (理論計算機科学の新展開)