| Sharing Memory Robustly in Message-Passing Systems |
16 FEB 90 |
27 pages |
| Authors:
Hagit Attiya; Amotz Bar-Noy; Danny Dolev; MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
|
 | Emulators that translate algorithms from the shared-memory model to two different message-passing models are presented. Both are achieved by implementing a wait-free, atomic, single-writer multi-reader register in unreliable, asynchronous networks. The two message-passing models considered are a complete network with processor failures and an arbitrary network with dynamic link failures. These results make it possible to view the shared-memory model as a higher-level language for designing algorithms in asynchronous distributed ... |
|
| Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments |
15 DEC 88 |
25 pages |
| Authors:
Amotz Bar-Noy; Joseph Naor; STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
|
| We present a general method for translating sorting by comparisons to algorithms that compute a Hamilton path in a tournament. The translation is based on the relation between minimal feedback sets and Hamilton paths in tournaments. We prove that there is a one to one correspondence between the set of minimal feedback sets and the set of Hamilton paths. In the comparison model, all the tradeoffs for sorting between the ... |
|
| Square Meshes are not Always Optimal |
09 AUG 88 |
25 pages |
| Authors:
Amotz Bar-Noy; David Peleg; STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
|
| In this paper we consider mesh connected computers with multiple buses, providing broadcast facilities along rows and columns. A tight bound of theta(n(1/2)) is established for the number of rounds required for semigroup computations on n values distributed on a 2-dimensional rectangular mesh of size n with a bus on every row and column. The upper bound is obtained for a skewed rectangular mesh of dimensions n(3/8) x n(5/8). This ... |
|
| Processor Renaming in Asynchronous Environments |
SEP 86 |
|
| Authors:
Amotz Bar-Noy; David Peleg; STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
|
 | Fischer, Lynch and Paterson FLP proved that in a completely asynchronous system weak agreement cannot be achieved even in the presence of a single benign fault. Following the direction proposed in ABDK, we demonstrate the interesting fact that some weaker forms of processor cooperation are still achievable in such a situation, and in fact, even in the presence of up to t < n/2 such faulty processors. In particular, we ... |
|
Reports by Author
