Jump to content

Talk:Global serializability

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Mjec (talk | contribs) at 04:26, 14 October 2023 (Change from B-class to C-class, and explain). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

WikiProject iconComputer science C‑class High‑importance
WikiProject iconThis article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles
CThis article has been rated as C-class on Wikipedia's content assessment scale.
HighThis article has been rated as High-importance on the project's importance scale.
Things you can help WikiProject Computer science with:

Are the experts experts?

(See also the article The History of Commitment Ordering that has been written following this comment)

Strangely, since its introduction publicly in formal publications, Commitment ordering has been misunderstood (including in papers mentioning strong recoverability), misrepresented, and totally ignored in many papers on database global concurrency control. The single existing description of CO in a textbook, by Weikum and Vossen, 2001, is indeed poor (as somebody already mentioned in the article Serializability’s discussion part) and a misunderstanding of the CO solution. A three years review process by IPL of a CO paper (see dates in the reference), a journal that typically accepts and publishes papers in few weeks, means a problematic review process with reviewers’ opposition very likely, but with acceptance at the end (persistent editor!). Acceptance to top journal and conferences means that at least some experts understood CO. CO is the most spectacular result in concurrency control theory since 2PL and multi-version CC, to my opinion, and apparently the only existing effective general solution to the global serializability problem. All the above is not a compliment to the researchers involved, whatever the reasons are.

Some more information connected to CO that I have found:

Closely related to CO is Dynamic atomicity that has been introduced at the MIT in the mid eighties by William E. Weihl (using a unique OO formalism), but without a general algorithm beyond mentioning known algorithms with locking. Under a specific transaction model translation it can be interpreted as CO (no commit order is mentioned there explicitly). In 1993 it was reformulated as CO (using commit) without reference to the CO papers. Atomic commitment and voting, which eliminate global cycles in the precedence graph, and are the basis for CO’s distribution, are not mentioned there.

In 1990 Analogous execution and serialization order, which unnecessarily has serializability as a premise (it implies serializability also without the premise), but otherwise similar to CO, was introduced in technical reports by Marek Rusinkievicz et al without a general algorithm. Its definition was enhanced in 1991 with a new name: Strong recoverability (wrong name), which is identical to CO. A paper about SS2PL (Rigorousness), already accepted for publication (“To appear in TSE, September 1991” is displayed at the top) that mentions analogous execution but does not mention strong recoverability, has been circulated in 1991. The definition of strong recoverability appears only in the September 1991 published version of the paper, and is used to assist a global serializability proof of a SS2PL based federated database. No related general algorithm is mentioned. A 1992 paper on strong recoverability cites a CO paper, but again, does not give any general properly defined CO algorithm. Atomic commitment and voting are not mentioned there, and neither I saw them mentioned in later papers that mention strong recoverability, sometimes together with CO. All papers that mention both state that they are "the same," which is true for the definitions, but not for the solutions: Only the CO papers describe valid CO algorithms and related effective system solutions.

In the mid nineties Transactional processes have been introduced, citing a CO paper. In later papers on transactional processes CO is not referenced, and distributed CO based algorithms are given (CO is assumed without mentioning the name CO). These algorithms are unlikely to be correct since they do not use the cycle elimination voting mechanism in atomic commitment, or any such alternative mechanism. 71.250.4.220 (talk) 17:04, 18 May 2008 (UTC)[reply]

  • I find this article essentially incomprehensible and unfortunately, your statement does little to clarify it. I would welcome some effort to make this entire discussion and the related pages about commitment ordering more accessible to a wider audience. If it's so spectacular, surely a more convincing case can be made. - JCLately (talk) 18:31, 18 May 2008 (UTC)[reply]
  • Some of the facts brought above, with proper references, can be a basis to an article about the evolution of CO.
Some more history:
In 89 Weihl also showed that Dynamic atomicity is a maximal property that ensures global serializability when operations are scheduled dynamically during transaction's life. This is similar to CO being a necessary condition to guarantee global serializability for autonomous database systems.
Though the papers about Strong recoverability (e.g., Breitbart Y. et al (1991): On Rigorous Transaction Scheduling, TSE, September 1991, 17(9) pp. 954-960) do not provide general algorithms, they state the importance of the property to achieve global serializability, and the fact that it is achieved when the property is present, like in SS2PL. Indeed they fail to provide a mechanism to achieve the property (the essential voting and atomic commitment are not mentioned). The description there "The class of transaction scheduling mechanisms in which the transaction serialization order can be determined by controlling their commitment order, is defined" is opposite to the CO solution: The serialization order, which is determined by data-access scheduling (the common way), determines the commit order.
Making Snapshot Isolation Serializable by Fekete et al, ACM TODS, June 2005, uses a theory developed for MVCO (Yoav Raz (1993): Commitment Ordering Based Distributed Concurrency Control for Bridging Single and Multi Version Resources, Proceedings of the Third IEEE International Workshop on Research Issues on Data Engineering: Interoperability in Multidatabase Systems (RIDE-IMS), Vienna, Austria, pp. 189-198, April 1993) without noticing it. Only in later publications about Snapshot isolation A. Fekete references this CO publication. -- Comps (talk) 19:40, 12 September 2009 (UTC)[reply]
To JCLately: Being this article's author I answer you since you made some comments about the article itself, and not just about the text above.
--- "your statement does little to clarify it" - I do not think the writer above tries to clarify the article, but I leave it to him/her to answer you.
To be honest, my comments were as much directed at you, but I didn't want to put you on the spot. - JCLately (talk) 17:44, 19 May 2008 (UTC)[reply]
--- "I find this article essentially incomprehensible" - I'm sorry about this, but since this is a general claim, I do not know how and where to start help. Please be more specific. At least show to me the first sentence in the article that you think is not understood, and I'll try to elaborate or change if needed. A list of places will help even more. I would like to note that this article, like most in any specific category, assume some knowledge within the category.
Sorry if I put that too strongly or perhaps chose the wrong word. The introduction has a quality of wordiness and circularity without clearly expressing the basic concept. Each of the first two paragraphs concludes with a strong statement that doesn't clearly follow, or which is not strongly supported. - JCLately (talk) 17:54, 19 May 2008 (UTC)[reply]
Which article? Commitment ordering has only one paragraph in the intro. The last statement is elaborated in a whole section. Comps (talk) 23:00, 19 May 2008 (UTC)[reply]
In the preceding remark, I was referring to this article on Global serializability. The sentence "This makes global serializability a major goal for global concurrency control in multidatabase systems." doesn't quite logically follow. Also, the portion that precedes it seems to use too many words to say too little. As for the second paragraph, the final sentence is worded too strongly, I think. Instead of saying "would lead to...", I'd substitute "may lead to...". - JCLately (talk) 04:05, 20 May 2008 (UTC)[reply]
No and No. I suggest you study concurrency control and get better understanding before commenting on the subject. Comps (talk) 14:31, 20 May 2008 (UTC)[reply]
--- "I would welcome some effort to make this entire discussion and the related pages about commitment ordering more accessible to a wider audience." - Again, knowledge in transaction processing is needed. For Serializability and Commitment ordering you need also some mathematical background (pointed to with links in the articles). "Wider audience" is quite unclear. I think that the paper gives an idea about the subject to non-experts (however general knowledge in the category is still needed), but goes deep enough also for the experts. Look for example at a randomly picked Math article: Calculus of variation. It goes deep enough also for a person who knows a great deal about Mathematics, with material and notation that a non-expert cannot understand.
Having created Category:Transaction processing and recently rewritten the introduction to e (mathematical constant), it would be fair to conclude that I have some knowledge of those subjects - more than should be required of the intended audience for these articles. The applicable guideline I have in mind is WP:LEAD, the section under "Provide an accessible overview" in particular. Taking your randomly selected example, Calculus of variations, I think it does a better job of introducing the subject than this article, because the essential concepts are sufficiently expanded to convey the gist of the idea, concrete examples are provided, and links to a well-chosen selection of additional topics have enough context to guide the reader appropriately. - JCLately (talk) 18:44, 19 May 2008 (UTC)[reply]
I do not agree. I think my intro of CO includes all necessary info for an intro. Comps (talk) 23:00, 19 May 2008 (UTC)[reply]
--- "If it's so spectacular, surely a more convincing case can be made." - "Spectacular" is the writer's above opinion. However, if "convincing case" relates to the article, I believe that the article makes a convincing case about the importance of the CO solution: It describes quite in detail why CO provides an effective solution to the global serializability problem. It also describes that quite many people for long time have tried to find an effective solution, which makes Global serializability an interesting enough article subject. How this solution works is shown in quite a detail in the article Commitment ordering.
--- Comps (talk) 14:09, 19 May 2008 (UTC)[reply]
It seems as though all roads lead to Commitment ordering, the article I find most objectionable, if that isn't putting it too strongly. It would be helpful if the CO concept were further clarified from the outset, in the article lead section. In its present form, the lead doen't exactly "invite a reading of the full article". Claims about the wonderfulness of CO may need to be toned down, unless they can be better justified in plain English. - JCLately (talk) 19:16, 19 May 2008 (UTC)[reply]
"Claims about the wonderfulness of CO" - I see no sentence in the articles saying anything about "The wonderfulness of CO." So, it should be your own deduction from the articles. Please show me any claim that you think is false, or inaccurate, and if you are right, I promise you to correct it. The article is supposed to include only correct facts. Also, I do not care about "invite a reading of the full article." The introduction plainly and shortly describes the main characteristics of CO, following mainly the original CO paper's abstract (paper in the references). Thank you, but it looks sufficiently inclusive to me as an intro. I am not in the business of luring people to read articles. I am in the business of providing information and teaching in my area of expertise, the best way I can. In this case, as I already wrote, targeting from the non-expert to the expert. The rest of the article is a quite detailed description of various aspects of CO, which requires more expertise, where you can also find the mathematical definition with no mathematical notation. If you are interested, you may read any other part of the article. If not, nobody holds you. PS You have started this discussion under the wrong section title. Comps (talk) 22:30, 19 May 2008 (UTC)[reply]
Sorry, my response was only to your last section. Only now I see that you have responded in several sections. I'll read and respond later. Comps (talk) 22:39, 19 May 2008 (UTC)[reply]
Please see above, immediately after your comments. Comps (talk) 23:00, 19 May 2008 (UTC)[reply]
I have a problem with the tenor of arguments to the effect that CO is the long-sought "solution" to the distributed concurrency control problem. I'm not convinced that this is a widely held view, and it may not even represent the original author's claim. Perhaps CO would be more correctly described as an optimization technique, and it should be noted that CO can only go so far toward making distributed transactions practical. To describe it as a "solution", or to assert that it is in some sense guaranteed to be "effective", I think may be overstating its significance. In any case, a clearer explanation would help the reader decide whether to bother investing more time on this subject.
I didn't pull the phrase "invite a reading of the full article" out of the air - it's an excerpt from the Wikipedia:Lead section style guideline, to which I call your attention again. It is not easy to write a good introduction to a complex technical subject, and I appreciate that you are highly knowledgeable and have contributed a great deal to this and related topics. Nevertheless, I encourage you to consider the possibility that there might be room for some further improvement along the lines I've suggested. - JCLately (talk) 05:24, 20 May 2008 (UTC)[reply]
Look, It is obvious from your comments that you are not an expert in the area of database concurrency control. You are welcome to find experts and consult with them on the subject, on the importance of CO, etc. While every article can be improved, I feel very comfortable with the current versions, after more than two years of refinement and presentation enhancements. I have not seen from you a single fact that contradicts anything I wrote. My articles deal with proven facts. If you have specific suggestions re text, please make them and I'll consider. Otherwise I see no point in continuing this discussion with you, since we get nowhere. Comps (talk) 14:31, 20 May 2008 (UTC)[reply]
Also it is obvious that you have not understood this "essentially incomprehensible" article (I asked for a single incomprehensible sentence and have not received...), which discusses what the problem is, and shows in great detail why CO is a good general solution to the problem, and why it is the only possible general solution for autonomous databases. Facts and only facts. Neither what I or this or that think about it, nor "Claims about the wonderfulness of CO," to use your expression. Comps (talk) 20:22, 20 May 2008 (UTC)[reply]
I have enhanced the Commitment ordering intro anyhow. Hope it helps a little Comps (talk) 18:17, 5 June 2008 (UTC)[reply]
...and of this article as well. I now see your point regarding intros, and think you are right because the better general understanding of the subject it can provide before reading the entire article. Not just matter of attractiveness. Thanks! Comps (talk) 23:23, 11 July 2008 (UTC)[reply]

Commitment ordering

The neutrality of part of this page is disputed, as part of a wider discussion. See Talk:Commitment ordering and Wikipedia talk:WikiProject Computer science#User:Comps / Commitment ordering. —Ruud 14:30, 23 December 2011 (UTC)[reply]


Copied from Talk:Serializability:

"I find this entire discussion improper. The "disputed neutrality" is not explained: What facts in this article (and related other articles listed in the main "discusion") are disputed? Not a single reason is given anywhere. I see no reason for such: only mathematically proven facts are outlined in the "disputed" text, and what kind of neutrality can be disputed about such? It is as disputing the neutrality of the Pythagorean theorem.
The "discussion" has never been really carried out in Wikipedia_ talk:WikiProject Computer science#User:Comps / Commitment ordering, except an attention request for a quite long list of related "suspected" articles (that at least some of them, if not all, have been similarly tagged). Also important text has been wrongly removed from Snapshot isolation as a result. The "discussion" went in March 2012 into archiving with nothing factual said or concluded.
The related tag (as well as similar tags in other articles) should be removed.
The archived main discussion can be found in Wikipedia_talk:WikiProject_Computer_science/Archive_10#User:Comps_.2F_Commitment_ordering
Also the "discussion" has recently ignited another similar baseless "discussion" named "The Raz infection is spreading" in Talk:Commitment ordering. I cannot avoid thinking about similarity to "The Jews infection" Nazi slur. 65.96.201.116 (talk) 16:50, 10 September 2012 (UTC)"[reply]

Removing baseless tag overdue. 209.144.63.76 (talk) 21:49, 5 December 2012 (UTC)[reply]

Proposal: Merging article to Serializability

Merging does not make any sense. Serializability and Global serializability are subjects with small overlap. A single relevant section exists in Serializability with Global serializability as a main article. This section is much smaller than this article, which includes substantial disjoint text material. I wonder if the proposal is based on either reading or understanding the texts. An unnecessary discussion. Tag should be removed. 209.144.63.76 (talk) 22:00, 5 December 2012 (UTC)[reply]

Hello fellow Wikipedians,

I have just modified one external link on Global serializability. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 03:44, 13 January 2017 (UTC)[reply]


Neutrality of commitment ordering section

I've left two tags above the section on commitment ordering: one for the writing style -- essay-like, though very tough to read at the same time -- and one for the neutrality of view -- it clearly expresses personal opinions and, as far as I can discern, was written by the author cited multiple times in it. Quotes like

"It [CO] has been misunderstood by many database researchers years after its introduction, which is evident by the quotes above from articles in 1997-1998 referencing Commitment ordering articles."

and

"The underlying Theory of Commitment ordering [sic; capitalisation not mine], part of Serializability theory [sic; once again, wrongful capitalisation], is both sound and elegant (and even "mathematically beautiful"; referring to structure and dynamics of conflicts, graph cycles, and deadlocks), with interesting implications for transactional distributed applications."

are completely out of place on Wikipedia. This seems to be an ailment not exclusive to this article, but rather present in many articles on transactional database management, where the same author pops up with the same entailed problems. The section should be trimmed significantly and be made neutral. — Preceding unsigned comment added by MewTheEditor (talk • contribs) 18:17, 4 December 2020 (UTC)[reply]

CO "in a nutshell"

Like many others I have found it difficult to get the gist of Commitment Ordering (CO). I believe the problem is that all articles that touch the subject are very dense/wordy. Today while reading this article on Global Serializability I saw the following sentence:

CO generalizes strong strict two phase locking (SS2PL)...

...which I actually understand. It says that if you understand SS2PL then CO is a more general form of that protocol, and while it may not be immediately clear what it means to generalize SS2PL at least you can now start with SS2PL as a foundation. SS2PL is really easy to understand because it explains what you need to do in just one sentence:

To comply with strong strict two-phase locking (SS2PL) the locking protocol releases both write (exclusive) and read (shared) locks applied by a transaction only after the transaction has ended, i.e., only after both completing executing (being ready) and becoming either committed or aborted.

I believe the whole CO concept could benefit from a single, implementation-focused instruction like the above, i.e. it needs a sentence that fills in the blank in the following: To comply with CO, the transaction processing protocol must ______. As of this comment, the year is 2021 which means Yoav Raz has been arguing vehemently for this thing for 30 years now. It's high time we move away from words (they are clearly not working) and start describing how to implement CO - preferably with actual running code that people can execute to see CO in action for themselves.

I work on massively distributed systems (think "databases running on thousands of nodes") and I am very much interested in what CO can offer to this field. So Yoav Raz, if you see this, please start working on a demo/simulator that can show CO in practice - it could be the final push needed to clarify a topic you are obviously very passionate about!

Change from B-class to C-class

I made the mentioned change here because this article fails to meet one or more of the B-class criteria, and therefore should be rated C-class. In particular, this article:

  1. is not suitably referenced; there are few inline citations besides direct quotes, and many long sections are entirely missing citations.
  2. is not reasonably well-written; in addition to multiple style issues, there are significant WP:NPOV violations and concerns already expressed on this talk page about comprehensibility.
  3. does not contain supporting materials; compare Two-phase locking (a similar topic) which is C-class and contains both tables and diagrams.
  4. does not present its content in an appropriately understandably way; there is extensive use of jargon and an assumption of deep familiarity with the field.

The original classification as B-class was done by User:Comps, who wrote most of the article, and has was banned more than ten years ago. I suspect the classification as "High-importance" to WP:WikiProject Computer Science may also not reflect reality, but I am not confident declaring so unilaterally.

I'm also thinking about nominating this to AfD. There was a previous nomination nearly twelve years ago that resolved keep. My preference is probably actually to stubify. Would welcome others' thoughts. mjec (t/c) 04:25, 14 October 2023 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Global_serializability&oldid=1180047089"