HackerPapers

arXiv:1103.4690cs.DC

Linearizable Implementations Do Not Suffice for Randomized Distributed Computation

Wojciech Golab, Lisa Higham, Philipp Woelfel

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

Linearizability is the gold standard among algorithm designers for deducing the correctness of a distributed algorithm using implemented shared objects from the correctness of the corresponding algorithm using atomic versions of the same objects. We show that linearizability does not suffice for this purpose when processes can exploit randomization, and we discuss the existence of alternative correctness conditions.

arXiv comments
Journal reference
DOI
Subjects
cs.DCDistributed, Parallel, and Cluster Computing

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Jul 2016 to Jul 2016.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Jepsen: VoltDB 6.3 1 comment

    • Most people require that linearizable execution must happen as-if it matches a global clock. Simply requiring that the effects of a transaction happen within the start/end time of the partition executing the transaction does not guarantee this. I'm not sure what you mean by…

      aphyrView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.