CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Commitment ordering - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-sticky-header-enabled vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"3105bfef-e1ab-42b7-a5e5-5c49873ba016","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Commitment_ordering","wgTitle":"Commitment ordering","wgCurRevisionId":1241510735,"wgRevisionId":1241510735,"wgArticleId":4379212,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Webarchive template wayback links","All articles with dead external links","Articles with dead external links from July 2019","Articles with permanently dead external links","Articles with short description","Short description matches Wikidata","Articles needing expert attention from October 2012","All articles needing expert attention","Computer science articles needing expert attention","Articles with topics of unclear notability from December 2011", "All articles with topics of unclear notability","Articles lacking in-text citations from November 2011","All articles lacking in-text citations","Wikipedia articles that are too technical from November 2011","All articles that are too technical","Wikipedia articles with style issues from November 2011","All articles with style issues","Wikipedia articles needing rewrite from April 2020","All articles needing rewrite","Articles with multiple maintenance issues","Data management","Databases","Transaction processing","Concurrency control","Distributed algorithms"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Commitment_ordering","wgRelevantArticleId":4379212,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true, "wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":100000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q5152903","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading", "ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions", "wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.17"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Commitment ordering - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Commitment_ordering"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Commitment_ordering&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Commitment_ordering"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Commitment_ordering rootpage-Commitment_ordering skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" title="Main menu" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Commitment+ordering" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Commitment+ordering" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Commitment+ordering" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Commitment+ordering" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Overview" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Overview"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Overview</span> </div> </a> <ul id="toc-Overview-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-The_commitment_ordering_solution_for_global_serializability" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#The_commitment_ordering_solution_for_global_serializability"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>The commitment ordering solution for global serializability</span> </div> </a> <button aria-controls="toc-The_commitment_ordering_solution_for_global_serializability-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle The commitment ordering solution for global serializability subsection</span> </button> <ul id="toc-The_commitment_ordering_solution_for_global_serializability-sublist" class="vector-toc-list"> <li id="toc-General_characterization_of_CO" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#General_characterization_of_CO"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>General characterization of CO</span> </div> </a> <ul id="toc-General_characterization_of_CO-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-The_distributed_CO_algorithm" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#The_distributed_CO_algorithm"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>The distributed CO algorithm</span> </div> </a> <ul id="toc-The_distributed_CO_algorithm-sublist" class="vector-toc-list"> <li id="toc-Enforcing_global_CO" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Enforcing_global_CO"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2.1</span> <span>Enforcing global CO</span> </div> </a> <ul id="toc-Enforcing_global_CO-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-The_exact_characterization_of_voting-deadlocks_by_global_cycles" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#The_exact_characterization_of_voting-deadlocks_by_global_cycles"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2.2</span> <span>The exact characterization of voting-deadlocks by global cycles</span> </div> </a> <ul id="toc-The_exact_characterization_of_voting-deadlocks_by_global_cycles-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Enforcing_CO_locally" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Enforcing_CO_locally"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Enforcing CO locally</span> </div> </a> <ul id="toc-Enforcing_CO_locally-sublist" class="vector-toc-list"> <li id="toc-A_generic_local_CO_algorithm" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#A_generic_local_CO_algorithm"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3.1</span> <span>A generic local CO algorithm</span> </div> </a> <ul id="toc-A_generic_local_CO_algorithm-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Example:_Concurrent_programming_and_Transactional_memory" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Example:_Concurrent_programming_and_Transactional_memory"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3.2</span> <span>Example: Concurrent programming and Transactional memory</span> </div> </a> <ul id="toc-Example:_Concurrent_programming_and_Transactional_memory-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Implementation_considerations:_The_Commitment_Order_Coordinator_(COCO)" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Implementation_considerations:_The_Commitment_Order_Coordinator_(COCO)"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3.3</span> <span>Implementation considerations: The Commitment Order Coordinator (COCO)</span> </div> </a> <ul id="toc-Implementation_considerations:_The_Commitment_Order_Coordinator_(COCO)-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-CO_is_a_necessary_condition_for_global_serializability_across_autonomous_database_systems." class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#CO_is_a_necessary_condition_for_global_serializability_across_autonomous_database_systems."> <div class="vector-toc-text"> <span class="vector-toc-numb">2.4</span> <span>CO is a necessary condition for global serializability across autonomous database systems.</span> </div> </a> <ul id="toc-CO_is_a_necessary_condition_for_global_serializability_across_autonomous_database_systems.-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Summary" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Summary"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.5</span> <span>Summary</span> </div> </a> <ul id="toc-Summary-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Distributed_serializability_and_CO" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Distributed_serializability_and_CO"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Distributed serializability and CO</span> </div> </a> <button aria-controls="toc-Distributed_serializability_and_CO-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Distributed serializability and CO subsection</span> </button> <ul id="toc-Distributed_serializability_and_CO-sublist" class="vector-toc-list"> <li id="toc-Distributed_CO" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Distributed_CO"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Distributed CO</span> </div> </a> <ul id="toc-Distributed_CO-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Distributed_optimistic_CO_(DOCO)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Distributed_optimistic_CO_(DOCO)"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Distributed optimistic CO (DOCO)</span> </div> </a> <ul id="toc-Distributed_optimistic_CO_(DOCO)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Examples" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Examples"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Examples</span> </div> </a> <ul id="toc-Examples-sublist" class="vector-toc-list"> <li id="toc-Distributed_SS2PL" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Distributed_SS2PL"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3.1</span> <span>Distributed SS2PL</span> </div> </a> <ul id="toc-Distributed_SS2PL-sublist" class="vector-toc-list"> <li id="toc-Comments" class="vector-toc-list-item vector-toc-level-4"> <a class="vector-toc-link" href="#Comments"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3.1.1</span> <span>Comments</span> </div> </a> <ul id="toc-Comments-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Variations" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Variations"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3.2</span> <span>Variations</span> </div> </a> <ul id="toc-Variations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Hypothetical_Multi_Single-Threaded_Core_(MuSiC)_environment" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Hypothetical_Multi_Single-Threaded_Core_(MuSiC)_environment"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3.3</span> <span>Hypothetical Multi Single-Threaded Core (MuSiC) environment</span> </div> </a> <ul id="toc-Hypothetical_Multi_Single-Threaded_Core_(MuSiC)_environment-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </li> <li id="toc-CO_variants:_special_cases_and_generalizations" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#CO_variants:_special_cases_and_generalizations"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>CO variants: special cases and generalizations</span> </div> </a> <button aria-controls="toc-CO_variants:_special_cases_and_generalizations-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle CO variants: special cases and generalizations subsection</span> </button> <ul id="toc-CO_variants:_special_cases_and_generalizations-sublist" class="vector-toc-list"> <li id="toc-Strong_strict_two_phase_locking_(SS2PL)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Strong_strict_two_phase_locking_(SS2PL)"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Strong strict two phase locking (SS2PL)</span> </div> </a> <ul id="toc-Strong_strict_two_phase_locking_(SS2PL)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Strict_CO_(SCO)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Strict_CO_(SCO)"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Strict CO (SCO)</span> </div> </a> <ul id="toc-Strict_CO_(SCO)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Optimistic_CO_(OCO)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Optimistic_CO_(OCO)"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.3</span> <span>Optimistic CO (OCO)</span> </div> </a> <ul id="toc-Optimistic_CO_(OCO)-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Extended_CO_(ECO)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Extended_CO_(ECO)"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.4</span> <span>Extended CO (ECO)</span> </div> </a> <ul id="toc-Extended_CO_(ECO)-sublist" class="vector-toc-list"> <li id="toc-General_characterization_of_ECO" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#General_characterization_of_ECO"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.4.1</span> <span>General characterization of ECO</span> </div> </a> <ul id="toc-General_characterization_of_ECO-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-The_ECO_algorithm" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#The_ECO_algorithm"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.4.2</span> <span>The ECO algorithm</span> </div> </a> <ul id="toc-The_ECO_algorithm-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Multi-version_CO_(MVCO)" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Multi-version_CO_(MVCO)"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.5</span> <span>Multi-version CO (MVCO)</span> </div> </a> <ul id="toc-Multi-version_CO_(MVCO)-sublist" class="vector-toc-list"> <li id="toc-Example:_CO_based_snapshot_isolation_(COSI)" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#Example:_CO_based_snapshot_isolation_(COSI)"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.5.1</span> <span>Example: CO based snapshot isolation (COSI)</span> </div> </a> <ul id="toc-Example:_CO_based_snapshot_isolation_(COSI)-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-CO_and_its_variants_are_transparently_interoperable_for_global_serializability" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#CO_and_its_variants_are_transparently_interoperable_for_global_serializability"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.6</span> <span>CO and its variants are transparently interoperable for global serializability</span> </div> </a> <ul id="toc-CO_and_its_variants_are_transparently_interoperable_for_global_serializability-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Footnotes" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#Footnotes"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Footnotes</span> </div> </a> <ul id="toc-Footnotes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" title="Table of Contents" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Commitment ordering</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 1 language" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-1" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">1 language</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%9F%E3%83%83%E3%83%88%E3%83%A1%E3%83%B3%E3%83%88%E9%A0%86%E5%BA%8F%E4%BB%98%E3%81%91" title="コミットメント順序付け – Japanese" lang="ja" hreflang="ja" data-title="コミットメント順序付け" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q5152903#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Commitment_ordering" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Commitment_ordering" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Commitment_ordering"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Commitment_ordering&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Commitment_ordering&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Commitment_ordering"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Commitment_ordering&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Commitment_ordering&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Commitment_ordering" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Commitment_ordering" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Commitment_ordering&oldid=1241510735" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Commitment_ordering&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Commitment_ordering&id=1241510735&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FCommitment_ordering"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FCommitment_ordering"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Commitment_ordering&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Commitment_ordering&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q5152903" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Concurrency control technique for databases</div> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><style data-mw-deduplicate="TemplateStyles:r1248332772">.mw-parser-output .multiple-issues-text{width:95%;margin:0.2em 0}.mw-parser-output .multiple-issues-text>.mw-collapsible-content{margin-top:0.3em}.mw-parser-output .compact-ambox .ambox{border:none;border-collapse:collapse;background-color:transparent;margin:0 0 0 1.6em!important;padding:0!important;width:auto;display:block}body.mediawiki .mw-parser-output .compact-ambox .ambox.mbox-small-left{font-size:100%;width:auto;margin:0}.mw-parser-output .compact-ambox .ambox .mbox-text{padding:0!important;margin:0!important}.mw-parser-output .compact-ambox .ambox .mbox-text-span{display:list-item;line-height:1.5em;list-style-type:disc}body.skin-minerva .mw-parser-output .multiple-issues-text>.mw-collapsible-toggle,.mw-parser-output .compact-ambox .ambox .mbox-image,.mw-parser-output .compact-ambox .ambox .mbox-imageright,.mw-parser-output .compact-ambox .ambox .mbox-empty-cell,.mw-parser-output .compact-ambox .hide-when-compact{display:none}</style><table class="box-Multiple_issues plainlinks metadata ambox ambox-content ambox-multiple_issues compact-ambox" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/40px-Ambox_important.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/60px-Ambox_important.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/80px-Ambox_important.svg.png 2x" data-file-width="40" data-file-height="40" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span"><div class="multiple-issues-text mw-collapsible"><b>This article has multiple issues.</b> Please help <b><a href="/wiki/Special:EditPage/Commitment_ordering" title="Special:EditPage/Commitment ordering">improve it</a></b> or discuss these issues on the <b><a href="/wiki/Talk:Commitment_ordering" title="Talk:Commitment ordering">talk page</a></b>. <small><i>(<a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove these messages</a>)</i></small> <div class="mw-collapsible-content"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Expert_needed plainlinks metadata ambox ambox-content" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/40px-Ambox_important.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/60px-Ambox_important.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/80px-Ambox_important.svg.png 2x" data-file-width="40" data-file-height="40" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>needs attention from an expert in computer science</b>. The specific problem is: <b>it is impossible to copy edit the article in its current state.</b><span class="hide-when-compact"> <a href="/wiki/Wikipedia:WikiProject_Computer_science" title="Wikipedia:WikiProject Computer science">WikiProject Computer science</a> may be able to help recruit an expert.</span> <span class="date-container"><i>(<span class="date">October 2012</span>)</i></span></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Notability plainlinks metadata ambox ambox-content ambox-Notability" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/40px-Ambox_important.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/60px-Ambox_important.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/b/b4/Ambox_important.svg/80px-Ambox_important.svg.png 2x" data-file-width="40" data-file-height="40" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">The topic of this article <strong>may not meet Wikipedia's <a href="/wiki/Wikipedia:Notability" title="Wikipedia:Notability">general notability guideline</a></strong>.<span class="hide-when-compact"> Please help to demonstrate the notability of the topic by citing <a href="/wiki/Wikipedia:Reliable_sources" title="Wikipedia:Reliable sources">reliable secondary sources</a> that are <a href="/wiki/Wikipedia:Independent_sources" title="Wikipedia:Independent sources">independent</a> of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be <a href="/wiki/Wikipedia:Merging" title="Wikipedia:Merging">merged</a>, <a href="/wiki/Wikipedia:Redirect" title="Wikipedia:Redirect">redirected</a>, or <a href="/wiki/Wikipedia:Deletion_policy" title="Wikipedia:Deletion policy">deleted</a>.<br /><small><span class="plainlinks"><i>Find sources:</i> <a rel="nofollow" class="external text" href="https://www.google.com/search?as_eq=wikipedia&q=%22Commitment+ordering%22">"Commitment ordering"</a> – <a rel="nofollow" class="external text" href="https://www.google.com/search?tbm=nws&q=%22Commitment+ordering%22+-wikipedia&tbs=ar:1">news</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?&q=%22Commitment+ordering%22&tbs=bkt:s&tbm=bks">newspapers</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.google.com/search?tbs=bks:1&q=%22Commitment+ordering%22+-wikipedia">books</a> <b>·</b> <a rel="nofollow" class="external text" href="https://scholar.google.com/scholar?q=%22Commitment+ordering%22">scholar</a> <b>·</b> <a rel="nofollow" class="external text" href="https://www.jstor.org/action/doBasicSearch?Query=%22Commitment+ordering%22&acc=on&wc=on">JSTOR</a></span></small></span> <span class="date-container"><i>(<span class="date">December 2011</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-More_footnotes_needed plainlinks metadata ambox ambox-style ambox-More_footnotes_needed" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Text_document_with_red_question_mark.svg/40px-Text_document_with_red_question_mark.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Text_document_with_red_question_mark.svg/60px-Text_document_with_red_question_mark.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Text_document_with_red_question_mark.svg/80px-Text_document_with_red_question_mark.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article includes a list of <a href="/wiki/Wikipedia:Citing_sources#General_references" title="Wikipedia:Citing sources">general references</a>, but <b>it lacks sufficient corresponding <a href="/wiki/Wikipedia:Citing_sources#Inline_citations" title="Wikipedia:Citing sources">inline citations</a></b>.<span class="hide-when-compact"> Please help to <a href="/wiki/Wikipedia:WikiProject_Reliability" title="Wikipedia:WikiProject Reliability">improve</a> this article by <a href="/wiki/Wikipedia:When_to_cite" title="Wikipedia:When to cite">introducing</a> more precise citations.</span> <span class="date-container"><i>(<span class="date">November 2011</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Technical plainlinks metadata ambox ambox-style ambox-technical" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>may be too technical for most readers to understand</b>.<span class="hide-when-compact"> Please <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Commitment_ordering&action=edit">help improve it</a> to <a href="/wiki/Wikipedia:Make_technical_articles_understandable" title="Wikipedia:Make technical articles understandable">make it understandable to non-experts</a>, without removing the technical details.</span> <span class="date-container"><i>(<span class="date">November 2011</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Essay-like plainlinks metadata ambox ambox-style ambox-essay-like" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/40px-Edit-clear.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/60px-Edit-clear.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/f/f2/Edit-clear.svg/80px-Edit-clear.svg.png 2x" data-file-width="48" data-file-height="48" /></span></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>is written like a <a href="/wiki/Wikipedia:What_Wikipedia_is_not#Wikipedia_is_not_a_publisher_of_original_thought" title="Wikipedia:What Wikipedia is not">personal reflection, personal essay, or argumentative essay</a></b> that states a Wikipedia editor's personal feelings or presents an original argument about a topic.<span class="hide-when-compact"> Please <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Commitment_ordering&action=edit">help improve it</a> by rewriting it in an <a href="/wiki/Wikipedia:Writing_better_articles#Information_style_and_tone" title="Wikipedia:Writing better articles">encyclopedic style</a>.</span> <span class="date-container"><i>(<span class="date">November 2011</span>)</i></span><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1251242444"><table class="box-Cleanup_rewrite plainlinks metadata ambox ambox-content" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Crystal_Clear_app_kedit.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Crystal_Clear_app_kedit.svg/40px-Crystal_Clear_app_kedit.svg.png" decoding="async" width="40" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Crystal_Clear_app_kedit.svg/60px-Crystal_Clear_app_kedit.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Crystal_Clear_app_kedit.svg/80px-Crystal_Clear_app_kedit.svg.png 2x" data-file-width="128" data-file-height="128" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This article <b>may need to be rewritten</b> to comply with Wikipedia's <a href="/wiki/Wikipedia:Manual_of_Style" title="Wikipedia:Manual of Style">quality standards</a>.<span class="hide-when-compact"> <a class="external text" href="https://en.wikipedia.org/w/index.php?title=Commitment_ordering&action=edit">You can help</a>. The <a href="/wiki/Talk:Commitment_ordering" title="Talk:Commitment ordering">talk page</a> may contain suggestions.</span> <span class="date-container"><i>(<span class="date">April 2020</span>)</i></span></div></td></tr></tbody></table> </div> </div><span class="hide-when-compact"><i> (<small><a href="/wiki/Help:Maintenance_template_removal" title="Help:Maintenance template removal">Learn how and when to remove this message</a></small>)</i></span></div></td></tr></tbody></table> <p><b>Commitment ordering</b> (<b>CO</b>) is a class of interoperable <i><a href="/wiki/Serializability" class="mw-redirect" title="Serializability">serializability</a></i> techniques in <a href="/wiki/Concurrency_control" title="Concurrency control">concurrency control</a> of <a href="/wiki/Database" title="Database">databases</a>, <a href="/wiki/Transaction_processing" title="Transaction processing">transaction processing</a>, and related applications. It allows <a href="/wiki/Serializability#Optimistic_versus_pessimistic_techniques" class="mw-redirect" title="Serializability">optimistic</a> (non-blocking) implementations. With the proliferation of <a href="/wiki/Multi-core_processor" title="Multi-core processor">multi-core processors</a>, CO has also been increasingly utilized in <a href="/wiki/Concurrent_computing" title="Concurrent computing">concurrent programming</a>, <a href="/wiki/Transactional_memory" title="Transactional memory">transactional memory</a>, and <a href="/wiki/Software_transactional_memory" title="Software transactional memory">software transactional memory</a> (STM) to achieve serializability <a href="/wiki/Optimistic_concurrency_control" title="Optimistic concurrency control">optimistically</a>. CO is also the name of the resulting <a href="/wiki/Database_transaction_schedule" title="Database transaction schedule">transaction schedule</a> (history) property, defined in 1988 with the name <i>dynamic atomicity</i>.<sup id="cite_ref-Fekete1988_1-0" class="reference"><a href="#cite_note-Fekete1988-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> In a CO compliant schedule, the chronological order of commitment events of transactions is compatible with the <a href="/wiki/Serializability#Testing_conflict_serializability" class="mw-redirect" title="Serializability">precedence</a> order of the respective transactions. CO is a broad special case of <i><a href="/wiki/Serializability#View_and_conflict_serializability" class="mw-redirect" title="Serializability">conflict serializability</a></i> and effective means (<a href="/wiki/Reliability_engineering" title="Reliability engineering">reliable</a>, high-performance, distributed, and <a href="/wiki/Scalability" title="Scalability">scalable</a>) to achieve <a href="/wiki/Global_serializability" title="Global serializability">global serializability</a> (modular serializability) across any collection of database systems that possibly use different concurrency control mechanisms (CO also makes each system serializability compliant, if not already). </p><p>Each not-CO-compliant database system is augmented with a CO component (the commitment order coordinator—COCO) which orders the commitment events for CO compliance, with neither data-access nor any other transaction operation interference. As such, CO provides a low overhead, general solution for global serializability (and distributed serializability), instrumental for <a href="/wiki/Global_concurrency_control" class="mw-redirect" title="Global concurrency control">global concurrency control</a> (and <a href="/wiki/Distributed_concurrency_control" title="Distributed concurrency control">distributed concurrency control</a>) of multi-database systems and other <a href="/w/index.php?title=Transactional_object&action=edit&redlink=1" class="new" title="Transactional object (page does not exist)">transactional objects</a>, possibly highly distributed (e.g., within <a href="/wiki/Cloud_computing" title="Cloud computing">cloud computing</a>, <a href="/wiki/Grid_computing" title="Grid computing">grid computing</a>, and networks of <a href="/wiki/Smartphone" title="Smartphone">smartphones</a>). An <a href="/w/index.php?title=Atomic_commitment_protocol&action=edit&redlink=1" class="new" title="Atomic commitment protocol (page does not exist)">atomic commitment protocol</a> (ACP; of any type) is a fundamental part of the solution, utilized to break global cycles in the conflict (precedence, serializability) graph. CO is the most general property (a <a href="/wiki/Necessary_condition" class="mw-redirect" title="Necessary condition">necessary condition</a>) that guarantees global serializability, if the database systems involved do not share concurrency control information beyond atomic commitment protocol (unmodified) messages and have no knowledge of whether transactions are global or local (the database systems are <i>autonomous</i>). Thus CO (with its variants) is the only general technique that does not require the typically costly distribution of local concurrency control information (e.g., local precedence relations, locks, timestamps, or tickets). It generalizes the popular <i><a href="/wiki/Two-phase_locking" title="Two-phase locking">strong strict two-phase locking</a></i> (SS2PL) property, which in conjunction with the <i><a href="/wiki/Two-phase_commit_protocol" title="Two-phase commit protocol">two-phase commit protocol</a></i> (2PC), is the <a href="/wiki/De_facto_standard" title="De facto standard">de facto standard</a> to achieve global serializability across (SS2PL based) database systems. As a result, CO compliant database systems (with any different concurrency control types) can transparently join such SS2PL based solutions for global serializability. </p><p>In addition, locking based <i>global deadlocks</i> are resolved automatically in a CO based multi-database environment, a vital side-benefit (including the special case of a completely SS2PL based environment; a previously unnoticed fact for SS2PL). </p><p>Furthermore, <b>strict commitment ordering</b> (SCO; <a href="#Raz1991c">Raz 1991c</a>), the intersection of <i><a href="/wiki/Database_transaction_schedule#Strict" title="Database transaction schedule">Strictness</a></i> and CO, provides better performance (shorter average transaction completion time and resulting in better transaction <a href="/wiki/Throughput" class="mw-redirect" title="Throughput">throughput</a>) than SS2PL whenever read-write conflicts are present (identical blocking behavior for write-read and write-write conflicts; comparable locking overhead). The advantage of SCO is especially during lock contention. Strictness allows both SS2PL and SCO to use the same effective <i>database recovery</i> mechanisms. </p><p>Two major generalizing variants of CO exist, <b>extended CO</b> (ECO; <a href="#Raz1993a">Raz 1993a</a>) and <b>multi-version CO</b> (MVCO; <a href="#Raz1993b">Raz 1993b</a>). They also provide global serializability without local concurrency control information distribution, can be combined with any relevant concurrency control, and allow optimistic (non-blocking) implementations. Both use additional information for relaxing CO constraints and achieving better concurrency and performance. <b>Vote ordering</b> (VO or Generalized CO (GCO); <a href="#Raz2009">Raz 2009</a>) is a container schedule set (property) and technique for CO and all its variants. Local VO is necessary for guaranteeing global serializability if the atomic commitment protocol (ACP) participants do not share concurrency control information (have the <i>generalized autonomy</i> property). CO and its variants inter-operate transparently, guaranteeing global serializability and automatic global deadlock resolution together in a mixed, heterogeneous environment with different variants. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=1" title="Edit section: Overview"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <i>Commitment ordering</i> (CO; <a href="#Raz1990">Raz 1990</a>, <a href="#Raz1992">1992</a>, <a href="#Raz1994">1994</a>, <a href="#Raz2009">2009</a>) schedule property has been referred to also as <i>Dynamic atomicity</i> (since 1988<sup id="cite_ref-Fekete1988_1-1" class="reference"><a href="#cite_note-Fekete1988-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>), <i>commit ordering</i>, <i>commit order serializability</i>, and <i>strong recoverability</i> (since 1991). The latter is a misleading name since CO is incomparable with <i><a href="/wiki/Serializability#Correctness_-_recoverability" class="mw-redirect" title="Serializability">recoverability</a></i>, and the term "strong" implies a special case. This means that a substantial recoverability property does not necessarily have the CO property and vice versa. </p><p>In 2009 CO has been characterized as a major concurrency control method, together with the previously known (since the 1980s) three major methods: <i>Locking</i>, <i>Time-stamp ordering</i>, and <i>Serialization graph testing</i>, and as an enabler for the interoperability of systems using different concurrency control mechanisms.<sup id="cite_ref-Bern2009_2-0" class="reference"><a href="#cite_note-Bern2009-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p><p>In a <a href="/wiki/Federated_database_system" title="Federated database system">federated database system</a> or any other more loosely defined multidatabase system, which are typically distributed in a communication network, transactions span multiple and possibly <a href="/wiki/Distributed_database" title="Distributed database">Distributed databases</a>. Enforcing <a href="/wiki/Global_serializability" title="Global serializability">global serializability</a> in such system is problematic. Even if every local schedule of a single database is still serializable, the global schedule of a whole system is not necessarily serializable. The massive communication exchanges of conflict information needed between databases to reach conflict serializability would lead to unacceptable performance, primarily due to computer and communication <a href="/wiki/Latency_(engineering)" title="Latency (engineering)">latency</a>. The problem of achieving global serializability effectively had been characterized as <a href="/wiki/Open_problem" title="Open problem">open</a> until the public disclosure of CO in 1991 by its <a href="/wiki/Invention" title="Invention">inventor</a> <a href="/w/index.php?title=Yoav_Raz&action=edit&redlink=1" class="new" title="Yoav Raz (page does not exist)">Yoav Raz</a> (<a href="#Raz1991a">Raz 1991a</a>; see also <a href="/wiki/Global_serializability" title="Global serializability">Global serializability</a>). </p><p>Enforcing CO is an effective way to enforce conflict serializability globally in a distributed system since enforcing CO locally in each database (or other transactional objects) also enforces it globally. Each database may use any, possibly different, type of concurrency control mechanism. With a local mechanism that already provides conflict serializability, enforcing CO locally does not cause any other aborts, since enforcing CO locally does not affect the data access scheduling strategy of the mechanism (this scheduling determines the serializability related aborts; such a mechanism typically does not consider the commitment events or their order). The CO solution requires no communication overhead since it uses (unmodified) <i><a href="/w/index.php?title=Atomic_commitment&action=edit&redlink=1" class="new" title="Atomic commitment (page does not exist)">atomic commitment</a></i> protocol messages only, already needed by each distributed transaction to reach atomicity. An atomic commitment protocol plays a central role in the distributed CO algorithm, which enforces CO globally by breaking global cycles (cycles that span two or more databases) in the global conflict graph. CO, its special cases, and its generalizations are interoperable and achieve global serializability while transparently being utilized together in a single heterogeneous distributed environment comprising objects with possibly different concurrency control mechanisms. As such, <i>Commitment ordering</i>, including its special cases, and together with its generalizations (see CO variants below), provides a general, high performance, fully distributed solution (no central processing component or central data structure are needed) for guaranteeing global serializability in heterogeneous environments of multidatabase systems and other multiple transactional objects (objects with states accessed and modified only by transactions; e.g., in the framework of <a href="/w/index.php?title=Transactional_processes&action=edit&redlink=1" class="new" title="Transactional processes (page does not exist)">transactional processes</a>, and within Cloud computing and Grid computing). The CO solution scales up with network size and the number of databases without any negative impact on performance (assuming the statistics of a single distributed transaction, e.g., the average number of databases involved with a single transaction, are unchanged). </p><p>With the proliferation of <a href="/wiki/Multi-core_processor" title="Multi-core processor">Multi-core processors</a>, Optimistic CO (OCO) has also been increasingly utilized to achieve serializability in software transactional memory, and numerous STM articles and patents utilizing "commit order" have already been published (e.g., Zhang et al. 2006<sup id="cite_ref-Zhang2006_3-0" class="reference"><a href="#cite_note-Zhang2006-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>). </p> <div class="mw-heading mw-heading2"><h2 id="The_commitment_ordering_solution_for_global_serializability">The commitment ordering solution for global serializability</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=2" title="Edit section: The commitment ordering solution for global serializability"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="General_characterization_of_CO">General characterization of CO</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=3" title="Edit section: General characterization of CO"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><i>Commitment ordering</i> (CO) is a special case of conflict serializability. CO can be enforced with <i>non-blocking</i> mechanisms (each transaction can complete its task without having its data-access blocked, which allows <a href="/wiki/Optimistic_concurrency_control" title="Optimistic concurrency control">optimistic concurrency control</a>; however, commitment could be blocked). In a CO schedule, the commitment events' (<a href="/wiki/Partial_order" class="mw-redirect" title="Partial order">partial</a>) precedence order of the transactions correspond to the precedence (partial) order of the respective transactions in the (<a href="/wiki/Directed_graph" title="Directed graph">directed</a>) conflict graph (precedence graph, serializability graph), as induced by their conflicting access operations (usually read and write (insert/modify/delete) operations; CO also applies to higher-level operations, where they are conflicting if <a href="/wiki/Noncommutative" class="mw-redirect" title="Noncommutative">noncommutative</a>, as well as to conflicts between operations upon multi-version data). </p> <dl><dt>Definition: commitment ordering</dt> <dd>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1},T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1},T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a0e6aef110538dac610120d6a38a5e5618810d12" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.858ex; height:2.509ex;" alt="{\displaystyle T_{1},T_{2}}"></span> be two <i>committed</i> transactions in a schedule, such that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> is <i>in a conflict</i> with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> <i>precedes</i> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span>). The schedule has the <b>Commitment ordering</b> (CO) property, if for every two such transactions <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> commits before <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> commits.</dd></dl> <p>The commitment decision events are generated by either a local commitment mechanism or an atomic commitment protocol if different processes need to reach a consensus on whether to commit or abort. The protocol may be distributed or centralized. Transactions may be committed concurrently if the commit partial order allows (if they do not have conflicting operations). Suppose different conflicting operations induce different partial orders of the same transactions. In that case, the conflict graph has <a href="/wiki/Cycle_(graph_theory)" title="Cycle (graph theory)">cycles</a>, and the schedule will violate serializability when all the transactions on a cycle are committed. In this case, no partial order for commitment events can be found. Thus, cycles in the conflict graph need to be broken by aborting transactions. However, any conflict serializable schedule can be made CO without aborting any transaction by properly delaying commit events to comply with the transactions' precedence partial order. </p><p>CO enforcement by itself is not sufficient as a concurrency control mechanism since CO lacks the recoverability property, which should be supported as well. </p> <div class="mw-heading mw-heading3"><h3 id="The_distributed_CO_algorithm">The distributed CO algorithm</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=4" title="Edit section: The distributed CO algorithm"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A fully distributed <i>Global commitment ordering</i> enforcement algorithm exists that uses local CO of each participating database, and needs only (unmodified) Atomic commitment protocol messages with no further communication. The distributed algorithm is the combination of local (to each database) CO algorithm processes and an atomic commitment protocol (which can be fully distributed). Atomic commitment protocol is essential to enforce atomicity of each distributed transaction (to decide whether to commit or abort it; this procedure is always carried out for distributed transactions, independently of concurrency control and CO). A common example of an atomic commitment protocol is the <i><a href="/wiki/Two-phase_commit_protocol" title="Two-phase commit protocol">two-phase commit protocol</a></i>, which is resilient to many types of system failure. In a reliable environment, or when processes usually fail together (e.g., in the same <a href="/wiki/Integrated_circuit" title="Integrated circuit">integrated circuit</a>), a simpler protocol for atomic commitment may be used (e.g., a simple handshake of distributed transaction's participating processes with some arbitrary but known special participant, the transaction's coordinator, i.e., a type of <i>one-phase commit</i> protocol). An atomic commitment protocol reaches consensus among participants on whether to <i>commit</i> or <i>abort</i> a distributed (global) transaction that spans these participants. An essential stage in each such protocol is the <b>YES vote</b> (either explicit or implicit) by each participant, which means an obligation of the voting participant to obey the decision of the protocol, either commit or abort. Otherwise, a participant can unilaterally abort the transaction by an explicit NO vote. The protocol commits the transaction only if YES votes have been received from <i>all</i> participants (thus, a missing vote is typically considered a NO). Otherwise, the protocol aborts the transaction. The various atomic commit protocols only differ in their abilities to handle different computing environment failure situations and the amounts of work and other computing resources needed in different situations. </p><p>The entire CO solution for global serializability is based on the fact that the atomic commitment protocol eventually aborts this transaction in case of a missing vote for a distributed transaction. </p> <div class="mw-heading mw-heading4"><h4 id="Enforcing_global_CO">Enforcing global CO</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=5" title="Edit section: Enforcing global CO"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In each database system, a local CO algorithm determines the needed commitment order for that database. By the characterization of CO above, this order depends on the local precedence order of transactions, which results from the local data access scheduling mechanisms. Accordingly, YES votes in the atomic commitment protocol are scheduled for each (unaborted) distributed transaction (in what follows, "a vote" means a YES vote). Suppose a precedence relation (conflict) exists between two transactions. In that case, the second will not be voted on before the first is completed (either committed or aborted), to prevent possible commit order violation by the atomic commitment protocol. Such can happen since the commit order by the protocol is not necessarily the same as the voting order. If no precedence relation exists, both can be voted on concurrently. This <i>vote ordering strategy</i> ensures that also the atomic commitment protocol maintains commitment order, and it is a <i>necessary condition</i> for guaranteeing Global CO (and the local CO of a database; without it both Global CO and Local CO (a property meaning that each database is CO compliant) may be violated). </p><p>However, since database systems schedule their transactions independently, it is possible that the transactions' precedence orders in two databases or more are not compatible (no global partial order exists that can <a href="/wiki/Embedding" title="Embedding">embed</a> the respective local partial orders together). With CO, precedence orders are also the commitment orders. When participating databases in the same distributed transaction do not have compatible local precedence orders for that transaction (without "knowing" it; typically no coordination between database systems exists on conflicts, since the needed communication is massive and unacceptably degrades performance) it means that the transaction resides on a global cycle (involving two or more databases) in the global conflict graph. In this case, the atomic commitment protocol will fail to collect all the votes needed to commit that transaction: By the <i>vote ordering strategy</i> above, at least one database will delay its vote for that transaction indefinitely to comply with its own commitment (precedence) order, since it will be waiting to the completion of another, preceding transactions on that global cycle delayed indefinitely by another database with a different order. This means a <i><b>voting-<a href="/wiki/Deadlock_(computer_science)" title="Deadlock (computer science)">deadlock</a></b></i> situation involving the databases on that cycle. As a result, the protocol will eventually abort some deadlocked transaction on this global cycle, since each such transaction is missing at least one participant's vote. Selection of the specific transaction on the cycle to be aborted depends on the atomic commitment protocol's abort policies (a <a href="/wiki/Timeout_(telecommunication)" class="mw-redirect" title="Timeout (telecommunication)">timeout</a> mechanism is common, but it may result in more than one needed abort per cycle; both preventing unnecessary aborts and abort time shortening can be achieved by a dedicated abort mechanism for CO). Such abort will break the global cycle involving that distributed transaction. Both deadlocked transactions and possibly others in conflict with the deadlocked (and thus blocked) will be free to be voted on. It is worthwhile noting that each database involved with the voting-deadlock continues to vote regularly on transactions that are not in conflict with its deadlocked transaction, typically almost all the outstanding transactions. Thus, in the case of incompatible local (partial) commitment orders, no action is needed since the atomic commitment protocol resolves it automatically by aborting a transaction that is a cause of incompatibility. This means that the above <i>vote ordering strategy</i> is also a <i>sufficient condition</i> for guaranteeing Global CO. </p><p>The following is concluded: </p> <ul><li><b>The Vote ordering strategy for Global CO Enforcing <a href="/wiki/Theorem" title="Theorem">Theorem</a></b></li></ul> <dl><dd>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1},T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1},T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a0e6aef110538dac610120d6a38a5e5618810d12" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.858ex; height:2.509ex;" alt="{\displaystyle T_{1},T_{2}}"></span> be undecided (neither committed nor aborted) transactions in a database system that enforces CO for local transactions, such that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> is <i>global</i> and <i>in conflict</i> with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> <i>precedes</i> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span>). Then, having <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> ended (either committed or aborted) before <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> is voted on to be committed (the <i>vote ordering strategy</i>), in each such database system in a multidatabase environment, is a <a href="/wiki/Necessary_and_sufficient_condition" class="mw-redirect" title="Necessary and sufficient condition">necessary and sufficient condition</a> for guaranteeing Global CO (the condition guarantees Global CO, which may be violated without it).</dd></dl> <dl><dd><b>Comments:</b></dd></dl> <ol><li>The <i>vote ordering strategy</i> that enforces global CO is referred to as <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle CD^{3}C}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <msup> <mi>D</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msup> <mi>C</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle CD^{3}C}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7ff359b5595f234adf7c923770a7a481a7bb3bb6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.511ex; height:2.676ex;" alt="{\displaystyle CD^{3}C}"></span> in (<a href="#Raz1992">Raz 1992</a>).</li> <li>The Local CO property of a global schedule means that each database is CO compliant. From the necessity discussion, the part above directly follows that the theorem is also true when replacing "Global CO" with "Local CO" when global transactions are present. Together it means that Global CO is guaranteed <a href="/wiki/If_and_only_if" title="If and only if">if and only if</a> Local CO is guaranteed (which is untrue for Global conflict serializability and Local conflict serializability: Global implies Local, but not the opposite).</li></ol> <p>Global CO implies Global serializability. </p><p>The <b>Global CO algorithm</b> comprises enforcing (local) CO in each participating database system by ordering commits of local transactions (see <a class="mw-selflink-fragment" href="#Enforcing_CO_locally">Enforcing CO locally</a> below) and enforcing the <i>vote ordering strategy</i> in the theorem above (for global transactions). </p> <div class="mw-heading mw-heading4"><h4 id="The_exact_characterization_of_voting-deadlocks_by_global_cycles">The exact characterization of voting-deadlocks by global cycles</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=6" title="Edit section: The exact characterization of voting-deadlocks by global cycles"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The above global cycle elimination process by a <b>voting deadlock</b> can be explained in detail by the following observation: </p><p>First, it is assumed, for simplicity, that every transaction reaches the ready-to-commit state and is voted on by at least one database (this implies that no blocking by locks occurs). Define a <i>"wait for vote to commit" graph</i> as a directed graph with transactions as nodes and a directed edge from any first transaction to a second transaction if the first transaction blocks the vote to commit of the second transaction (opposite to conventional edge direction in a <a href="/wiki/Wait-for_graph" title="Wait-for graph">wait-for graph</a>). Such blocking happens only if the second transaction conflicts with the first transaction (see above). Thus this "wait for vote to commit" graph is identical to the global conflict graph. A cycle in the "wait for vote to commit" graph means a deadlock in voting. Hence there is a deadlock in voting if there is a cycle in the conflict graph. The local serializability mechanisms eliminate local cycles (confined to a single database). Consequently, only global cycles are left, which are then eliminated by the atomic commitment protocol when it aborts deadlocked transactions with missing (blocked) respective votes. </p><p>Secondly, also local commits are dealt with: Note that when enforcing CO, also waiting for a regular local commit of a local transaction can block local commits and votes of other transactions upon conflicts, and the situation for global transactions does not also change without the simplifying assumption above: The final result is the same also with a local commitment for local transactions, without voting in atomic commitment for them. </p><p>Finally, blocking by a lock (which has been excluded so far) needs to be considered: A lock blocks a conflicting operation and prevents a conflict from being materialized. Suppose the lock is released only after the transaction end. In that case, it may block indirectly either a vote or a local commit of another transaction (which now cannot get to ready state), with the same effect as a direct blocking of a vote or a local commit. A cycle is generated in the conflict graph only if such blocking by a lock is also represented by an edge. With such added edges representing events of blocking-by-a-lock, the conflict graph is becoming an <i>augmented conflict graph</i>. </p> <ul><li><b>Definition: augmented conflict graph</b></li></ul> <dl><dd>An <b>augmented conflict graph</b> is a <a href="/wiki/Serializability#Testing_conflict_serializability" class="mw-redirect" title="Serializability">conflict graph</a> with added edges: In addition to the original edges a directed edge exists from transaction <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> to transaction <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> if two conditions are met:</dd></dl> <ol><li><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> is blocked by a data-access lock applied by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> (the blocking prevents the conflict of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> from being materialized and have an edge in the regular conflict graph), and</li> <li>This blocking will not stop before <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> ends (commits or aborts; true for any locking-based CO)</li></ol> <dl><dd>The graph can also be defined as the <a href="/wiki/Union_(set_theory)" title="Union (set theory)">union</a> of the (regular) <i>conflict graph</i> with the (reversed edge, regular) <i>wait-for graph</i></dd></dl> <dl><dd><b>Comments:</b></dd></dl> <ol><li>Here, unlike the regular conflict graph, which has edges only for materialized conflicts, all materialized, and non-materialized conflicts are represented by edges.</li> <li>Note that all the new edges are all the (reversed to the conventional) edges of the <i>wait-for graph</i>. The <i>wait-for graph</i> can also be defined as the graph of non-materialized conflicts. By the common conventions, edge direction in a <i>conflict graph</i> defines time order between conflicting operations, which is opposite to the time order defined by an edge in a <i>wait-for graph</i>.</li> <li>Note that such a global graph contains (has embedded) all the (reversed edge) regular local <i>wait-for</i> graphs and also may include locking based global cycles (which cannot exist in the local graphs). For example, if all the databases on a global cycle are SS2PL based, then all the related vote blocking situations are caused by locks (this is the classical and probably the only global deadlock situation dealt with in the database research literature). This is a global deadlock case where each related database creates a portion of the cycle, but the complete cycle does not reside in any local wait-for graph.</li></ol> <p>In the presence of CO, the <i>augmented conflict graph</i> is, in fact, a (reversed edge) <i>local-commit and voting wait-for graph</i>: An edge exists from a first transaction, either local or global, to a second, if the second is waiting for the first to end in order to be either voted on (if global) or locally committed (if local). All <i>global cycles</i> (across two or more databases) in this graph generate voting-deadlocks. The graph's global cycles provide complete characterization for voting deadlocks and may include any combination of materialized and non-materialized conflicts. Only cycles of (only) materialized conflicts are also cycles of the regular conflict graph and affect serializability. One or more (lock related) non-materialized conflicts on a cycle prevent it from being a cycle in the regular conflict graph and make it a locking related deadlock. All the global cycles (voting-deadlocks) need to be broken (resolved) to both maintain global serializability and resolve global deadlocks involving data access locking. Indeed they are all broken by the atomic commitment protocol due to missing votes upon a voting deadlock. </p><p><b>Comment:</b> This observation also explains the correctness of <i><a class="mw-selflink-fragment" href="#Extended_CO_(ECO)">Extended CO (ECO)</a></i> below: Global transactions' voting order must follow the conflict graph order with vote blocking when order relation (graph path) exists between two global transactions. Local transactions are not voted on, and their (local) commits are not blocked upon conflicts. This results in the same voting-deadlock situations and resulting global cycle elimination process for ECO. </p><p>The <i>voting-deadlock</i> situation can be summarized as follows: </p> <ul><li><b>The CO Voting-Deadlock Theorem</b></li></ul> <dl><dd>Let a multidatabase environment comprise CO compliant (which eliminates <i>local cycles</i>) database systems that enforce each <i>Global CO</i> (using the condition in the theorem above). A <i>voting-deadlock</i> occurs if and only if a <i>global cycle</i> (spans two or more databases) exists in the <i>Global augmented conflict graph</i> (also blocking by a data-access lock is represented by an edge). Suppose the cycle does not break by any abort. In that case, all the <i>global transactions</i> on it are involved with the respective voting-deadlock. Eventually, each has its vote blocked (either directly or indirectly by a data-access lock); if a local transaction resides on the cycle, eventually, it has its (local) commit blocked.</dd></dl> <dl><dd><b>Comment:</b> A rare situation of a voting deadlock (by missing blocked votes) can happen, with no voting for any transaction on the related cycle by any of the database systems involved with these transactions. This can occur when local sub-transactions are <a href="/wiki/Thread_(computer_science)" class="mw-redirect" title="Thread (computer science)">multi-threaded</a>. The highest probability instance of such a rare event involves two transactions on two simultaneous opposite cycles. Such global cycles (deadlocks) overlap with local cycles that are resolved locally and are typically resolved by local mechanisms without involving atomic commitment. Formally it is also a global cycle, but practically it is local (portions of local cycles generate a global one; to see this, split each global transaction (node) to local sub-transactions (its portions confined each to a single database); a directed edge exists between transactions if an edge exists between any respective local sub-transactions; a cycle is local if all its edges originate from a cycle among sub-transactions of the same database, and global if not; global and local can overlap: the same cycle among transactions can result from several different cycles among sub-transactions, and be both local and global).</dd></dl> <p>Also, the following locking based special case is concluded: </p> <ul><li><b>The CO Locking-based Global-Deadlock Theorem</b></li></ul> <dl><dd>In a CO compliant multidatabase system, a locking-based global-deadlock, involving at least one data-access lock (non-materialized conflict), and two or more database systems, is a reflection of a global cycle in the <i>Global augmented conflict graph</i>, which results in a voting-deadlock. Such a cycle is not a cycle in the (regular) <i>Global conflict graph</i> (which reflects only materialized conflicts, so such a cycle does not affect <i><a href="/wiki/Serializability" class="mw-redirect" title="Serializability">serializability</a></i>).</dd></dl> <dl><dd><b>Comments:</b></dd></dl> <ol><li>Any blocking (edge) in the cycle that is not by a data-access lock directly blocks either voting or local commit. All voting-deadlocks are resolved (almost all by <i>Atomic commitment</i>; see comment above), including this locking-based type.</li> <li>Locking-based global-deadlocks can also be generated in a completely SS2PL-based distributed environment (special case of CO based). All the vote blocking (and voting-deadlocks) are caused by data-access locks. Many research articles have dealt for years with resolving such global deadlocks, but none (except the CO articles) is known (as of 2009) to notice that <i>atomic commitment</i> automatically resolves them. Such automatic resolutions are regularly occurring unnoticed in all existing SS2PL based multidatabase systems, often bypassing dedicated resolution mechanisms.</li></ol> <p>Voting-deadlocks are the key to the operation of distributed CO. </p><p>Global cycle elimination (here voting-deadlock resolution by <i>atomic commitment</i>) and resulting aborted transactions' re-executions are time-consuming, regardless of concurrency control used. If databases schedule transactions independently, global cycles are unavoidable (in a complete analogy to cycles/deadlocks generated in local SS2PL; with distribution, any transaction or operation scheduling coordination results in autonomy violation and is typically in substantial performance penalty). However, their likelihood can be made very low in many cases by implementing database and transaction design guidelines that reduce the number of conflicts involving a global transaction. This, primarily by properly handling hot spots (database objects with frequent access,) and avoiding conflicts by using commutativity when possible (e.g., when extensively using counters, as in finances, and especially multi-transaction <i>accumulation counters</i>, which are typically hot spots). </p><p>Atomic commitment protocols are intended and designed to achieve atomicity without considering database concurrency control. They abort upon detecting or <a href="/wiki/Heuristic_algorithm" class="mw-redirect" title="Heuristic algorithm">heuristically</a> finding (e.g., by a timeout; sometimes mistakenly, unnecessarily) missing votes and typically unaware of global cycles. These protocols can be especially enhanced for CO (including CO's variants below) to prevent unnecessary aborts and accelerate aborts used for breaking global cycles in the global augmented conflict graph (for better performance by earlier release upon transaction-end of computing resources and typically locked data). For example, existing locking based global deadlock detection methods, other than the timeout, can be generalized also to consider local commit and vote direct blocking, besides data access blocking. A possible compromise in such mechanisms is effectively detecting and breaking the most frequent and relatively simple to handle length-2 global cycles, and using timeout for undetected, much less frequent, longer cycles. </p> <div class="mw-heading mw-heading3"><h3 id="Enforcing_CO_locally">Enforcing CO locally</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=7" title="Edit section: Enforcing CO locally"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><i>Commitment ordering</i> can be enforced locally (in a single database) by a dedicated CO algorithm, or by any algorithm/protocol that provides any special case of CO. An important such protocol, being utilized extensively in database systems, which generates a CO schedule, is the <i>strong strict <a href="/wiki/Two_phase_locking" class="mw-redirect" title="Two phase locking">two phase locking</a></i> protocol (SS2PL: "release transaction's locks only after the transaction has been either committed or aborted"; see below). SS2PL is a <a href="/wiki/Proper_subset" class="mw-redirect" title="Proper subset">proper subset</a> of the intersection of <a href="/wiki/Two-phase_locking" title="Two-phase locking">2PL</a> and strictness. </p> <div class="mw-heading mw-heading4"><h4 id="A_generic_local_CO_algorithm">A generic local CO algorithm</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=8" title="Edit section: A generic local CO algorithm"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A <b>generic local CO algorithm</b> (<a href="#Raz1992">Raz 1992</a>; Algorithm 4.1) is an algorithm independent of implementation details that enforces exactly the CO property. It does not block data access (nonblocking) and consists of aborting a certain set of transactions (only if needed) upon committing a transaction. It aborts a (uniquely determined at any given time) minimal set of other undecided (neither committed, nor aborted) transactions that run locally and can cause serializability violation in the future (can later generate cycles of committed transactions in the conflict graph; this is the ABORT set of a committed transaction T; after committing T no transaction in ABORT at commit time can be committed, and all of them are doomed to be aborted). This set consists of all undecided transactions with directed edges in the conflict graph to the committed transaction. The size of this set cannot increase when that transaction is waiting to be committed (in the ready state: processing has ended,) and typically decreases in time as its transactions are being decided. Thus, unless <a href="/wiki/Real-time_computing" title="Real-time computing">real-time</a> constraints exist to complete that transaction, it is preferred to wait with committing that transaction and let this set decrease in size. If another serializability mechanism exists locally (which eliminates cycles in the local conflict graph), or if no cycle involving that transaction exists, the set will be empty eventually, and no abort of a set member is needed. Otherwise, the set will stabilize with transactions on local cycles, and aborting set members will have to occur to break the cycles. Since in the case of CO conflicts generate blocking on commit, local cycles in the <i>augments conflict graph</i> (see above) indicate local commit-deadlocks, and deadlock resolution techniques as in <a href="/wiki/Serializability#Common_mechanism_-_SS2PL" class="mw-redirect" title="Serializability">SS2PL</a> can be used (e.g., like <i>timeout</i> and <i>wait-for graph</i>). A local cycle in the <i>augmented conflict graph</i> with at least one non-materialized conflict reflects a locking-based deadlock. The <a href="/wiki/Local_algorithm" title="Local algorithm">local algorithm</a> above, applied to the local augmented conflict graph rather than the regular local conflict graph, comprises the <b>generic enhanced local CO algorithm</b>, a single local cycle elimination mechanism, for both guaranteeing local serializability and handling locking based local deadlocks. Practically an additional concurrency control mechanism is always utilized, even solely to enforce recoverability. The generic CO algorithm does not affect the local data access scheduling strategy when it runs alongside any other local concurrency control mechanism. It affects only the commit order, and for this reason, it does not need to abort more transactions than those needed to be aborted for serializability violation prevention by any combined local concurrency control mechanism. At most, the net effect of CO may be a delay of commit events (or voting in a distributed environment), to comply with the needed commit order (but not more delay than its special cases, for example, SS2PL, and on average significantly less). </p><p>The following theorem is concluded: </p> <ul><li><b>The Generic Local CO Algorithm Theorem</b></li></ul> <dl><dd>When running alone or alongside any concurrency control mechanism in a database system, then</dd></dl> <ol><li>The <i>Generic local CO algorithm</i> guarantees (local) CO (a CO compliant schedule).</li> <li>The <i>Generic enhanced local CO algorithm</i> guarantees both (local) CO and (local) locking based deadlock resolution. And (when not using a <i>timeout</i>, and no <i>real-time</i> transaction completion constraints are applied) neither algorithm aborts more transactions than the minimum needed (which is determined by the transactions' operations scheduling, out of the scope of the algorithms).</li></ol> <div class="mw-heading mw-heading4"><h4 id="Example:_Concurrent_programming_and_Transactional_memory">Example: Concurrent programming and Transactional memory</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=9" title="Edit section: Example: Concurrent programming and Transactional memory"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <dl><dd>See also <i><a href="/w/index.php?title=The_History_of_Commitment_Ordering&action=edit&redlink=1" class="new" title="The History of Commitment Ordering (page does not exist)">Concurrent programming and Transactional memory.</a></i></dd></dl> <p>With the proliferation of Multi-core processors, variants of the Generic local CO algorithm have also been increasingly utilized in Concurrent programming, <a href="/wiki/Transactional_memory" title="Transactional memory">Transactional memory</a>, and especially in Software transactional memory for achieving serializability optimistically by "commit order" (e.g., Ramadan et al. 2009,<sup id="cite_ref-Ramadan2009_4-0" class="reference"><a href="#cite_note-Ramadan2009-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Zhang et al. 2006,<sup id="cite_ref-Zhang2006_3-1" class="reference"><a href="#cite_note-Zhang2006-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> von Parun et al. 2007<sup id="cite_ref-vonParun2007_5-0" class="reference"><a href="#cite_note-vonParun2007-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>). Numerous related articles and patents utilizing CO have already been published. </p> <div class="mw-heading mw-heading4"><h4 id="Implementation_considerations:_The_Commitment_Order_Coordinator_(COCO)"><span id="Implementation_considerations:_The_Commitment_Order_Coordinator_.28COCO.29"></span>Implementation considerations: The Commitment Order Coordinator (COCO)</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=10" title="Edit section: Implementation considerations: The Commitment Order Coordinator (COCO)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A database system in a multidatabase environment is assumed. From a <a href="/wiki/Software_architecture" title="Software architecture">software architecture</a> point of view, a CO component that implements the generic CO algorithm locally, the <i>Commitment Order Coordinator</i> (COCO), can be designed straightforwardly as a <a href="/wiki/Mediator_pattern" title="Mediator pattern">mediator</a> between a (single) database system and an atomic commitment protocol component (<a href="#Raz1991b">Raz 1991b</a>). However, the COCO is typically an integral part of the database system. The COCO's functions are to vote to commit on ready global transactions (the processing has ended) according to the local commitment order, to vote to abort on transactions for which the database system has initiated an abort (the database system can initiate abort for any transaction, for many reasons), and to pass the atomic commitment decision to the database system. For local transactions (when can be identified), no voting is needed. For determining the commitment order, the COCO maintains an updated representation of the local conflict graph (or local augmented conflict graph for capturing also locking deadlocks) of the undecided (neither committed nor aborted) transactions as a data structure (e.g., utilizing mechanisms similar to <a href="/wiki/Lock_(computer_science)" title="Lock (computer science)">locking</a> for capturing conflicts, but with no data-access blocking). The COCO component has an <a href="/wiki/Interface_(computer_science)" class="mw-redirect" title="Interface (computer science)">interface</a> with its database system to receive "conflict," "ready" (the processing has ended; readiness to vote on a global transaction or commit a local one), and "abort" notifications from the database system. It also interfaces with the atomic commitment protocol to vote and receive the atomic commitment protocol's decision on each global transaction. The decisions are delivered from the COCO to the database system through their interface, as well as local transactions' commit notifications, at a proper commit order. The COCO, including its interfaces, can be enhanced, if it implements another variant of CO (see below) or plays a role in the database's concurrency control mechanism beyond voting in atomic commitment. </p><p>The COCO also guarantees CO locally in a single, isolated database system with no interface with an atomic commitment protocol. </p> <div class="mw-heading mw-heading3"><h3 id="CO_is_a_necessary_condition_for_global_serializability_across_autonomous_database_systems.">CO is a necessary condition for global serializability across autonomous database systems.</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=11" title="Edit section: CO is a necessary condition for global serializability across autonomous database systems."><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Suppose databases that participate in distributed transactions (i.e., transactions that span more than a single database) do not use any shared concurrency control information and use unmodified atomic commitment protocol messages (for reaching atomicity). In that case, maintaining (local) <i>commitment ordering</i> or one of its generalizing variants (see below) is a <a href="/wiki/Necessary_condition" class="mw-redirect" title="Necessary condition">necessary condition</a> for guaranteeing global serializability (a proof technique can be found in (<a href="#Raz1992">Raz 1992</a>), and a different proof method for this in (<a href="#Raz1993a">Raz 1993a</a>)); it is also a <a href="/wiki/Sufficient_condition" class="mw-redirect" title="Sufficient condition">sufficient condition</a>. This is a mathematical fact derived from the definitions of <i>serializability</i> and a <i><a href="/wiki/Database_transaction" title="Database transaction">transaction</a></i>. It means that if not complying with CO, then global serializability cannot be guaranteed under this condition (the condition of no local concurrency control information sharing between databases beyond atomic commit protocol messages). Atomic commitment is a minimal requirement for a distributed transaction since it is always needed, which is implied by the transaction definition. </p><p>(<a href="#Raz1992">Raz 1992</a>) defines <i>database autonomy</i> and <i>independence</i> as complying with this requirement without using any additional local knowledge: </p> <ul><li><b>Definition:</b> (concurrency control based) <b>autonomous database system</b></li></ul> <dl><dd>A database system is <b>Autonomous</b>, if it does not share any concurrency control information beyond unmodified <a href="/w/index.php?title=Atomic_commitment_protocol&action=edit&redlink=1" class="new" title="Atomic commitment protocol (page does not exist)">atomic commitment protocol</a> messages with any other entity. In addition, it does not use for concurrency control any additional local information beyond conflicts (the last sentence does not appear explicitly but rather implied by further discussion in <a href="#Raz1992">Raz 1992</a>).</dd></dl> <p>Using this definition, the following is concluded: </p> <ul><li><b>The CO and Global serializability Theorem</b></li></ul> <ol><li>CO compliance of every <i>autonomous</i> database system (or transactional object) in a multidatabase environment is a <i>necessary condition</i> for guaranteeing Global serializability (without CO, Global serializability may be violated).</li> <li>CO compliance with every database system is a <i>sufficient condition</i> for guaranteeing Global serializability.</li></ol> <p>However, the definition of autonomy above implies, for example, that transactions are scheduled in a way that local transactions (confined to a single database) cannot be identified as such by an autonomous database system. This is realistic for some transactional objects but too restrictive and less realistic for general purpose database systems. If autonomy is augmented with the ability to identify local transactions, then compliance with a more general property, <i>Extended commitment ordering</i> (ECO, see below), makes ECO the necessary condition. </p><p>Only in (<a href="#Raz2009">Raz 2009</a>) the notion of <i>Generalized autonomy</i> captures the intended notion of autonomy: </p> <ul><li><b>Definition: generalized autonomy</b></li></ul> <dl><dd>A database system has the <i>Generalized autonomy</i> property if it does not share any other database system any local concurrency information beyond (unmodified) atomic commit protocol messages (however, any local information can be utilized).</dd></dl> <p>This definition is probably the broadest such definition possible in the context of database concurrency control, and it makes CO together with any of its (useful: No concurrency control information distribution) generalizing variants (Vote ordering (VO); see CO variants below) the necessary condition for Global serializability (i.e., the union of CO and its generalizing variants is the necessary set VO, which may also include new unknown useful generalizing variants). </p> <div class="mw-heading mw-heading3"><h3 id="Summary">Summary</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=12" title="Edit section: Summary"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The <i>Commitment ordering</i> (CO) solution (technique) for global serializability can be summarized as follows: </p><p>If each <i>database</i> (or any other <i>transactional object</i>) in a multidatabase environment complies with CO, i.e., arranges its local transactions' commitments and its votes on (global, distributed) transactions to the <i><a href="/w/index.php?title=Atomic_commitment&action=edit&redlink=1" class="new" title="Atomic commitment (page does not exist)">atomic commitment</a></i> protocol according to the local (to the database) <a href="/wiki/Partial_order" class="mw-redirect" title="Partial order">partial order</a> induced by the local conflict graph (serializability graph) for the respective transactions, then <i>Global CO</i> and <i>Global serializability</i> are guaranteed. A database's CO compliance can be achieved effectively with any local <a href="/wiki/Serializability#View_serializability_and_conflict_serializability" class="mw-redirect" title="Serializability">conflict serializability</a> based concurrency control mechanism, neither affecting any transaction's execution process or scheduling nor aborting it. Also, the database's autonomy is not violated. The only low overhead incurred is detecting conflicts (e.g., with locking, but with no data-access blocking; if not already detected for other purposes) and ordering votes and local transactions' commits according to the conflicts. </p> <figure typeof="mw:File/Thumb"><a href="/wiki/File:CO-ScheduleClasses.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/d/db/CO-ScheduleClasses.jpg/350px-CO-ScheduleClasses.jpg" decoding="async" width="350" height="435" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/d/db/CO-ScheduleClasses.jpg/525px-CO-ScheduleClasses.jpg 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/d/db/CO-ScheduleClasses.jpg/700px-CO-ScheduleClasses.jpg 2x" data-file-width="869" data-file-height="1080" /></a><figcaption> <b>Schedule classes containment:</b> An arrow from class A to class B indicates that class A strictly contains B; a lack of a directed path between classes means that the classes are incomparable. A property is <b>inherently blocking</b>, if it can be enforced only by blocking transaction's data access operations until certain events occur in other transactions. (<a href="#Raz1992">Raz 1992</a>)</figcaption></figure> <p>In case of incompatible partial orders of two or more databases (no global partial order can <a href="/wiki/Embedding" title="Embedding">embed</a> the respective local partial orders together), a global cycle (spans two databases or more) in the global conflict graph is generated. This, together with CO, results in a cycle of blocked votes. A <i>voting-<a href="/wiki/Deadlock_(computer_science)" title="Deadlock (computer science)">deadlock</a></i> occurs for the databases on that cycle (however, allowed concurrent voting in each database, typically for almost all the outstanding votes, continue to execute). In this case, the atomic commitment protocol fails to collect all the votes needed for the blocked transactions on that global cycle. Consequently the protocol aborts some transactions with a missing vote. This breaks the global cycle, the voting-deadlock is resolved, and the related blocked votes are free to be executed. Breaking the global cycle in the global conflict graph ensures that global CO and global serializability are maintained. Thus, in the case of incompatible local (partial) commitment orders, no action is needed since the atomic commitment protocol resolves it automatically by aborting a transaction that is a cause for the incompatibility. Furthermore, global deadlocks due to locking (global cycles in the <i>augmented conflict graph</i> with at least one data access blocking) result in voting deadlocks and are resolved automatically by the same mechanism. </p><p><i>Local CO</i> is a necessary condition for guaranteeing <i>Global serializability</i> if the databases involved do not share any concurrency control information beyond (unmodified) atomic commitment protocol messages, i.e., if the databases are <i>autonomous</i> in the context of concurrency control. This means that every global serializability solution for autonomous databases must comply with CO. Otherwise, global serializability may be violated (and thus, is likely to be violated very quickly in a high-performance environment). </p><p>The CO solution <a href="/wiki/Scalability" title="Scalability">scales up</a> with network size and the number of databases without performance penalty when it utilizes <a href="/wiki/Two-phase_commit_protocol#Common_architecture" title="Two-phase commit protocol">common distributed atomic commitment architecture</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Distributed_serializability_and_CO">Distributed serializability and CO</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=13" title="Edit section: Distributed serializability and CO"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Distributed_CO">Distributed CO</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=14" title="Edit section: Distributed CO"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A distinguishing characteristic of the CO solution to distributed serializability from other techniques is the fact that it requires no conflict information distributed (e.g., local precedence relations, locks, <a href="/wiki/Timestamp-based_concurrency_control" title="Timestamp-based concurrency control">timestamps</a>, tickets), which makes it uniquely effective. It utilizes (unmodified) atomic commitment protocol messages (which are already used) instead. </p><p>A common way to achieve distributed serializability in a <a href="/wiki/Distributed_system" class="mw-redirect" title="Distributed system">(distributed) system</a> is by a <a href="/wiki/Distributed_lock_manager" title="Distributed lock manager">distributed lock manager</a> (DLM). DLMs, which communicate lock (non-materialized conflict) information in a distributed environment, typically suffer from computer and communication <a href="/wiki/Latency_(engineering)" title="Latency (engineering)">latency</a>, which reduces the performance of the system. CO allows to achieve distributed serializability under very general conditions, without a distributed lock manager, exhibiting the benefits already explored above for multidatabase environments; in particular: reliability, high performance, scalability, the possibility of using <i>optimistic concurrency control</i> when desired, no conflict information related communications over the network (which have incurred overhead and delays), and automatic <a href="/wiki/Distributed_deadlock" class="mw-redirect" title="Distributed deadlock">distributed deadlock</a> resolution. </p><p>All <i>distributed transactional systems</i> rely on some atomic commitment protocol to coordinate atomicity (whether to commit or abort) among processes in a <a href="/wiki/Distributed_transaction" title="Distributed transaction">distributed transaction</a>. Also, typically <i>recoverable data</i> (i.e., data under transactions' control, e.g., database data; not to be confused with the <i>recoverability</i> property of a schedule) are directly accessed by a single <i>transactional data manager</i> component (also referred to as a <i>resource manager</i>) that handles local sub-transactions (the distributed transaction's portion in a single location, e.g., network node), even if these data are accessed indirectly by other entities in the distributed system during a transaction (i.e., indirect access requires a direct access through a local sub-transaction). Thus recoverable data in a distributed transactional system are typically partitioned among transactional data managers. In such system, these transactional data managers typically comprise the participants in the system's atomic commitment protocol. If each participant complies with CO (e.g., by using SS2PL, or COCOs, or a combination; see above), then the entire distributed system provides CO (by the theorems above; each participant can be considered a separate transactional object), and thus (distributed) serializability. Furthermore: When CO is utilized together with an atomic commitment protocol also <i><a href="/wiki/Distributed_deadlock" class="mw-redirect" title="Distributed deadlock">distributed deadlocks</a></i> (i.e., deadlocks that span two or more data managers) caused by data-access locking are resolved automatically. Thus the following corollary is concluded: </p> <ul><li><b>The CO Based Distributed Serializability Theorem</b></li></ul> <dl><dd>Let a <i>distributed transactional system</i> (e.g., a <a href="/wiki/Distributed_database" title="Distributed database">distributed database</a> system) comprise <i>transactional data managers</i> (also called <i>resource managers</i>) that manage all the system's <i>recoverable data</i>. The data managers meet three conditions:</dd></dl> <ol><li><b>Data partition:</b> Recoverable data are partitioned among the data managers, i.e., each recoverable datum (data item) is controlled by a single data manager (e.g., as common in a <a href="/wiki/Shared_nothing_architecture" class="mw-redirect" title="Shared nothing architecture">Shared nothing architecture</a>; even copies of the same datum under different data managers are physically distinct, <i>replicated</i>).</li> <li><b>Participants in atomic commitment protocol:</b> These data managers are the participants in the system's atomic commitment protocol for coordinating distributed transactions' atomicity.</li> <li><b>CO compliance:</b> Each such data manager is CO compliant (or some CO variant compliant; see below).</li></ol> <dl><dd>Then</dd></dl> <ol><li>The entire distributed system guarantees (distributed CO and) <i>serializability</i>, and</li> <li>Data-access-based <i>distributed deadlocks</i> (deadlocks involving two or more data managers with at least one non-materialized conflict) are resolved automatically.</li></ol> <dl><dd>Furthermore: The data managers being CO compliant is a <i>necessary condition</i> for (distributed) serializability in a system meeting conditions 1, 2 above, when the data managers are <i>autonomous</i>, i.e., do not share concurrency control information beyond unmodified messages of atomic commitment protocol.</dd></dl> <p>This theorem also means that when SS2PL (or any other CO variant) is used locally in each transactional data manager, and each data manager has exclusive control of its data, no distributed lock manager (which is often utilized to enforce distributed SS2PL) is needed for distributed SS2PL and serializability. It is relevant to a wide range of distributed transactional applications, which can be easily designed to meet the theorem's conditions. </p> <div class="mw-heading mw-heading3"><h3 id="Distributed_optimistic_CO_(DOCO)"><span id="Distributed_optimistic_CO_.28DOCO.29"></span>Distributed optimistic CO (DOCO)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=15" title="Edit section: Distributed optimistic CO (DOCO)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For implementing Distributed Optimistic CO (DOCO), the generic local CO algorithm is utilized in all the atomic commitment protocol participants in the system with no data access blocking and thus with no local deadlocks. The previous theorem has the following corollary: </p> <ul><li><b>The Distributed optimistic CO (DOCO) Theorem</b></li></ul> <dl><dd>If DOCO is utilized, then: <ol><li>No local deadlocks occur, and</li> <li>Global (voting) deadlocks are resolved automatically (and all are serializability related (with non-blocking conflicts) rather than locking related (with blocking and possibly also non-blocking conflicts)).</li></ol></dd></dl> <dl><dd>Thus, no deadlock handling is needed.</dd></dl> <div class="mw-heading mw-heading3"><h3 id="Examples">Examples</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=16" title="Edit section: Examples"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading4"><h4 id="Distributed_SS2PL">Distributed SS2PL</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=17" title="Edit section: Distributed SS2PL"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A distributed database system that utilizes <a href="/wiki/Two-phase_locking#Strong_strict_two-phase_locking" title="Two-phase locking">SS2PL</a> resides on two remote nodes, A and B. The database system has two <i>transactional data managers</i> (<i>resource managers</i>), one on each node, and the database data are partitioned between the two data managers in a way that each has an exclusive control of its own (local to the node) portion of data: Each handles its own data and locks without any knowledge on the other manager's. For each distributed transaction such data managers need to execute the available atomic commitment protocol. </p><p>Two distributed transactions, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span>, are running concurrently, and both access data x and y. x is under the exclusive control of the data manager on A (B's manager cannot access x), and y under that on B. </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> reads x on A and writes y on B, i.e., <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}=R_{\text{1A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}=R_{\text{1A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f2c5dd20d02b9abf6fdd1248926291ec57f65450" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.7ex; height:2.843ex;" alt="{\displaystyle T_{1}=R_{\text{1A}}(x)}"></span> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{\text{1B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{\text{1B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/443d1246bf450b6c658666e056a08d70857f5684" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.376ex; height:2.843ex;" alt="{\displaystyle W_{\text{1B}}(y)}"></span> when using notation common for concurrency control.</dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> reads y on B and writes x on A, i.e., <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}=R_{\text{2B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>=</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}=R_{\text{2B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8dfdaaa0ca846ad4e58728cbe5a120e9cb5a3fd1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.457ex; height:2.843ex;" alt="{\displaystyle T_{2}=R_{\text{2B}}(y)}"></span> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{\text{2A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{\text{2A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec17fa4cfd3a886ad454ad6a775a63d7ad17eee7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.619ex; height:2.843ex;" alt="{\displaystyle W_{\text{2A}}(x)}"></span></dd></dl> <p>The respective <i>local sub-transactions</i> on A and B (the portions of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> on each of the nodes) are the following: </p> <dl><dd><table class="wikitable" style="text-align:center;"> <caption>Local sub-transactions </caption> <tbody><tr> <th style="background:var(--background-color-neutral,#eaecf0);color:inherit;background:linear-gradient(to top right,var(--background-color-neutral,#eaecf0) 49%,var(--border-color-base,#a2a9b1) 49.5%,var(--border-color-base,#a2a9b1) 50.5%,var(--background-color-neutral,#eaecf0) 51%);line-height:1.2;padding:0.1em 0.4em;"><div style="margin-left:2em;text-align:right"> Node</div><div style="margin-right:2em;text-align:left"> Transaction </div></th> <th>A</th> <th>B </th></tr> <tr> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> </th> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/36a6f9af0af124dcaf6dc1a7a0e037520663a67b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.933ex; height:2.843ex;" alt="{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}"></span></td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1B</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6edd8dbe82a9915e2afc3fa0cfd1336edb58711c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.05ex; height:2.843ex;" alt="{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}"></span> </td></tr> <tr> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> </th> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2A</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cf6d10fc3c5ea83c70eacdfdcad8267323c8e421" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.362ex; height:2.843ex;" alt="{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}"></span></td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4cd8e6837840b169bf6587850bb9c7c38c5d8f48" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.62ex; height:2.843ex;" alt="{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}"></span> </td></tr></tbody></table></dd></dl> <p>The database system's <a href="/wiki/Database_transaction_schedule" title="Database transaction schedule">schedule</a> at a certain point in time is the following: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\text{1A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\text{1A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/37761811653d05232f522bc1e032aa414767823e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.19ex; height:2.843ex;" alt="{\displaystyle R_{\text{1A}}(x)}"></span> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\text{2B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\text{2B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/42df4d39055471f4a7e14ee5aac8224b4275ba69" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.947ex; height:2.843ex;" alt="{\displaystyle R_{\text{2B}}(y)}"></span></dd> <dd>(also <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\text{2B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\text{2B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/42df4d39055471f4a7e14ee5aac8224b4275ba69" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.947ex; height:2.843ex;" alt="{\displaystyle R_{\text{2B}}(y)}"></span> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\text{1A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\text{1A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/37761811653d05232f522bc1e032aa414767823e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.19ex; height:2.843ex;" alt="{\displaystyle R_{\text{1A}}(x)}"></span> is possible)</dd></dl> <p><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> holds a read-lock on x and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> holds read-locks on y. Thus <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{\text{1B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{\text{1B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/443d1246bf450b6c658666e056a08d70857f5684" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.376ex; height:2.843ex;" alt="{\displaystyle W_{\text{1B}}(y)}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W_{\text{2A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle W_{\text{2A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec17fa4cfd3a886ad454ad6a775a63d7ad17eee7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.619ex; height:2.843ex;" alt="{\displaystyle W_{\text{2A}}(x)}"></span> are blocked by the <a href="/wiki/Two-phase_locking#Data-access_locks" title="Two-phase locking">lock compatibility</a> rules of SS2PL and cannot be executed. This is a distributed deadlock situation, which is also a voting-deadlock (see below) with a distributed (global) cycle of length 2 (number of edges, conflicts; 2 is the most frequent length). The local sub-transactions are in the following states: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{1A}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{1A}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e941376924175ae288d8e313f530771ded6174b3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.644ex; height:2.509ex;" alt="{\displaystyle T_{\text{1A}}}"></span> is <i>ready</i> (execution has ended) and <i>voted</i> (in atomic commitment)</dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{1B}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1B</mtext> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{1B}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/de74930a1af35473d4e8b4907e7106766f4bef1c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.575ex; height:2.509ex;" alt="{\displaystyle T_{\text{1B}}}"></span> is <i>running</i> and blocked (a non-materialized conflict situation; no vote on it can occur)</dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{2B}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{2B}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0bd044635ea82ce87c1b596833e910569689aa03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.575ex; height:2.509ex;" alt="{\displaystyle T_{\text{2B}}}"></span> is <i>ready</i> and <i>voted</i></dd> <dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{2A}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2A</mtext> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{2A}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3ee42ad394d84dbcd0315442762931d4025e0f51" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.644ex; height:2.509ex;" alt="{\displaystyle T_{\text{2A}}}"></span> is <i>running</i> and blocked (a non-materialized conflict; no vote).</dd></dl> <p>Since the atomic commitment protocol cannot receive votes for blocked sub-transactions (a voting-deadlock), it will eventually abort some transaction with a missing vote(s) by <a href="/wiki/Timeout_(computing)" title="Timeout (computing)">timeout</a>, either <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span>, or <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span>, (or both, if the timeouts fall very close). This will resolve the global deadlock. The remaining transaction will complete running, be voted on, and committed. An aborted transaction is immediately <i>restarted</i> and re-executed. </p> <div class="mw-heading mw-heading5"><h5 id="Comments">Comments</h5><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=18" title="Edit section: Comments"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ol><li>The data partition (x on A; y on B) is important since without it, for example, x can be accessed directly from B. If a transaction <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{3}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{3}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ac0936b6ba76bf0d900bb7315c99f64c5376f5ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{3}}"></span> is running on B concurrently with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> and directly writes x, then, without a distributed lock manager the read-lock for x held by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> on A is not visible on B and cannot block the write of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{3}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{3}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ac0936b6ba76bf0d900bb7315c99f64c5376f5ed" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{3}}"></span> (or signal a materialized conflict for a non-blocking CO variant; see below). Thus serializability can be violated.</li> <li>Due to data partition, x cannot be accessed directly from B. However, functionality is not limited, and a transaction running on B still can issue a write or read request of x (not common). This request is communicated to the transaction's local sub-transaction on A (which is generated, if does not exist already) which issues this request to the local data manager on A.</li></ol> <div class="mw-heading mw-heading4"><h4 id="Variations">Variations</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=19" title="Edit section: Variations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the scenario above both conflicts are <i>non-materialized</i>, and the global voting-deadlock is reflected as a cycle in the global <i>wait-for graph</i> (but not in the global <i>conflict graph</i>; see <a class="mw-selflink-fragment" href="#Exact_characterization_of_voting-deadlocks_by_global_cycles">Exact characterization of voting-deadlocks by global cycles</a> above). However the database system can utilize any CO variant with exactly the same conflicts and voting-deadlock situation, and same resolution. Conflicts can be either <i>materialized</i> or <i>non-materialized</i>, depending on CO variant used. For example, if <a class="mw-selflink-fragment" href="#Strict_CO_(SCO)">SCO</a> (below) is used by the distributed database system instead of SS2PL, then the two conflicts in the example are <i>materialized</i>, all local sub-transactions are in <i>ready</i> states, and vote blocking occurs in the two transactions, one on each node, because of the CO voting rule applied independently on both A and B: due to conflicts <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2A</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cf6d10fc3c5ea83c70eacdfdcad8267323c8e421" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.362ex; height:2.843ex;" alt="{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}"></span> is not voted on before <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/36a6f9af0af124dcaf6dc1a7a0e037520663a67b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.933ex; height:2.843ex;" alt="{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}"></span> ends, and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1B</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6edd8dbe82a9915e2afc3fa0cfd1336edb58711c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.05ex; height:2.843ex;" alt="{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}"></span> is not voted on before <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4cd8e6837840b169bf6587850bb9c7c38c5d8f48" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.62ex; height:2.843ex;" alt="{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}"></span> ends, which is a voting-deadlock. Now the <i>conflict graph</i> has the global cycle (all conflicts are materialized), and again it is resolved by the atomic commitment protocol, and distributed serializability is maintained. Unlikely for a distributed database system, but possible in principle (and occurs in a multi-database), A can employ SS2PL while B employs SCO. In this case the global cycle is neither in the wait-for graph nor in the serializability graph, but still in the <i>augmented conflict graph</i> (the union of the two). The various combinations are summarized in the following table: </p> <table class="wikitable" style="text-align:center;"> <caption>Voting-deadlock situations </caption> <tbody><tr> <th>Case</th> <th>Node<br />A</th> <th>Node<br />B</th> <th>Possible schedule</th> <th>Materialized<br />conflicts<br />on cycle</th> <th>Non-<br />materialized<br />conflicts</th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/36a6f9af0af124dcaf6dc1a7a0e037520663a67b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.933ex; height:2.843ex;" alt="{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1B</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6edd8dbe82a9915e2afc3fa0cfd1336edb58711c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.05ex; height:2.843ex;" alt="{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2A</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cf6d10fc3c5ea83c70eacdfdcad8267323c8e421" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.362ex; height:2.843ex;" alt="{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)}"></span></th> <th><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo>=</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4cd8e6837840b169bf6587850bb9c7c38c5d8f48" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.62ex; height:2.843ex;" alt="{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)}"></span> </th></tr> <tr> <th>1 </th> <td>SS2PL</td> <td>SS2PL</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b2ac214ea8b345613b7d65c203decf24206ae5fe" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.136ex; height:2.843ex;" alt="{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)}"></span></td> <td>0</td> <td>2</td> <td>Ready<br />Voted</td> <td>Running<br />(Blocked)</td> <td>Running<br />(Blocked)</td> <td>Ready<br />Voted </td></tr> <tr> <th>2 </th> <td>SS2PL</td> <td>SCO</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/99272b83290b9e6fda23c6be3c587a04f55107bc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.513ex; height:2.843ex;" alt="{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)}"></span></td> <td>1</td> <td>1</td> <td>Ready<br />Voted</td> <td>Ready<br />Vote blocked</td> <td>Running<br />(Blocked)</td> <td>Ready<br />Voted </td></tr> <tr> <th>3 </th> <td>SCO</td> <td>SS2PL</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{2A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{2A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2afa077f81b23adc03f22fea6a98fb6f701327d7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.756ex; height:2.843ex;" alt="{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{2A}}(x)}"></span></td> <td>1</td> <td>1</td> <td>Ready<br />Voted</td> <td>Running<br />(Blocked)</td> <td>Ready<br />Vote blocked</td> <td>Ready<br />Voted </td></tr> <tr> <th>4 </th> <td>SCO</td> <td>SCO</td> <td><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)W_{\text{2A}}(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <msub> <mi>R</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>1B</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>y</mi> <mo stretchy="false">)</mo> <msub> <mi>W</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext>2A</mtext> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)W_{\text{2A}}(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/67c300f35ced7cdaadbb371acfc6af7f85ecf0cf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.132ex; height:2.843ex;" alt="{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)W_{\text{2A}}(x)}"></span></td> <td>2</td> <td>0</td> <td>Ready<br />Voted</td> <td>Ready<br />Vote blocked</td> <td>Ready<br />Vote blocked</td> <td>Ready<br />Voted </td></tr></tbody></table> <dl><dd><b>Comments:</b></dd></dl> <ol><li>Conflicts and thus cycles in the <i>augmented conflict graph</i> are determined by the transactions and their initial scheduling only, independently of the concurrency control utilized. With any variant of CO, any <i>global cycle</i> (i.e., spans two databases or more) causes a <i>voting deadlock</i>. Different CO variants may differ on whether a certain conflict is <i>materialized</i> or <i>non-materialized</i>.</li> <li>Some limited operation order changes in the schedules above are possible, constrained by the orders inside the transactions, but such changes do not change the rest of the table.</li> <li>As noted above, only case 4 describes a cycle in the (regular) conflict graph which affects serializability. Cases 1-3 describe cycles of locking based global deadlocks (at least one lock blocking exists). All cycle types are equally resolved by the atomic commitment protocol. Case 1 is the common Distributed SS2PL, utilized since the 1980s. However, no research article, except the CO articles, is known to notice this automatic locking global deadlock resolution as of 2009. Such global deadlocks typically have been dealt with by dedicated mechanisms.</li> <li>Case 4 above is also an example for a typical voting-deadlock when <a class="mw-selflink-fragment" href="#Distributed_optimistic_CO_(DOCO)">Distributed optimistic CO (DOCO)</a> is used (i.e., Case 4 is unchanged when Optimistic CO (OCO; see below) replaces SCO on both A and B): No data-access blocking occurs, and only materialized conflicts exist.</li></ol> <div class="mw-heading mw-heading4"><h4 id="Hypothetical_Multi_Single-Threaded_Core_(MuSiC)_environment"><span id="Hypothetical_Multi_Single-Threaded_Core_.28MuSiC.29_environment"></span>Hypothetical Multi Single-Threaded Core (MuSiC) environment</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=20" title="Edit section: Hypothetical Multi Single-Threaded Core (MuSiC) environment"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Comment:</b> While the examples above describe real, recommended utilization of CO, this example is hypothetical, for demonstration only. </p><p>Certain experimental distributed memory-resident databases advocate multi single-threaded core (MuSiC) transactional environments. "Single-threaded" refers to transaction <a href="/wiki/Thread_(computer_science)" class="mw-redirect" title="Thread (computer science)">threads</a> only, and to <i>serial</i> execution of transactions. The purpose is possible orders of magnitude gain in performance (e.g., <a href="/wiki/Michael_Stonebraker#H-Store_and_VoltDB" title="Michael Stonebraker">H-Store</a><sup id="cite_ref-Stone08_6-0" class="reference"><a href="#cite_note-Stone08-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> and <a href="/wiki/VoltDB" title="VoltDB">VoltDB</a>) relatively to conventional transaction execution in multiple threads on a same core. In what described below MuSiC is independent of the way the cores are distributed. They may reside in one <a href="/wiki/Integrated_circuit" title="Integrated circuit">integrated circuit</a> (chip), or in many chips, possibly distributed geographically in many computers. In such an environment, if recoverable (transactional) data are partitioned among threads (cores), and it is implemented in the conventional way for distributed CO, as described in previous sections, then DOCO and Strictness exist automatically. However, downsides exist with this straightforward implementation of such environment, and its practicality as a general-purpose solution is questionable. On the other hand, tremendous performance gain can be achieved in applications that can bypass these downsides in most situations. </p><p><b>Comment:</b> The MuSiC straightforward implementation described here (which uses, for example, as usual in distributed CO, voting (and transaction thread) blocking in atomic commitment protocol when needed) is for demonstration only, and has <b>no connection</b> to the implementation in H-Store or any other project. </p><p>In a MuSiC environment local schedules are <i>serial</i>. Thus both local Optimistic CO (OCO; see below) and the <i>Global CO enforcement vote ordering strategy</i> condition for the atomic commitment protocol are met automatically. This results in both distributed CO compliance (and thus distributed serializability) and automatic global (voting) deadlock resolution. </p><p>Furthermore, also local <i>Strictness</i> follows automatically in a serial schedule. By Theorem 5.2 in (<a href="#Raz1992">Raz 1992</a>; page 307), when the CO vote ordering strategy is applied, also Global Strictness is guaranteed. Note that <i>serial</i> locally is the only mode that allows strictness and "optimistic" (no data access blocking) together. </p><p>The following is concluded: </p> <ul><li><b>The MuSiC Theorem</b></li></ul> <dl><dd>In MuSiC environments, if recoverable (transactional) data are partitioned among cores (threads), then both <ol><li><i>OCO</i> (and implied <i>Serializability</i>; i.e., DOCO and Distributed serializability)</li> <li><i>Strictness</i> (allowing effective recovery; 1 and 2 implying Strict CO—see SCO below) and</li> <li>(voting) <i>deadlock resolution</i></li></ol></dd> <dd>automatically exist globally with unbounded scalability in number of cores used.</dd></dl> <dl><dd><b>Comment:</b> However, two major downsides, which need special handling, may exist:</dd></dl> <ol><li>Local sub-transactions of a global transaction are blocked until commit, which makes the respective cores idle. This reduces core utilization substantially, even if scheduling of the local sub-transactions attempts to execute all of them in time proximity, almost together. It can be overcome by detaching execution from commit (with some atomic commitment protocol) for global transactions, at the cost of possible cascading aborts.</li> <li>increasing the number of cores for a given amount of recoverable data (database size) decreases the average amount of (partitioned) data per core. This may make some cores idle, while others very busy, depending on data utilization distribution. Also a local (to a core) transaction may become global (multi-core) to reach its needed data, with additional incurred overhead. Thus, as the number of cores increases, the amount and type of data assigned to each core should be balanced according to data usage, so a core is neither overwhelmed to become a bottleneck, nor becoming idle too frequently and underutilized in a busy system. Another consideration is putting in a same core partition all the data that are usually accessed by a same transaction (if possible), to maximize the number of local transactions (and minimize the number of global, distributed transactions). This may be achieved by occasional data re-partition among cores based on load balancing (data access balancing) and patterns of data usage by transactions. Another way to considerably mitigate this downside is by proper physical data replication among some core partitions in a way that read-only global transactions are possibly (depending on usage patterns) completely avoided, and replication changes are synchronized by a dedicated commit mechanism.</li></ol> <div class="mw-heading mw-heading2"><h2 id="CO_variants:_special_cases_and_generalizations">CO variants: special cases and generalizations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=21" title="Edit section: CO variants: special cases and generalizations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Special case schedule property classes (e.g., SS2PL and SCO below) are strictly contained in the CO class. The generalizing classes (ECO and MVCO) strictly contain the CO class (i.e., include also schedules that are not CO compliant). The generalizing variants also guarantee global serializability without distributing local concurrency control information (each database has the <i>generalized autonomy</i> property: it uses only local information), while relaxing CO constraints and utilizing additional (local) information for better concurrency and performance: ECO uses knowledge about transactions being local (i.e., confined to a single database), and MVCO uses availability of data versions values. Like CO, both generalizing variants are <i>non-blocking</i>, do not interfere with any transaction's operation scheduling, and can be seamlessly combined with any relevant concurrency control mechanism. </p><p>The term <b>CO variant</b> refers in general to CO, ECO, MVCO, or a combination of each of them with any relevant concurrency control mechanism or property (including Multi-version based ECO, MVECO). No other generalizing variants (which guarantee global serializability with no local concurrency control information distribution) are known, but may be discovered. </p> <div class="mw-heading mw-heading3"><h3 id="Strong_strict_two_phase_locking_(SS2PL)"><span id="Strong_strict_two_phase_locking_.28SS2PL.29"></span>Strong strict two phase locking (SS2PL)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=22" title="Edit section: Strong strict two phase locking (SS2PL)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Two-phase_locking" title="Two-phase locking">Two-phase locking</a></div> <p><b>Strong Strict Two Phase Locking</b> (SS2PL; also referred to as <i>Rigorousness</i> or <i>Rigorous scheduling</i>) means that both read and write locks of a transaction are released only after the transaction has ended (either committed or aborted). The set of SS2PL schedules is a <a href="/wiki/Proper_subset" class="mw-redirect" title="Proper subset">proper subset</a> of the set of CO schedules. This property is widely utilized in database systems, and since it implies CO, databases that use it and participate in global transactions generate together a serializable global schedule (when using any atomic commitment protocol, which is needed for atomicity in a multi-database environment). No database modification or addition is needed in this case to participate in a CO distributed solution: The set of undecided transactions to be aborted before committing in the <a class="mw-selflink-fragment" href="#The_algorithm">local generic CO algorithm</a> above is empty because of the locks, and hence such an algorithm is unnecessary in this case. A transaction can be voted on by a database system immediately after entering a "ready" state, i.e., completing running its task locally. Its locks are released by the database system only after it is decided by the atomic commitment protocol, and thus the condition in the <i>Global CO enforcing theorem</i> above is kept automatically. If a local timeout mechanism is used by a database system to resolve (local) SS2PL deadlocks, then aborting blocked transactions breaks not only potential local cycles in the global conflict graph (real cycles in the augmented conflict graph), but also database system's potential global cycles as a side effect, if the <a href="/w/index.php?title=Atomic_commitment&action=edit&redlink=1" class="new" title="Atomic commitment (page does not exist)">atomic commitment</a> protocol's abort mechanism is relatively slow. Such independent aborts by several entities typically may result in unnecessary aborts for more than one transaction per global cycle. The situation is different for a local <i>wait-for graph</i> based mechanisms: Such cannot identify global cycles, and the atomic commitment protocol will break the global cycle, if the resulting voting deadlock is not resolved earlier in another database. </p><p>Local SS2PL together with atomic commitment implying global serializability can also be deduced directly: All transactions, including distributed, obey the <a href="/wiki/Two-phase_locking" title="Two-phase locking">2PL</a> (SS2PL) rules. The atomic commitment protocol mechanism is not needed here for consensus on commit, but rather for the end of phase-two synchronization point. Probably for this reason, without considering the atomic commitment voting mechanism, automatic global deadlock resolution has not been noticed before CO. </p> <div class="mw-heading mw-heading3"><h3 id="Strict_CO_(SCO)"><span id="Strict_CO_.28SCO.29"></span>Strict CO (SCO)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=23" title="Edit section: Strict CO (SCO)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:SCO-VS-SS2PL.jpg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/en/thumb/0/0c/SCO-VS-SS2PL.jpg/450px-SCO-VS-SS2PL.jpg" decoding="async" width="450" height="322" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/0/0c/SCO-VS-SS2PL.jpg/675px-SCO-VS-SS2PL.jpg 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/0/0c/SCO-VS-SS2PL.jpg/900px-SCO-VS-SS2PL.jpg 2x" data-file-width="1124" data-file-height="804" /></a><figcaption><b>Read-write conflict: SCO Vs. SS2PL</b>. Duration of transaction T2 is longer with SS2PL than with SCO. SS2PL delays write operation w2[x] of T2 until T1 commits, due to a lock on x by T1 following read operation r1[x]. If t time units are needed for transaction T2 after starting write operation w2[x] in order to reach ready state, than T2 commits t time units after T1 commits. However, SCO does not block w2[x], and T2 can commit immediately after T1 commits. (<a href="#Raz1991c">Raz 1991c</a>)</figcaption></figure> <p><b>Strict Commitment Ordering</b> (SCO; (<a href="#Raz1991c">Raz 1991c</a>)) is the intersection of <a href="/wiki/Database_transaction_schedule#Strict" title="Database transaction schedule">strictness</a> (a special case of recoverability) and CO, and provides an upper bound for a schedule's concurrency when both properties exist. It can be implemented using blocking mechanisms (locking) similar to those used for the popular SS2PL with similar overheads. </p><p>Unlike SS2PL, SCO does not block on a read-write conflict but possibly blocks on commit instead. SCO and SS2PL have identical blocking behavior for the other two conflict types: write-read, and write-write. As a result, SCO has shorter average blocking periods, and more concurrency (e.g., performance simulations of a single database for the most significant variant of <i><a href="/wiki/Locks_with_ordered_sharing" title="Locks with ordered sharing">locks with ordered sharing</a>,</i> which is identical to SCO, clearly show this, with approximately 100% gain for some transaction loads; also for identical transaction loads SCO can reach higher transaction rates than SS2PL before <i>lock <a href="/wiki/Thrashing_(computer_science)" title="Thrashing (computer science)">thrashing</a></i> occurs). More concurrency means that with given computing resources more transactions are completed in time unit (higher transaction rate, <a href="/wiki/Throughput" class="mw-redirect" title="Throughput">throughput</a>), and the average duration of a transaction is shorter (faster completion; see chart). The advantage of SCO is especially significant during lock contention. </p> <ul><li><b>The SCO Vs. SS2PL Performance Theorem</b></li></ul> <dl><dd>SCO provides shorter average transaction completion time than SS2PL, if read-write conflicts exist. SCO and SS2PL are identical otherwise (have identical blocking behavior with write-read and write-write conflicts).</dd></dl> <p>SCO is as practical as SS2PL since as SS2PL it provides besides serializability also strictness, which is widely utilized as a basis for efficient recovery of databases from failure. An SS2PL mechanism can be converted to an SCO one for better performance in a straightforward way without changing recovery methods. A description of an SCO implementation can be found in (Perrizo and Tatarinov 1998).<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> See also <i><a href="/w/index.php?title=The_History_of_Commitment_Ordering&action=edit&redlink=1" class="new" title="The History of Commitment Ordering (page does not exist)">Semi-optimistic database scheduler</a></i>. </p><p>SS2PL is a proper subset of SCO (which is another explanation why SCO is less constraining and provides more concurrency than SS2PL). </p> <div class="mw-heading mw-heading3"><h3 id="Optimistic_CO_(OCO)"><span id="Optimistic_CO_.28OCO.29"></span>Optimistic CO (OCO)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=24" title="Edit section: Optimistic CO (OCO)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For implementing <b>Optimistic commitment ordering</b> (OCO) the generic local CO algorithm is utilized without data access blocking, and thus without local deadlocks. OCO without transaction or operation scheduling constraints covers the entire CO class, and is not a special case of the CO class, but rather a useful CO variant and mechanism characterization. </p> <div class="mw-heading mw-heading3"><h3 id="Extended_CO_(ECO)"><span id="Extended_CO_.28ECO.29"></span>Extended CO (ECO)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=25" title="Edit section: Extended CO (ECO)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading4"><h4 id="General_characterization_of_ECO">General characterization of ECO</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=26" title="Edit section: General characterization of ECO"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Extended Commitment Ordering</b> (ECO; (<a href="#Raz1993a">Raz 1993a</a>)) generalizes CO. When local transactions (transactions confined to a single database) can be distinguished from global (distributed) transactions (transactions that span two databases or more), commitment order is applied to global transactions only. Thus, for a local (to a database) schedule to have the ECO property, the chronological (partial) order of commit events of global transactions only (unimportant for local transactions) is consistent with their order on the respective local conflict graph. </p> <ul><li><b>Definition: extended commitment ordering</b></li></ul> <dl><dd>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1},T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1},T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a0e6aef110538dac610120d6a38a5e5618810d12" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.858ex; height:2.509ex;" alt="{\displaystyle T_{1},T_{2}}"></span> be two committed <i>global</i> transactions in a schedule, such that a <i>directed path</i> of unaborted transactions exists in the <i>conflict graph</i> (<a href="/wiki/Precedence_graph" title="Precedence graph">precedence graph</a>) from <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> (<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> precedes <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span>, possibly <a href="/wiki/Transitive_relation" title="Transitive relation">transitively</a>, indirectly). The schedule has the <b>Extended commitment ordering</b> (ECO) property, if for every two such transactions <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> commits before <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> commits.</dd></dl> <p>A distributed algorithm to guarantee global ECO exists. As for CO, the algorithm needs only (unmodified) atomic commitment protocol messages. In order to guarantee global serializability, each database needs to guarantee also the conflict serializability of its own transactions by any (local) concurrency control mechanism. </p> <ul><li><b>The ECO and Global Serializability Theorem</b></li></ul> <ol><li>(Local, which implies global) ECO together with local conflict serializability, is a sufficient condition to guarantee global conflict serializability.</li> <li>When no concurrency control information beyond atomic commitment messages is shared outside a database (autonomy), and local transactions can be identified, it is also a necessary condition.</li></ol> <dl><dd>See a necessity proof in (<a href="#Raz1993a">Raz 1993a</a>).</dd></dl> <p>This condition (ECO with local serializability) is weaker than CO, and allows more concurrency at the cost of a little more complicated local algorithm (however, no practical overhead difference with CO exists). </p><p>When all the transactions are assumed to be global (e.g., if no information is available about transactions being local), ECO reduces to CO. </p> <div class="mw-heading mw-heading4"><h4 id="The_ECO_algorithm">The ECO algorithm</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=27" title="Edit section: The ECO algorithm"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Before a global transaction is committed, a generic local (to a database) ECO algorithm aborts a minimal set of undecided transactions (neither committed, nor aborted; either local transactions, or global that run locally), that can cause later a cycle in the conflict graph. This set of aborted transactions (not unique, contrary to CO) can be optimized, if each transaction is assigned with a weight (that can be determined by transaction's importance and by the computing resources already invested in the running transaction; optimization can be carried out, for example, by a reduction from the <i><a href="/wiki/Max_flow_in_networks" class="mw-redirect" title="Max flow in networks">Max flow in networks</a></i> problem (<a href="#Raz1993a">Raz 1993a</a>)). Like for CO such a set is time dependent, and becomes empty eventually. Practically, almost in all needed implementations a transaction should be committed only when the set is empty (and no set optimization is applicable). The local (to the database) concurrency control mechanism (separate from the ECO algorithm) ensures that local cycles are eliminated (unlike with CO, which implies serializability by itself; however, practically also for CO a local concurrency mechanism is utilized, at least to ensure Recoverability). Local transactions can be always committed concurrently (even if a precedence relation exists, unlike CO). When the overall transactions' local partial order (which is determined by the local conflict graph, now only with possible temporary local cycles, since cycles are eliminated by a local serializability mechanism) allows, also global transactions can be voted on to be committed concurrently (when all their transitively (indirect) preceding (via conflict) <i>global</i> transactions are committed, while transitively preceding local transactions can be at any state. This in analogy to the distributed CO algorithm's stronger concurrent voting condition, where all the transitively preceding transactions need to be committed). </p><p>The condition for guaranteeing <i>Global ECO</i> can be summarized similarly to CO: </p> <ul><li><b>The Global ECO Enforcing Vote ordering strategy Theorem</b></li></ul> <dl><dd>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1},T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1},T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a0e6aef110538dac610120d6a38a5e5618810d12" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.858ex; height:2.509ex;" alt="{\displaystyle T_{1},T_{2}}"></span> be undecided (neither committed nor aborted) <i>global transactions</i> in a database system that ensures serializability locally, such that a <i>directed path</i> of unaborted transactions exists in the <i>local conflict graph</i> (that of the database itself) from <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span>. Then, having <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f304724948a3ef606c4a92459e22b87a954d993" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{1}}"></span> ended (either committed or aborted) before <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>T</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d1ba5f12fbb0ff766aec6e22148b429373608555" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.412ex; height:2.509ex;" alt="{\displaystyle T_{2}}"></span> is voted on to be committed, in every such database system in a multidatabase environment, is a <a href="/wiki/Necessary_and_sufficient_condition" class="mw-redirect" title="Necessary and sufficient condition">necessary and sufficient condition</a> for guaranteeing Global ECO (the condition guarantees Global ECO, which may be violated without it).</dd></dl> <p>Global ECO (all global cycles in the global conflict graph are eliminated by atomic commitment) together with Local serializability (i.e., each database system maintains serializability locally; all local cycles are eliminated) imply Global serializability (all cycles are eliminated). This means that if each database system in a multidatabase environment provides local serializability (by <i>any</i> mechanism) and enforces the <i>vote ordering strategy</i> in the theorem above (a generalization of CO's vote ordering strategy), then <i>Global serializability</i> is guaranteed (no local CO is needed anymore). </p><p>Similarly to CO as well, the ECO <i>voting-deadlock</i> situation can be summarized as follows: </p> <ul><li><b>The ECO Voting-Deadlock Theorem</b></li></ul> <dl><dd>Let a multidatabase environment comprise database systems that enforce, each, both <i>Global ECO</i> (using the condition in the theorem above) and <i>local conflict serializability</i> (which eliminates local cycles in the global conflict graph). Then, a <i>voting-deadlock</i> occurs if and only if a <i>global cycle</i> (spans two or more databases) exists in the <i>Global augmented conflict graph</i> (also blocking by a data-access lock is represented by an edge). If the cycle does not break by any abort, then all the <i>global transactions</i> on it are involved with the respective voting-deadlock, and eventually each has its vote blocked (either directly, or indirectly by a data-access lock). If a local transaction resides on the cycle, it may be in any unaborted state (running, ready, or committed; unlike CO no local commit blocking is needed).</dd></dl> <p>As with CO this means that also global deadlocks due to data-access locking (with at least one lock blocking) are voting deadlocks, and are automatically resolved by atomic commitment. </p> <div class="mw-heading mw-heading3"><h3 id="Multi-version_CO_(MVCO)"><span id="Multi-version_CO_.28MVCO.29"></span>Multi-version CO (MVCO)</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=28" title="Edit section: Multi-version CO (MVCO)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Multi-version Commitment Ordering</b> (MVCO; (<a href="#Raz1993b">Raz 1993b</a>)) is a generalization of CO for databases with <a href="/wiki/Multiversion_concurrency_control" title="Multiversion concurrency control">multi-version resources</a>. With such resources <i>read-only transactions</i> do not block or being blocked for better performance. Utilizing such resources is a common way nowadays to increase concurrency and performance by generating a new version of a database object each time the object is written, and allowing transactions' read operations of several last relevant versions (of each object). MVCO implies <i>One-copy-serializability</i> (1SER or 1SR) which is the generalization of <a href="/wiki/Serializability" class="mw-redirect" title="Serializability">serializability</a> for multi-version resources. Like CO, MVCO is non-blocking, and can be combined with any relevant multi-version concurrency control mechanism without interfering with it. In the introduced underlying theory for MVCO conflicts are generalized for different versions of a same resource (differently from earlier multi-version theories). For different versions conflict chronological order is replaced by version order, and possibly reversed, while keeping the usual definitions for conflicting operations. Results for the regular and augmented conflict graphs remain unchanged, and similarly to CO a distributed MVCO enforcing algorithm exists, now for a mixed environment with both single-version and multi-version resources (now single-version is a special case of multi-version). As for CO, the MVCO algorithm needs only (unmodified) <a href="/w/index.php?title=Atomic_commitment&action=edit&redlink=1" class="new" title="Atomic commitment (page does not exist)">atomic commitment</a> protocol messages with no additional communication overhead. Locking-based global deadlocks translate to voting deadlocks and are resolved automatically. In analogy to CO the following holds: </p> <ul><li><b>The MVCO and Global one-copy-serializability Theorem</b></li></ul> <ol><li>MVCO compliance of every <i>autonomous</i> database system (or transactional object) in a mixed multidatabase environment of single-version and multi-version databases is a <i>necessary condition</i> for guaranteeing Global one-copy-serializability (1SER).</li> <li>MVCO compliance of every database system is a <i>sufficient condition</i> for guaranteeing Global 1SER.</li> <li>Locking-based global deadlocks are resolved automatically.</li></ol> <dl><dd><b>Comment</b>: Now a CO compliant single-version database system is automatically also MVCO compliant.</dd></dl> <p>MVCO can be further generalized to employ the generalization of ECO (MVECO). </p> <div class="mw-heading mw-heading4"><h4 id="Example:_CO_based_snapshot_isolation_(COSI)"><span id="Example:_CO_based_snapshot_isolation_.28COSI.29"></span>Example: CO based snapshot isolation (COSI)</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=29" title="Edit section: Example: CO based snapshot isolation (COSI)"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>CO based snapshot isolation</b> (COSI) is the intersection of <i><a href="/wiki/Snapshot_isolation" title="Snapshot isolation">Snapshot isolation</a></i> (SI) with MVCO. SI is a <a href="/wiki/Multiversion_concurrency_control" title="Multiversion concurrency control">multiversion concurrency control</a> method widely utilized due to good performance and similarity to serializability (1SER) in several aspects. The theory in (Raz 1993b) for MVCO described above is utilized later in (Fekete et al. 2005) and other articles on SI, e.g., (Cahill et al. 2008);<sup id="cite_ref-Cahill08_8-0" class="reference"><a href="#cite_note-Cahill08-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> see also <a href="/wiki/Snapshot_isolation#Making_Snapshot_Isolation_Serializable" title="Snapshot isolation">Making snapshot isolation serializable</a> and the references there), for analyzing conflicts in SI in order to make it serializable. The method presented in (Cahill et al. 2008), <i>Serializable snapshot isolation</i> (SerializableSI), a low overhead modification of SI, provides good performance results versus SI, with only small penalty for enforcing serializability. A different method, by combining SI with MVCO (COSI), makes SI serializable as well, with a relatively low overhead, similarly to combining the generic CO algorithm with single-version mechanisms. Furthermore, the resulting combination, COSI, being MVCO compliant, allows COSI compliant database systems to inter-operate and transparently participate in a CO solution for distributed/global serializability (see below). Besides overheads also protocols' behaviors need to be compared quantitatively. On one hand, all serializable SI schedules can be made MVCO by COSI (by possible commit delays when needed) without aborting transactions. On the other hand, SerializableSI is known to unnecessarily abort and restart certain percentages of transactions also in serializable SI schedules. </p> <div class="mw-heading mw-heading3"><h3 id="CO_and_its_variants_are_transparently_interoperable_for_global_serializability">CO and its variants are transparently interoperable for global serializability</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=30" title="Edit section: CO and its variants are transparently interoperable for global serializability"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>With CO and its variants (e.g., SS2PL, SCO, OCO, ECO, and MVCO above) global serializability is achieved via <i>atomic commitment</i> protocol based distributed algorithms. For CO and all its variants atomic commitment protocol is the instrument to eliminate global cycles (cycles that span two or more databases) in the <i>global augmented</i> (and thus also regular) <i>conflict graph</i> (implicitly; no global data structure implementation is needed). In cases of either incompatible local commitment orders in two or more databases (when no global <a href="/wiki/Partial_order" class="mw-redirect" title="Partial order">partial order</a> can <a href="/wiki/Embedding" title="Embedding">embed</a> the respective local partial orders together), or a data-access locking related voting deadlock, both implying a global cycle in the global augmented conflict graph and missing votes, the atomic commitment protocol breaks such cycle by aborting an undecided transaction on it (see <a class="mw-selflink-fragment" href="#The_distributed_CO_algorithm">The distributed CO algorithm</a> above). Differences between the various variants exist at the local level only (within the participating database systems). Each local CO instance of any variant has the same role, to determine the position of every global transaction (a transaction that spans two or more databases) within the local commitment order, i.e., to determine when it is the transaction's turn to be voted on locally in the atomic commitment protocol. Thus, all the CO variants exhibit the same behavior in regard to atomic commitment. This means that they are all interoperable via atomic commitment (using the same software interfaces, typically provided as <a href="/wiki/Service_(systems_architecture)" title="Service (systems architecture)">services</a>, some already <a href="/wiki/International_standard" title="International standard">standardized</a> for atomic commitment, primarily for the <a href="/wiki/Two_phase_commit" class="mw-redirect" title="Two phase commit">two phase commit</a> protocol, e.g., <a href="/wiki/X/Open_XA" title="X/Open XA">X/Open XA</a>) and transparently can be utilized together in any distributed environment (while each CO variant instance is possibly associated with any relevant local concurrency control mechanism type). </p><p>In summary, any single global transaction can participate simultaneously in databases that may employ each any, possibly different, CO variant (while concurrently running processes in each such database, and running concurrently with local and other global transactions in each such database). The atomic commitment protocol is indifferent to CO, and does not distinguish between the various CO variants. Any <i>global cycle</i> generated in the augmented global conflict graph may span databases of different CO variants, and generate (if not broken by any local abort) a voting deadlock that is resolved by atomic commitment exactly the same way as in a single CO variant environment. <i>local cycles</i> (now possibly with mixed materialized and non-materialized conflicts, both serializability and data-access-locking deadlock related, e.g., SCO) are resolved locally (each by its respective variant instance's own local mechanisms). </p><p><b>Vote ordering</b> (VO or Generalized CO (GCO); <a href="#Raz2009">Raz 2009</a>), the union of CO and all its above variants, is a useful concept and global serializability technique. To comply with VO, local serializability (in it most general form, commutativity based, and including multi-versioning) and the <i>vote order strategy</i> (voting by local precedence order) are needed. </p><p>Combining results for CO and its variants, the following is concluded: </p> <ul><li><b>The CO Variants Interoperability Theorem</b></li></ul> <ol><li>In a multi-database environment, where each database system (transactional object) is compliant with some CO variant property (VO compliant), any global transaction can participate simultaneously in databases of possibly different CO variants, and Global serializability is guaranteed (<i>sufficient condition</i> for Global serializability; and Global one-copy-serializability (1SER), for a case when a multi-version database exists).</li> <li>If only local (to a database system) concurrency control information is utilized by every database system (each has the <i>generalized autonomy</i> property, a generalization of <i>autonomy</i>), then compliance of each with some (any) CO variant property (VO compliance) is a <i>necessary condition</i> for guaranteeing Global serializability (and Global 1SER; otherwise they may be violated).</li> <li>Furthermore, in such environment data-access-locking related global deadlocks are resolved automatically (each such deadlock is generated by a global cycle in the <i>augmented conflict graph</i> (i.e., a <i>voting deadlock</i>; see above), involving at least one data-access lock (non-materialized conflict) and two database systems; thus, not a cycle in the regular conflict graph and does not affect serializability).</li></ol> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=31" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFRaz1992" class="citation cs2">Raz, Yoav (August 1992), <a rel="nofollow" class="external text" href="http://www.vldb.org/conf/1992/P292.PDF">"The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment"</a> <span class="cs1-format">(PDF)</span>, <i>Proceedings of the Eighteenth International Conference on Very Large Data Bases</i>, Vancouver, Canada, pp. <span class="nowrap">292–</span>312</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+Eighteenth+International+Conference+on+Very+Large+Data+Bases&rft.atitle=The+Principle+of+Commitment+Ordering%2C+or+Guaranteeing+Serializability+in+a+Heterogeneous+Environment+of+Multiple+Autonomous+Resource+Managers+Using+Atomic+Commitment&rft.pages=%3Cspan+class%3D%22nowrap%22%3E292-%3C%2Fspan%3E312&rft.date=1992-08&rft.aulast=Raz&rft.aufirst=Yoav&rft_id=http%3A%2F%2Fwww.vldb.org%2Fconf%2F1992%2FP292.PDF&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACommitment+ordering" class="Z3988"></span> (also DEC-TR 841, <a href="/wiki/Digital_Equipment_Corporation" title="Digital Equipment Corporation">Digital Equipment Corporation</a>, November 1990)</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRaz1994" class="citation cs2">Raz, Yoav (September 1994), "Serializability by Commitment Ordering", <i>Information Processing Letters</i>, <b>51</b> (5): <span class="nowrap">257–</span>264, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0020-0190%2894%2990005-1">10.1016/0020-0190(94)90005-1</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Information+Processing+Letters&rft.atitle=Serializability+by+Commitment+Ordering&rft.volume=51&rft.issue=5&rft.pages=%3Cspan+class%3D%22nowrap%22%3E257-%3C%2Fspan%3E264&rft.date=1994-09&rft_id=info%3Adoi%2F10.1016%2F0020-0190%2894%2990005-1&rft.aulast=Raz&rft.aufirst=Yoav&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACommitment+ordering" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRaz2009" class="citation cs2">Raz, Yoav (June 2009), <a rel="nofollow" class="external text" href="https://sites.google.com/site/yoavraz2/home/theory-of-commitment-ordering"><i>Theory of Commitment Ordering: Summary</i></a><span class="reference-accessdate">, retrieved <span class="nowrap">November 11,</span> 2011</span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Theory+of+Commitment+Ordering%3A+Summary&rft.date=2009-06&rft.aulast=Raz&rft.aufirst=Yoav&rft_id=http%3A%2F%2Fsites.google.com%2Fsite%2Fyoavraz2%2Fhome%2Ftheory-of-commitment-ordering&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACommitment+ordering" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFRaz1990" class="citation cs2">Raz, Yoav (November 1990), <a rel="nofollow" class="external text" href="http://yoavraz.googlepages.com/DEC-CO-MEMO-90-11-16.pdf"><i>On the Significance of Commitment Ordering</i></a> <span class="cs1-format">(PDF)</span>, Digital Equipment Corporation</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=On+the+Significance+of+Commitment+Ordering&rft.pub=Digital+Equipment+Corporation&rft.date=1990-11&rft.aulast=Raz&rft.aufirst=Yoav&rft_id=http%3A%2F%2Fyoavraz.googlepages.com%2FDEC-CO-MEMO-90-11-16.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACommitment+ordering" class="Z3988"></span></li> <li><cite id="Raz1991a">Yoav Raz (1991a): US patents <a rel="nofollow" class="external text" href="http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=3&f=G&l=50&co1=AND&d=PTXT&s1=%22commitment+ordering%22.TI.&OS=TTL/">5,504,899 (ECO)</a> <a rel="nofollow" class="external text" href="http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=2&f=G&l=50&co1=AND&d=PTXT&s1=%22commitment+ordering%22.TI.&OS=TTL/">5,504,900 (CO)</a> <a rel="nofollow" class="external text" href="http://patft1.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=1&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=1&f=G&l=50&co1=AND&d=PTXT&s1=%22commitment+ordering%22.TI.&OS=TTL/">5,701,480 (MVCO)</a> </cite></li> <li><cite id="Raz1991b">Yoav Raz (1991b): "The Commitment Order Coordinator (COCO) of a Resource Manager, or Architecture for Distributed Commitment Ordering Based Concurrency Control", DEC-TR 843, Digital Equipment Corporation, December 1991. </cite></li> <li><cite id="Raz1991c">Yoav Raz (1991c): "Locking Based Strict Commitment Ordering, or How to improve Concurrency in Locking Based Resource Managers", DEC-TR 844, December 1991. </cite></li> <li><cite id="Raz1993a">Yoav Raz (1993a): <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=153858">"Extended Commitment Ordering or Guaranteeing Global Serializability by Applying Commitment Order Selectivity to Global Transactions."</a> <i>Proceedings of the Twelfth ACM Symposium on Principles of Database Systems</i> (PODS), Washington, DC, pp. 83-96, May 1993. (also DEC-TR 842, November 1991) </cite></li> <li><cite id="Raz1993b">Yoav Raz (1993b): <a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/281924/;jsessionid=8A55F00EAE1D0EA97F2C701C0F479BBA?arnumber=281924">"Commitment Ordering Based Distributed Concurrency Control for Bridging Single and Multi Version Resources."</a> <i>Proceedings of the Third IEEE International Workshop on Research Issues on Data Engineering: Interoperability in Multidatabase Systems</i> (RIDE-IMS), Vienna, Austria, pp. 189-198, April 1993. (also DEC-TR 853, July 1992) </cite></li></ul> <div class="mw-heading mw-heading2"><h2 id="Footnotes">Footnotes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=32" title="Edit section: Footnotes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-Fekete1988-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-Fekete1988_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Fekete1988_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Alan Fekete, <a href="/wiki/Nancy_Lynch" title="Nancy Lynch">Nancy Lynch</a>, Michael Merritt, William Weihl (1988): <a rel="nofollow" class="external text" href="https://web.archive.org/web/20121008112828/http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA200980&Location=U2&doc=GetTRDoc.pdf"><i>Commutativity-based locking for nested transactions</i> (PDF)</a> MIT, LCS lab, Technical report MIT/LCS/TM-370, August 1988.</span> </li> <li id="cite_note-Bern2009-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Bern2009_2-0">^</a></b></span> <span class="reference-text"><a href="/wiki/Phil_Bernstein" title="Phil Bernstein">Philip A. Bernstein</a>, Eric Newcomer (2009): <a rel="nofollow" class="external text" href="http://www.elsevierdirect.com/product.jsp?isbn=9781558606234"><i>Principles of Transaction Processing</i>, 2nd Edition</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20100807151625/http://www.elsevierdirect.com/product.jsp?isbn=9781558606234">Archived</a> 2010-08-07 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a>, Morgan Kaufmann (Elsevier), June 2009, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-55860-623-4" title="Special:BookSources/978-1-55860-623-4">978-1-55860-623-4</a> (pages 145, 360)</span> </li> <li id="cite_note-Zhang2006-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-Zhang2006_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Zhang2006_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Lingli Zhang, Vinod K.Grover, Michael M. Magruder, David Detlefs, John Joseph Duffy, Goetz Graefe (2006): <a rel="nofollow" class="external text" href="http://www.freepatentsonline.com/7711678.html">Software transaction commit order and conflict management</a> United States Patent 7711678, Granted 05/04/2010.</span> </li> <li id="cite_note-Ramadan2009-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-Ramadan2009_4-0">^</a></b></span> <span class="reference-text">Hany E. Ramadan, Indrajit Roy, Maurice Herlihy, Emmett Witchel (2009): <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=1504201">"Committing conflicting transactions in an STM"</a> (<a rel="nofollow" class="external text" href="http://www.cs.utexas.edu/~indrajit/pubs/ppopp121-ramadan.pdf">PDF</a><sup class="noprint Inline-Template"><span style="white-space: nowrap;">[<i><a href="/wiki/Wikipedia:Link_rot" title="Wikipedia:Link rot"><span title=" Dead link tagged July 2019">permanent dead link</span></a></i><span style="visibility:hidden; color:transparent; padding-left:2px">‍</span>]</span></sup>) <i>Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming</i> (PPoPP '09), <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-60558-397-6" title="Special:BookSources/978-1-60558-397-6">978-1-60558-397-6</a></span> </li> <li id="cite_note-vonParun2007-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-vonParun2007_5-0">^</a></b></span> <span class="reference-text">Christoph von Praun, Luis Ceze, Calin Cascaval (2007) <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=1229443">"Implicit Parallelism with Ordered Transactions"</a> (<a rel="nofollow" class="external text" href="http://www.cs.washington.edu/homes/luisceze/publications/ipot_ppopp07.pdf">PDF</a>), <i>Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming</i> (PPoPP '07), ACM New York ©2007, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-59593-602-8" title="Special:BookSources/978-1-59593-602-8">978-1-59593-602-8</a> doi 10.1145/1229428.1229443</span> </li> <li id="cite_note-Stone08-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-Stone08_6-0">^</a></b></span> <span class="reference-text">Robert Kallman, Hideaki Kimura, Jonathan Natkins, Andrew Pavlo, Alex Rasin, <a href="/wiki/Stanley_Zdonik" title="Stanley Zdonik">Stanley Zdonik</a>, Evan Jones, Yang Zhang, Samuel Madden, <a href="/wiki/Michael_Stonebraker" title="Michael Stonebraker">Michael Stonebraker</a>, John Hugg, Daniel Abadi (2008): <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=1454211">"H-Store: A High-Performance, Distributed Main Memory Transaction Processing System"</a>, <i>Proceedings of the 2008 VLDB</i>, pages 1496 - 1499, Auckland, New-Zealand, August 2008.</span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPerrizoTatarinov1998" class="citation conference cs1">Perrizo, William; Tatarinov, Igor (November 11, 1998). <i>A Semi-Optimistic Database Scheduler Based on Commit Ordering</i>. 1998 Int'l Conference on Computer Applications in Industry and Engineering. Las Vegas. pp. <span class="nowrap">75–</span>79. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.7318">10.1.1.53.7318</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=A+Semi-Optimistic+Database+Scheduler+Based+on+Commit+Ordering&rft.place=Las+Vegas&rft.pages=%3Cspan+class%3D%22nowrap%22%3E75-%3C%2Fspan%3E79&rft.date=1998-11-11&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.53.7318%23id-name%3DCiteSeerX&rft.aulast=Perrizo&rft.aufirst=William&rft.au=Tatarinov%2C+Igor&rfr_id=info%3Asid%2Fen.wikipedia.org%3ACommitment+ordering" class="Z3988"></span></span> </li> <li id="cite_note-Cahill08-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-Cahill08_8-0">^</a></b></span> <span class="reference-text">Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008): <a rel="nofollow" class="external text" href="http://portal.acm.org/citation.cfm?id=1376690">"Serializable isolation for snapshot databases"</a>, <i>Proceedings of the 2008 ACM SIGMOD international conference on Management of data</i>, pp. 729-738, Vancouver, Canada, June 2008, <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-60558-102-6" title="Special:BookSources/978-1-60558-102-6">978-1-60558-102-6</a> (SIGMOD 2008 best paper award</span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Commitment_ordering&action=edit&section=33" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="https://sites.google.com/site/yoavraz2/the_principle_of_co">Yoav Raz's Commitment ordering page</a></li></ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Commitment_ordering&oldid=1241510735">https://en.wikipedia.org/w/index.php?title=Commitment_ordering&oldid=1241510735</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Data_management" title="Category:Data management">Data management</a></li><li><a href="/wiki/Category:Databases" title="Category:Databases">Databases</a></li><li><a href="/wiki/Category:Transaction_processing" title="Category:Transaction processing">Transaction processing</a></li><li><a href="/wiki/Category:Concurrency_control" title="Category:Concurrency control">Concurrency control</a></li><li><a href="/wiki/Category:Distributed_algorithms" title="Category:Distributed algorithms">Distributed algorithms</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li><li><a href="/wiki/Category:All_articles_with_dead_external_links" title="Category:All articles with dead external links">All articles with dead external links</a></li><li><a href="/wiki/Category:Articles_with_dead_external_links_from_July_2019" title="Category:Articles with dead external links from July 2019">Articles with dead external links from July 2019</a></li><li><a href="/wiki/Category:Articles_with_permanently_dead_external_links" title="Category:Articles with permanently dead external links">Articles with permanently dead external links</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_matches_Wikidata" title="Category:Short description matches Wikidata">Short description matches Wikidata</a></li><li><a href="/wiki/Category:Articles_needing_expert_attention_from_October_2012" title="Category:Articles needing expert attention from October 2012">Articles needing expert attention from October 2012</a></li><li><a href="/wiki/Category:All_articles_needing_expert_attention" title="Category:All articles needing expert attention">All articles needing expert attention</a></li><li><a href="/wiki/Category:Computer_science_articles_needing_expert_attention" title="Category:Computer science articles needing expert attention">Computer science articles needing expert attention</a></li><li><a href="/wiki/Category:Articles_with_topics_of_unclear_notability_from_December_2011" title="Category:Articles with topics of unclear notability from December 2011">Articles with topics of unclear notability from December 2011</a></li><li><a href="/wiki/Category:All_articles_with_topics_of_unclear_notability" title="Category:All articles with topics of unclear notability">All articles with topics of unclear notability</a></li><li><a href="/wiki/Category:Articles_lacking_in-text_citations_from_November_2011" title="Category:Articles lacking in-text citations from November 2011">Articles lacking in-text citations from November 2011</a></li><li><a href="/wiki/Category:All_articles_lacking_in-text_citations" title="Category:All articles lacking in-text citations">All articles lacking in-text citations</a></li><li><a href="/wiki/Category:Wikipedia_articles_that_are_too_technical_from_November_2011" title="Category:Wikipedia articles that are too technical from November 2011">Wikipedia articles that are too technical from November 2011</a></li><li><a href="/wiki/Category:All_articles_that_are_too_technical" title="Category:All articles that are too technical">All articles that are too technical</a></li><li><a href="/wiki/Category:Wikipedia_articles_with_style_issues_from_November_2011" title="Category:Wikipedia articles with style issues from November 2011">Wikipedia articles with style issues from November 2011</a></li><li><a href="/wiki/Category:All_articles_with_style_issues" title="Category:All articles with style issues">All articles with style issues</a></li><li><a href="/wiki/Category:Wikipedia_articles_needing_rewrite_from_April_2020" title="Category:Wikipedia articles needing rewrite from April 2020">Wikipedia articles needing rewrite from April 2020</a></li><li><a href="/wiki/Category:All_articles_needing_rewrite" title="Category:All articles needing rewrite">All articles needing rewrite</a></li><li><a href="/wiki/Category:Articles_with_multiple_maintenance_issues" title="Category:Articles with multiple maintenance issues">Articles with multiple maintenance issues</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 21 August 2024, at 15:42<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Commitment_ordering&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia"> <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Commitment ordering</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>1 language</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-7b95555b9d-zzg4t","wgBackendResponseTime":167,"wgPageParseReport":{"limitreport":{"cputime":"0.390","walltime":"0.604","ppvisitednodes":{"value":3024,"limit":1000000},"postexpandincludesize":{"value":88729,"limit":2097152},"templateargumentsize":{"value":24191,"limit":2097152},"expansiondepth":{"value":19,"limit":100},"expensivefunctioncount":{"value":10,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":44788,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 374.807 1 -total"," 32.30% 121.081 1 Template:Multiple_issues"," 23.24% 87.093 4 Template:Citation"," 21.28% 79.743 1 Template:Short_description"," 16.57% 62.101 1 Template:Reflist"," 16.26% 60.940 6 Template:Ambox"," 14.92% 55.905 2 Template:Pagetype"," 13.21% 49.516 1 Template:Expert_needed"," 5.42% 20.297 4 Template:ISBN"," 5.08% 19.050 3 Template:Category_handler"]},"scribunto":{"limitreport-timeusage":{"value":"0.174","limit":"10.000"},"limitreport-memusage":{"value":6113490,"limit":52428800}},"cachereport":{"origin":"mw-api-ext.eqiad.main-6b5dbbb84-n84zc","timestamp":"20250210052635","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Commitment ordering","url":"https:\/\/en.wikipedia.org\/wiki\/Commitment_ordering","sameAs":"http:\/\/www.wikidata.org\/entity\/Q5152903","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q5152903","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2006-03-13T16:12:39Z","dateModified":"2024-08-21T15:42:30Z","headline":"concurrency control technique for databases"}</script> </body> </html>