Content deleted Content added
m General fixes, removed: |curly=y using AWB (9268) |
Aaron Schulz (talk | contribs) |
||
Line 12:
| last2 = Stonebraker
| first2 = M.
}}</ref> is a [[distributed algorithm]] which lets all nodes in a [[distributed system]] agree to [[commit]] a [[database transaction|transaction]]. Unlike the [[two-phase commit protocol]] (2PC) however, 3PC is non-blocking. Specifically, 3PC places an upper bound on the amount of time required before a transaction either commits or [[Abort (computing)|aborts]]. This property ensures that if a given transaction is attempting to commit via 3PC and holds some [[lock (computer science)|resource locks]], it will release the locks after the timeout.
3PC was originally described by [[Dale Skeen]] and [[Michael Stonebraker]] in their paper, “A Formal Model of Crash Recovery in a Distributed System”.<ref name=3PC /> In that work, they modeled 2PC as a system of [[non-deterministic finite automaton|non-deterministic finite state automata]] and proved that it is not resilient to a random single site failure. The basic observation is that in 2PC, while one site is in the “prepared to commit” state, the other may be in either the “commit” or the “abort” state. From this analysis, they developed 3PC to avoid such states and it is thus resilient to such failures.
Line 49:
==Disadvantages==
The main disadvantage to this algorithm is that it cannot recover in the event the network is segmented in any manner. The original 3PC algorithm assumes a fail-stop model, where processes fail by crashing and crashes can be
accurately detected, and does not work with network partitions or asynchronous communication.
Keidar and Dolev's E3PC<ref name=E3PC>{{cite
url=http://webee.technion.ac.il/~idish/Abstracts/jcss.html|doi=10.1006/jcss.1998.1566}}</ref> algorithm eliminates this disadvantage.
| |||