An Omega(n log2n / log log n) lower bound for Algorithm W in a synchronous fail-stop (no restart) PRAM
[.ps]
[.pdf]
Abstract
Buss et al. proposed an algorithm for the Write-All problem for a general fail-stop PRAM. In the same paper it is conjectured that the algorithm performs work Omega(n log n log log n) for the fail-stop with no restart model. In this work it is shown that, using the adversary proposed by Kanellakis and Shvartsman, the amount of work performed by such algorithm is Omega(n log^2 n/log log n).
Bibtex Entry
