Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• We consider linearizable implementations of shared FIFO queues and general deterministic objects on a distributed message-passing system which provides a real-time timer. The effeciency of an implementation is measured by the worst-case response time res_time(op)for each operation op of the implemented objects. We show the following results under the assumption that all message delays are in the range[d-u, d]for some constants d and u(0≦u≦d). We first present an implementation of deterministic objects with res_time(op_a)=u for any ack-type operation op_a and res_time(op_v)=2d for any val-type operation op_v, where an ack-type operation is an operation which always returns a unique response and a val-type operation is an operation which is not ack-type. We also consider an implementation of FIFO queues, which have two kinds of operations, enq(v)and deq. We show that, for any implementation of FIFO queues, (1)res_time(enq(v))≧u(n-1)/n holds for some v where n is the number of processes, and(2)res_time(deq)≧d+u/2 holds in the case of u≦(2/3)d.

• 社団法人電子情報通信学会の論文
• 1998-05-25

著者

• MASUZAWA Toshimitsu

  the Graduate School of Information Science and Technology, Osaka University

• INOUE Michiko

  the Graduate School of Information Science, Nara Institute of Science and Technology(NAIST)

• Masuzawa Toshimitsu

  The Graduate School Of Information Science And Technology Osaka University

• Masuzawa Toshimitsu

  The Graduate School Of Information Science Nara Institute Of Science And Technology(naist)

• TOKURA Nobuki

  the Faculty of Engineering Science, Osaka University

• Tokura N

  Osaka Univ. Osaka Jpn

• Tokura Nobuki

  The Faculty Of Engineering Science Osaka University

• Inoue Michiko

  The Graduate School Of Information Science Nara Institute Of Science And Technology(naist)

関連論文

• Fault-Tolerant and Self-Stabilizing Protocols Using an Unreliable Failure Detector
• Timed Uniform Atomic Broadcast in Presence of Crash and Timing Faults(Foundations of Computer Science)
• Wait-Free Linearizable Distributed Shared Memory
• Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model
• High-Level Synthesis for Weakly Testable Data Paths(Special Issue on Test and Diagnosis of VLSI)
• A Simple Parallel Algorithm for the Medial Axis Transform (Special Issue on Architectures Algorithms and Networks for Massively parallel Computing)
• A Parallel Method for the Prefix Convex Hulls Problem
• Distributed Leader Election on Chordal Ring Networks
• Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model(Parallel and Distributed Computing,Foundations of Computer Science)
• Scheduling for Gather Operation in Heterogeneous Parallel Computing Environments
• Fault-Tolerance of Distributed Algorithms : Self-Stabilization and Wait-Freedom(Special Issue on Algorithm Engineering : Surveys)
• A Non-scan DFT Method at Register-Transfer Level to Achieve 100% Fault Efficiency (特集:システムLSIの設計技術と設計自動化)
• Parallel Selection Algorithms for CGM and BSP Models with Application to Sorting (特集 並列処理) -- (並列・分散アルゴリズム)
• Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System(Special Section on Discrete Mathematics and Its Applications)
• Test Pattern Ordering and Selection for High Quality Test Set under Constraints

もっと見る 閉じる

スポンサーリンク