博碩士論文查詢聯邦系統首頁 聯絡信箱 關於我們 加入我們

本論文已被瀏覽 46 次, [ 造訪詳細資料與全文 ] 29 次,[ 回到前頁查詢結果 ] [ 重新搜尋 ]

Coded Emulation of Shared Atomic Memory for Message Passing Architectures.

作者:Viveck R. Cadambe, Nancy Ann Lynch, Muriel Medard, Peter Musial,
出版單位:Institute of Electrical and Electronics Engineers (IEEE)
核准日期:2016-01-15
類型:Article http //purl.org/eprint/type/ConferencePape
權限:Creative Commons Attribution-Noncommercial-Share Alike.http://creativecommons.org/licenses/by-nc-sa/4.0/....

英文摘要

This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains two main contributions:
(1) We present an atomic shared-memory emulation algorithm that we call Coded Atomic Storage (CAS). This algorithm uses erasure coding methods. In a storage system with N servers that is resilient to f server failures, we show that the communication 0cost of CAS is [N over N−2f]. The storage cost of CAS is unbounded.
(2) We present a variant of CAS known as CAS with Garbage Collection (CASGC). The CASGC algorithm is parametrized by an integer δ and has a bounded storage cost. We show that in every execution where the number of write operations that are concurrent with a read operation is no bigger than δ, the CASGC algorithm with parameter δ satisfies atomicity and liveness. We explicitly characterize the storage cost of CASGC, and show that it has the same communication cost as CAS.

United States. Air Force Office of Scientific Research (Contract FA9550-13-1-0042)

National Science Foundation (U.S.) (Award CCF-1217506)

National Science Foundation (U.S.) (Award 0939370-CCF)

Bae Systems National Security Solutions Inc. (Award 739532-SLIN 0004)


無相關資訊


無相關資訊

 

計畫贊助者: