TY - GEN
T1 - Controlling memory access concurrency in efficient fault-tolerant parallel algorithms
AU - Kanellakis, Paris C.
AU - Michailidis, Dimitrios
AU - Shvartsman, Alex A.
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 1995
Y1 - 1995
N2 - The crcw pram with dynamic fail-stop errors is a faultprone multiprocessor model for which it is possible to control memory access redundancy while guaranteeing the reliability of efficient algorithms. Concurrent common reads and writes are necessary to handle dynamic faults and in this paper we show how to significantly decrease this concurrency and how to bound it in terms of the number of processor faults. We describe a low concurrency, efficient, and fault-tolerant algorithm for the Write- All primitive: “using ≤ N processors, write 1’s into N locations”. This primitive serves as the basis for efficient faulttolerant simulations of algorithms written for fault-free prams on faultprone prams. For any dynamic failure pattern F, our algorithm has total write concurrency ≤ |F| and total read concurrency ≤7 |F| log N, where |F| is the number of processor faults (e.g. no concurrency in a run without failures). Previous algorithms used Ω (N log N) concurrency even in the absence of faults. We also present an optimal fault-tolerant erew pram algorithm for Write-All when all processor faults are initial.
AB - The crcw pram with dynamic fail-stop errors is a faultprone multiprocessor model for which it is possible to control memory access redundancy while guaranteeing the reliability of efficient algorithms. Concurrent common reads and writes are necessary to handle dynamic faults and in this paper we show how to significantly decrease this concurrency and how to bound it in terms of the number of processor faults. We describe a low concurrency, efficient, and fault-tolerant algorithm for the Write- All primitive: “using ≤ N processors, write 1’s into N locations”. This primitive serves as the basis for efficient faulttolerant simulations of algorithms written for fault-free prams on faultprone prams. For any dynamic failure pattern F, our algorithm has total write concurrency ≤ |F| and total read concurrency ≤7 |F| log N, where |F| is the number of processor faults (e.g. no concurrency in a run without failures). Previous algorithms used Ω (N log N) concurrency even in the absence of faults. We also present an optimal fault-tolerant erew pram algorithm for Write-All when all processor faults are initial.
UR - http://www.scopus.com/inward/record.url?scp=85027488904&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85027488904&partnerID=8YFLogxK
U2 - 10.1007/3-540-57271-6_30
DO - 10.1007/3-540-57271-6_30
M3 - Conference contribution
AN - SCOPUS:85027488904
SN - 9783540572718
VL - 2
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 146
EP - 180
BT - Distributed Algorithms - 7th International Workshop, WDAG 1993, Proceedings
A2 - Schipe, Andre
PB - Springer Verlag
T2 - 7th International Workshop on Distributed Algorithms, WDAG 1993
Y2 - 27 September 1993 through 29 September 1993
ER -