Talk:Linearizability

Atomicity and linearizability

The page currently states:

• In concurrent programming, atomicity is equivalent to linearizability, which has the additional property that none of its effects are visible until after it completes. That is, that there are no intermediate states visible to other threads. (In database systems, this property is classified separately as "isolation".)

• In operating systems, an "atomic" operation is an operation that is not (or cannot be) interrupted once it has begun. For example, basic machine instructions like add or store are usually guaranteed by the hardware to be atomic, and some platforms provide a pair of operations (load-link/store-conditional) that only have an effect if they occur atomically. This property can be used to implement locks, a vital mechanism for multithreaded programming

However, the latter is merely a special case of the former, and hard to define rigorously. "Atomicity = linearizability" makes much more sense even in operating systems. I suggest merging the two, and moving away from "atomicity includes isolation" to "atomicity means the operation appears to take effect instantaneously at some point", in the interest of simplification and clarification. Chris Purcell 09:30, 7 February 2006 (UTC)

Revisions

I have reverted the edit of Ewlyahoocom as it conflates the database ideas of isolation and atomicity, to the point where the article is now factually inaccurate. Perhaps we could discuss and refine the changes here before pushing them live again? --Chris Purcell 23:44, 10 April 2006 (UTC)

Relocated from User talk:Ewlyahoocom

I've reverted your edit of atomicity because I don't feel it accurately describes the predominant meaning of the term in databases: namely, it appears to conflate atomicity with isolation. Apologies for the brusqueness. Most willing to discuss more constructive forward progress though! --Chris Purcell 23:50, 10 April 2006 (UTC)

That explains my confusion! OK, I've broken out the computer science bits to Atomic operation, and modified Atomicity (computer science) to make it more clear that that page is about databases -- hopefully this will allow it to develop alopng the lines of the other ACID pages. Maybe those pages should even move to "(data management)" instead of "(computer science)"? Ewlyahoocom 05:51, 11 April 2006 (UTC)

Ok, now I think you're conflating atomicity in the database sense with atomicity in the parallel algorithm sense. Atomicity in the parallel algorithm sense really doesn't have anything to do with "an operation either executes completely or not at all": if that were true, it would be part of the serial definition of the operation, not its atomicity. Atomicity in the parallel algorithm sense means linearizability, nothing more, nothing less.

Perhaps we should re-merge the various atomicity disambiguation pages, and use atomic transaction and linearizability as the disambiguation pages for databases and parallel algorithms, respectively? --Chris Purcell 07:56, 11 April 2006 (UTC)

Yeah, I can see your point. When I read linearizability I was tempted to add some merge tags, but it really seemed to be addressing the issue from a concurrency angle, maybe I should read it again. (BTW, thanks for removing your "confusing" paragraph about ACID from that article, but maybe a paragraph like that should be added to Atomicity.) Now, compare that page to Atomic transaction where the merge tags are clearly appropriate.

But this still leaves open the question about atomic operations at the lowest levels (which may even exist in a single processor/single process environment): e.g. reading/writing a 64-bit value which is really two 32-bit reads/writes, with the added condition that a failed write will never leave the value in a intermediate or undefined state, and any read will either get the old value or the new value and never an intermediate or undefined value? (The "Invariant" section of at the bottom of the old Atomicity page.) Where would you suggest that information should go?

Finally, is it possible that the rest of computer science isn't "conflating atomicity", but that database science is making a pedantic distinction where none need exist? Ewlyahoocom 08:40, 11 April 2006 (UTC)

I've come to think that isolation (database) equals atomicity (parallel algorithms). Atomicity (database) is a property of the *sequential* specification of a transaction, namely that it will either succeed or fail; isolation (database) specifies how things hold up under *concurrency*. In contrast, atomicity (parallel algorithms) means "linearisable isolation" (if you will), and succeed-or-fail really has no appropriate place to go, since of all the atomic primitives, only load-linked/store-conditional can fail.

Thus, database science is not making a pedantic distinction; it is specifying a sequential property of "a transaction", and using the catch-all term "atomic" to cover it. The fact that other parts of computer science use the same word to refer solely to isolation properties is neither here nor there.

I don't feel that atomic transaction should be merged with atomic operation, since they are completely different things!

I'll have a crack at rewriting things the way I'd like to see them go, and then we can meet back here. --Chris Purcell 12:40, 11 April 2006 (UTC)

Yes! Of course! Atomic in computer science is most akin to isolation in database science! At its simplest level it just implies exclusive locking, without indicating how errors are handled: for example, I would not be the least bit surprised to read in a manual that "in the event of an exception, the contents of the register are undefined". The next level up would include the ability to undo changes on an exception.

I notice the proposed merge of Atomic operation in to Linearizability. If it does the name should really be changed. Has anyone ever referred to an atomic Compare-and-swap instruction as "linearizable"?

When you write "I don't feel that atomic transaction should be merged with atomic operation..." do you mean that you think the low level details on that page (e.g. open, semop, flock, Test-and-set machine instructions) are better suited for a page about databases than a page about programming and CPUs? I'm not sure I agree -- but I look forward to seeing what you come up with. Ewlyahoocom 16:35, 11 April 2006 (UTC)

Glad you like :)

Yes, people refer to an atomic Compare-and-swap instruction as linearizable, all through concurrent algorithm literature. The original definition ignores the issue of memory barriers, but that can be worked back in by correctly modifying the basic invocation-response setup of Herlihy et al. It's definitely the right term.

I think the "low-level details" on the atomic transaction page are bogus and should be removed. They're a hold-over from the previous revision. However, I didn't want to strip them right out without consulting, as they feel at least vaguely related to the title of the page, unlike the stuff I cut. They're more appropriate on the linearizability page, but on the whole feel rather flung together and unedifying (to me). What do you think? Delete them? Move and rewrite? --Chris Purcell 23:03, 11 April 2006 (UTC)

Continued discussion

Wait, you mean you're done? When I said "I look forward to seeing what you come up with" I was under the impression that you were still working on these pages. Let me see if I understand this:

• Atomicity is a disambiguation page?
  • If so then it should follow the style laid out at Manual of Style, and the links to it should be resolved to their proper pages;
  • If not then it should be written like an article.
• Atomic transaction is about databases. There's a lede, and the it launches into examples. Does it ever really define the term? Again, I think the low-level details don't belong on this page. Unless you're including the OS calls and the machine level instructions in some new definition of "database transaction".
• Linearizability is a consistency model? I'm not quite sure what that means, nor do I think a lot of other people will too. Is there a reason you're avoiding the use of the more widely used and accepted term atomic? Remember, this is supposed to a fairly accessible encyclopedia articles, not your PhD thesis.

Finally, I would like to remind you of the old adage "If you can't explain it simply, you don't understand it well enough". Are you certain that you understand it well enough? Ewlyahoocom 09:58, 12 April 2006 (UTC)

No, I wasn't done. You'll have to help me out, though, hence why I stopped.

• Yes, Atomicity is a disambiguation page.
  • You'll have to help me make it follow the Manual of Style, because I'm not experienced enough to do that. I take it you were going to make those changes anyway, to the almost identical Atomicity (disambiguation)?
  • I haven't fixed the backlinks because it was a preemptive change and I didn't want to mess up dozens of pages only to put them back again a day later. Your response doesn't fill me with confidence that you agree with the decision, either :)
• Please explain how "An atomic transaction is a database transaction which either completely occurs (commits), or has no effects (rolled back)" doesn't define the term. Is it just not prominent enough as the second sentence on the page? I know most articles have the definition in the very first sentence.
• Help me here, too, then. I understand the concept fine. The problem with "If you can't explain it simply, you don't understand it well enough" is that it assumes one has someone's (constructive) feedback during the initial refinement of the explanation. What about "a sequence of operations on a shared object is linearizable (or atomic) if each operation appears to happen instantaneously at some point during its execution" is unhelpful? Or is it the fact that the definition then goes on to say "A shared object is linearizable if every possible sequence of its operations can be linearized"? Is that too close to the original (highly rigorous) definition? Should it be simplified to a single sentence, and the stuff about linearization points moved?

If you think we should move Atomicity to Atomicity (disambiguation), and move and redirect Linearizability to Atomicity, that could work. --Chris Purcell 10:33, 12 April 2006 (UTC)

I've rewritten the Linearizability page. What do you think? --Chris Purcell 11:45, 12 April 2006 (UTC)

Here's what I had in mind:

• Atomicity should be specific to databases, to be expanded from a purely database point-of-view, similar to Isolation (computer science) (I also think these and the other 2 should be renamed to "(data management)" instead of "(computer science)");
• Atomicity (disambiguation) can be the disambiguation page, it'll be probably be pretty minimal because of all the entries only S-expression mentions the term (in passing, without defining it);
• and some other page, e.g. Atomic operation, can focus on the computer science angle (outside of databases I just don't believe the word "Atomicity" gets a lot of use).

Perhaps you could also lay out your plan for these pages? (As an aside, I'm not a fan of the names of these pages being noun-ified adjectives; e.g. Automatic transmission renamed to Automaticness (vehicles), but if that's how they're commonly referred to in the field then it's hard to argue.) I haven't yet read the revised Linearizability. Ewlyahoocom 10:27, 13 April 2006 (UTC)

Atomicity as a concept gets used a lot outside of databases. I don't think the "ity" ending gets used much, though. Was that your point?

My plan for the page names was as I've laid them out: atomicity a short disambiguation page, linearizability used for the isolation property. I like Atomic transaction as the database page title, but there's no denying that "atomicity" is the favoured term. That said, it starts getting clunky to have to use "atomicity (databases)" or "atomicity (data management)": you might as well say "atomicity (transactions)", and then you're basically back to Atomic transaction. Atomicity would be best.

Ultimately, I'm not too fussed how we arrange the pages, as long as the contents are correct. My blessings on whatever alternative you prefer. --Chris Purcell 14:17, 13 April 2006 (UTC)

I don't understand why we're having so much trouble communicating. Know what? Do whatever you want with these pages -- I just don't care anymore. Ewlyahoocom 06:48, 14 April 2006 (UTC)

Ah, the joys of attempting to have a constructive conversation on the Internet. Thanks for trying as long as you did. --Chris Purcell 10:31, 14 April 2006 (UTC)

Too abstract

--24.251.211.127 01:34, 28 July 2006 (UTC)This description is way too abstract. It would be appropriate to retain the abstracted details, but there really should be some real-world examples both here and in atomicity, not this A vs. B stuff. I've been a software developer for a decade but I don't necessarily find this stuff to be self-explanatory or useful without something to associate the abstract concepts with.

• I agree.--al95521 09:34, 28 January 2007 (UTC)

Got any suggestions? Do we simply want to enhance "A" and "B" with more evocative examples? e.g. "The main thread (A) attempts to lock the progress data structure so it can update the GUI. Meanwhile, a worker thread (B) also attempts to lock the structure to note its latest progress." --Chris Purcell 09:23, 29 January 2007 (UTC)

I've rewritten the page since these comments were made. Hopefully I have addressed the concerns. --Chris Purcell (talk) 16:07, 30 October 2008 (UTC)

linearizability and atomic operation

Many of the pages that link to this "linearizability" article[1] use this pattern: [[Linearizability|atomic operations]].

I find this odd, since there is an atomic operation article, and it doesn't even mention "linearizability" (except as an uncommented bullet point in the final "See also" section).

If "linearizable" and "atomic operation" really mean the same thing (as implied by the current first sentence of the linearizability article, and also implied by the atomicity disambiguation page), shouldn't we merge the two articles?

If they mean different things, shouldn't the "atomic operation" article say a few words about the difference, and shouldn't other articles that are really talking about linearizability use a [[linearizability]] link and other articles that are really talking about atomic operations use a [[atomic operations]] link? --68.0.124.33 (talk) 06:31, 3 December 2008 (UTC)

I see there is a long discussion at Talk:Read-copy-update of whether or not "atomic = linearizable". Could we summarize the conclusions in this linearizability article and the atomic operation article? --68.0.124.33 (talk) 07:14, 3 December 2008 (UTC)

There are no references in the discussion or in the Read-copy-update article. This discussion appears to be original research and can't be included here. --Kvng (talk) 16:52, 17 September 2010 (UTC)

At the time I made those links, Atomic operation and Linearizibility were marked for merging. The end result of reams of discussion was that they were indeed the same thing, at which point an admin came along and removed the merge request on the grounds of "no consensus". (Apparently he didn't bother to read the discussion.) After the second time this happened, I gave up. Please do reopen and complete the merge request. --Chris Purcell (talk) 12:08, 21 December 2008 (UTC)

Apparently complex merge issues aside, I'd like to know why this article is called Linearizability and not Atomicity (programming) or somesuch. Comments at the top of this section indicate that Atomicity is the term most often used when linking to this article. I was personally confused when I arrived here from one of these links. Atomicity shows up on Goole 20x more than Linearizability. --Kvng (talk) 16:52, 17 September 2010 (UTC)

(1) The numbers I see are ~240K hits for an "atomicity" search, ~32.7K for "linearizability" (about 7x). However, the overwhelming majority of (at least the first few pages of) the atomicity hits have nothing to do with the subject at hand, while every linearizability one does, so that comparison is meaningless. (2) "Linearizability" is the accepted term in technical literature. --Chris Purcell (talk) 15:49, 18 September 2010 (UTC)

Don't know what we're doing differently but I get 747K Google hits for atomicity. I don't know how to fairly assess what all of these hits refer to so instead let me pile on a bit more evidence for good measure. In a Wikipedia search, linearizability shows up 9 times and atomicity shows up 16,134! I don't know if you have a citation to back up your technical literature claim. I've done a couple searches with Google scholar and atomicity (78,200 hits) soundly beats linearizability (11,600 hits) there too. A patent search yields 30 linearizability hits and 408 for atomicity. --Kvng (talk) 18:53, 18 September 2010 (UTC)

Atomicity (database systems) is one of the pivotal parts of ACID in databases. Of course there are lots of hits. As for "linearizability", there's the original usage citation on the page, plus the 11 thousand others you mentioned, since to my knowledge the word isn't used for any other purpose. I'm not fundamentally opposed to renaming the page, but in my experience it's "atomic" and "linearizability" in concurrency, not "atomicity", and "number of hits" is not valid evidence to the contrary (for the reasons specified). --Chris Purcell (talk) 19:59, 18 September 2010 (UTC)

I would like to submit a WP:RM application and see how that goes. But first I'd like to try and select a new name candidate. Here are the current redirects to this page: Atomic (computer science), Atomic action, Atomic actions, Atomic operation, Atomic operations, Atomic primitive, Atomicity (programming), Indivisibility (programming), Indivisible operation, Strict consistency, Uninterruptibility (programming). Do any of these strike anyone's fancy? Atomic operation is the most popular link target but that's probably because up until July, it was a stand-alone article. I personally prefer Atomicity (programming) or Atomicity (computer science). --Kvng (talk) 21:55, 18 September 2010 (UTC)

Once again, "linearizable" is the accepted term in academic literature, hence I fail to see the need for a page rename. However, "atomic" would be preferable to "atomicity", since I believe the latter is mainly used with reference to ACID (i.e. all-or-nothing operations), not concurrency, and is more easily confused as a result. --Chris Purcell (talk) 16:28, 20 September 2010 (UTC)

I don't mean to try your patience. I understand your assertion for "linearizable" but I haven't seen any backing for it. I admit I'm not coming at this from an academic perspective so you could well be right (though I'd still like to see some evidence). What I'm trying to do is improve terminology consistency within Wikipedia. Arriving at an article called "linearizable" after clicking on an "atomicity" link is a problem in my opinion. Do you understand my assertion? --Kvng (talk) 17:25, 20 September 2010 (UTC)

Obviously your opinion is valid. If you want evidence about "linearisability", read some of the academic articles you found with a simple search, or the Herlihy citation on the page. Other than that, "atomic operation" would be an acceptable name for the page. --Chris Purcell (talk) 07:47, 21 September 2010 (UTC)

FWIW. Technically, there is a subtle difference between linearizable and atomic, see [2]. The difference is that linearizability requires atomicity plus preserving order of non-concurrent operations. Therefore, probably current article should be split into two separate articles along this line. For me, it does not look as two different terms for the same entity, as in academic literature both atomic operations and linearization are routinely used in similar, though not identical sense (see for example fundamental works in compare-and-swap field [3] and [4], often wording goes along the lines of linearizability which implies operations are atomic). Ipsign (talk) 06:15, 4 December 2010 (UTC)

Comment: I came here from the link at Wikipedia talk:WikiProject Computing. What's the specific proposal on the table? --Pnm (talk) 01:07, 7 December 2010 (UTC)

The proposal prior to Ipsign's contribution was to rename the article Atomic operation --Kvng (talk) 03:13, 7 December 2010 (UTC)

I would propose to split the article in two: Linearizability and Atomic operation, and explain the difference between two in Linearizability (which relies on Atomic operation). Ipsign (talk) 15:40, 7 December 2010 (UTC)

I support the split. The existing lead seems to more closely summarize atomic operation, so for the mechanics, I suggest first moving this article to become the new Atomic operation, then split back to Linearizability "under" the redirect. I named the subject headings explicitly to prepare for the move. --Pnm (talk) 23:48, 7 December 2010 (UTC)

Rename to Atomic?

The term "atomic" more clearly states the conceptually-easiest form of this concept. Perhaps we should rename the page to Atomic operation? --Yoderj (talk) 17:22, 6 March 2015 (UTC)

In databases, "atomic" means something different (all-or-nothing). I vote to keep as is. --Chris Purcell (talk) 12:00, 13 March 2015 (UTC)

Are there any articles about the "all-or-nothing" definition, besides this one? This article includes in the opening paragraph: "Additionally, atomic operations commonly have a succeed-or-fail definition." The "appears visible from other threads" is interesting, but much more subtle. I would like to see an article that looks at the "all-or-nothing" concept of "atomic," both in databases and in concurrent programming --Yoderj (talk) 15:07, 25 May 2015 (UTC)

Atomicity race

please comment on phrase "atomicity race" —Preceding unsigned comment added by Skysong263 (talk • contribs) 18:45, 21 December 2009 (UTC)

Very low quality

It mixes all the concepts and contradicts itself. Atomicity means distinct things at different levels of abstraction starting by mentioning databases in reference to it is extremely objectionable... --81.84.152.156 (talk) 21:16, 29 June 2010 (UTC)

Could you elaborate on what distinct things atomicity means at different levels of abstraction? Also, what contradictions are you referring to? --Chris Purcell (talk) 17:58, 9 July 2010 (UTC)

I too think the article is useless (to put it harshly). I expected to find the definition of linearizability from the summary, but it just mentions that some operation may be one of four things. Then, the article continues forward more or less without mentioning linarizability at all until the section 'History of linearizability', where some kind of an explanation is provided. I suggest that people how know more about the subject than I do modify the article so that the definition of the topic is at the top, or change the topic (and most of the content) of the article completely.

APR

The page says, "the Apache Portable Runtime library provides a selection of atomic operation function macros for use within MPL [Mozilla Public License?] licensed software." Is this really right? Apache Foundation software is (almost?) always under Apache License. And derivative works are not required to use that license. Superm401 - Talk 04:28, 10 January 2009 (UTC)

The example

The example details a situation, but it doesn't explain what the situation has to do with atomic operations. --Snaxe/fow (talk) 02:10, 10 April 2009 (UTC).

Hopefully that's a bit clearer now --Chris Purcell (talk) 11:12, 10 July 2010 (UTC)

Merge with Atomic action

I recommend redirecting the atomic action stub to this page. Atomic actions fall under the linearizability umbrella; the stub mainly describes some possible implementation details that may or may not enhance this page. --Chris Purcell (talk) 09:35, 5 August 2010 (UTC)

Merge done. --Chris Purcell (talk) 16:28, 28 August 2010 (UTC)

But now here is the problem that the link atomic action in the "See also" part is redirected to the article itself. 134.91.76.129 (talk) 12:59, 2 December 2010 (UTC)

Removed the see also. --Pnm (talk) 23:31, 3 December 2010 (UTC)

Strict Consistency

What is the section on strict consistency doing here? Could someone expand on the relation of linearizability to strict consistency? Or maybe we can remove this useless section --Jetru (talk) 12:40, 8 April 2011 (UTC)

This appears to be largely redundant and not even correct (e.g., "most stringent"). I suggest deleting this. Perhaps the author is confused with respect to "strict serializability," which is indeed one of the strictest models (linearizability plus serializability), but is still not the "most stringent" (namely because "most stringent" is not well-defined; it's possible to order the strength of models, but there's no one strongest model--e.g., "never return 0", "never return 1", etc.).Peter Bailis (talk) 00:12, 19 June 2013 (UTC)

"Primitive atomic instructions" as relates to Burroughs mainframes

The section "Primitive atomic instructions" has a statement in it that reads: "Atomic swap as used in some Burroughs mainframes, also called XCHG."

The XCHG operator is emitted by the compiler to implement its needs in stack manipulation, but is not accessible to the user directly. [It was, in ESPOL, but ESPOL is no longer used.] It causes the two top-of-stack values to be exchanged; that is, it only affects the stack.

The user-accessible instruction that is used for implementing locks is RDLK (ReadLock). It exchanges a top-of-stack value with an address in memory, in one uininterruptible swell foop.

EXCH & RDLK are both atomic, in that they are not interruptible. Other "atomic" operators are RSUP & RSDN, which manipulate the top 3 stack cells. But only RDLK is accessible to programmers (in Algol & NEWP) & thus used with implementing locks.

Thus, I believe the line should read, "Atomic swap as used in some Burroughs mainframes, also called RDLK." Or, it should stated another way, but involve the use of RDLK, not EXCH. — Preceding unsigned comment added by 70.181.124.207 (talk) 06:54, 28 February 2013 (UTC)

 Done. I agree that that line incorrectly implies that XCHG was used by programmers of Burroughs mainframes. --DavidCary (talk) 18:03, 4 June 2014 (UTC)

Merger proposal

The following discussion is closed. Please do not modify it. Subsequent comments should be made in a new section. A summary of the conclusions reached follows.

The result of this discussion was to delete Immediate consistency and redirect to Linearizability Peter Bailis (talk) 22:27, 18 July 2013 (UTC)

---

I propose that Immediate consistency be merged into Linearizability (or, alternatively, Immediate consistency should be deleted). These are the same models, and the former is non-standard terminology for the latter. Pbailis (talk) 23:49, 18 June 2013 (UTC)

I second deletion. --Chris Purcell (talk) 23:19, 17 July 2013 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

Separate atomicity from linearizability

Linearizability should be a separate article from atomicity. The current definition of atomicity is simply wrong. I won't comment on the definition of linearizability because I can't follow it, but it should probably be defined in terms of total orders.

Here's what I propose for atomicity:

In computer science, an operation (say, X) is atomic with respect to some other operation (say, Y), if it appears to Y that X either occurs all at once, or not at all. Atomicity allows the correctness of Y to depend on a property being true, even though the property may not be true during the execution of X, because Y cannot observe the period during which X is executing. If X is atomic with respect to Y, then it is sufficient (for the correctness of Y) for the property to be true before and after X executes.

Note that an operation may be atomic with respect to some operations, and not atomic with respect to others. Note also that atomicity is not necessarily symmetric: X may be atomic with respect to Y, without Y being atomic with respect to X.

Atomicity is similar to mutual exclusion--mutual exclusion prevents the occurrences of X and Y from overlapping--but the two concepts are not identical. Atomicity may be implemented by mutual exclusion, or by other methods such as optimistic concurrency control. Mutual exclusion is often implemented by using atomicity, but does not require it.

References

Tim Leonard (talk) 19:05, 29 June 2015 (UTC)

I concur. I have no idea why atomicity redirects to linearizability, and I think it deserves it's own page 98.116.215.118 (talk) 01:43, 27 February 2019 (UTC)

Proposal to rewrite _Definition of linearizability_ section

Mainly the definition stated on the page is invalid.

In the second, it mixes formal and informal styles very badly. Not only in the intro part, but in the definition itself.

> If an operation op1 completes (gets a response) before op2 begins (invokes), then op1 precedes op2 in σ.

This is not part of the definition. And its states mainly nothing if understood right. It's formulated very unclearly.

> if a response preceded an invocation in the original history, it must still precede it in the sequential reordering.

It may be thought that its states about the order in σ, but it's still not very clear. Both conditions, the original one, and reformulated one hardly reflects what it states about. What is sufficient and what is necessary. Also it states its from [2], but anyway the def in [2] is different.

> For every completed operation in σ, the operation returns the same result in the execution as the operation would return if every operation was completed one by one in order σ.

Its partly formal, and mainly rewritten in that form for some unknown purpose. The original def is much clearer.

There are also examples there which maybe separated into independent section.

I offer:

1. Take exact definition from one of the works of Herlihy, Maurice P.
2. Take both informal and formal definitions from that work - they are good and clear.
3. Add examples from Linearizability: A Correctness Condition for Concurrent Objects

John.koepi (talk) 21:21, 1 July 2017 (UTC)

Improper mixing of database terminology with distributed computing

DB and DC have some of the same words that mean vastly different things. "Atomic" is a simple example. Mixing serializability with linearizability is problematic because the former is a DB term and the latter from DC. The operating models aren't compatible. DB talks about transactions made up of multiple operations, where DC is focused on a single operation and what happens in the presence of other operations. http://www.bailis.org/blog/linearizability-versus-serializability/ has a really great breakdown of the problem.

Bcr33d (talk) 15:34, 23 September 2019 (UTC)

A problem with the "Counter" example?

I don't understand why the "Atomic" implementation of the Counter is linearizable. I understand that the individual read/write operations are linearizable (because each register is only written by a single process). The "increment" operation has a linearization point at step 3 (write to Ri), but it doesn't seem like the Read operation needs to have a linearization point. Specifically, consider the following execution with 3 processes, starting at time 0 (with all registers initialized to 0):

- Process 1 increments at times 1 and 2 (i.e., these are the linearization points)

- Process 2 increments at time 3

- Process 3 calls increment at time 1: it reads 1 from R1 a time 1.5 and reads 1 from R2 at time 3.5. Thus, it returns a value of 2.

It doesn't seem this execution can be linearized because there is no time at which R1 has value 1 and R2 has value 1. Such a linearization point would have to be after 1 and before 2 (because process 3 read 1 from R1), but after time 3 (because process 3 read 1 from R2).

Am I missing something here?

Will.rosenbaum (talk) 16:55, 23 March 2021 (UTC)