Talk:Atomicity

From Wikipedia, the free encyclopedia

Contents 1 Revisions 1.1 Relocated from User talk:Ewlyahoocom 1.2 Continued discussion 2 22 December 2006

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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 22 December 2006

The interface between database and programming environment may reintroduce problems that a programmer might naively expect atomic transactions to do away with. For instance, if an operation fails in a transaction, it is often the programmer's responsibility to detect that failure and manually roll back the transaction before retrying. Not doing so will result in a partially-completed transaction!

This was removed by DanPope. I think this text is an important point, but I'm not going to re-add it without support. (I put it there in the first place.) Is there a good place to put it in the article? Somewhere else to put it? --Chris Purcell 12:41, 22 December 2006 (UTC)