Algorithms for the Certified Write-All Problem

Abstract

In this paper, we prove new upper bounds on the complexity of the certified write-all problem with respect to an adaptive adversary. Our strongest result is that for any $\epsilon > 0$, there exists an $O(p^{1+\epsilon})$ work algorithm for the p-processor p-memory cell write-all. We also give a randomized $O(p^2\log p)$ work algorithm for a p-processor $p^2$-memory cell write-all.