An O (n log 2 n / log log n) lower bound for Algorithm W in a synchronous fail-stop (no restart) PRAM
| dc.contributor.author | Lopez-Ortiz, Alejandro | |
| dc.date.accessioned | 2023-03-01T18:31:06Z | |
| dc.date.available | 2023-03-01T18:31:06Z | |
| dc.description.abstract | In [1] Buss et al. propose 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 O (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 O (n log[superscript 2] n / log log n). | |
| dc.description.copyright | Copyright @ Alejandro Lopez-Ortiz. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/15032 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | An O (n log 2 n / log log n) lower bound for Algorithm W in a synchronous fail-stop (no restart) PRAM | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1