000225579 001__ 225579
000225579 005__ 20190317000634.0
000225579 037__ $$aREP_WORK
000225579 245__ $$aHow Fast can a Distributed Transaction Commit?
000225579 269__ $$a2017
000225579 260__ $$c2017
000225579 300__ $$a26
000225579 336__ $$aReports
000225579 520__ $$aThe atomic commit problem lies at the heart of distributed database systems. The problem consists for a set of processes (database nodes) to agree on whether to commit or abort a transaction (agreement property). The commit decision can only be taken if all processes are initially willing to commit the transaction, and this decision must be taken if all processes are willing to commit and there is no failure (validity property). An atomic commit protocol is said to be non-blocking if every correct process (a database node that does not fail) eventually reaches a decision (commit or abort) even if there are failures elsewhere in the distributed database system (termination property). Surprisingly, despite the importance of the atomic commit problem, little is known about its complexity. In this paper, we present, for the first time, a systematic study on the time and message complexity of the problem. We measure complexity in the executions that are considered the most frequent in practice, i.e., failure-free, with all processes willing to commit. In other words, we measure how fast a transaction can commit. Through our systematic study, we close many open questions like the complexity of synchronous non-blocking atomic commit. We also present optimal protocols which may be of independent interest. In particular, we present an effective protocol which solves what we call indulgent atomic commit that tolerates practical distributed database systems which are synchronous ``most of the time''.
000225579 6531_ $$aatomic commit
000225579 6531_ $$atime and message complexity
000225579 6531_ $$aindulgent atomic commit
000225579 700__ $$0240335$$g105326$$aGuerraoui, Rachid
000225579 700__ $$aWang, Jingjing$$0248100$$g232934
000225579 8564_ $$uhttps://infoscience.epfl.ch/record/225579/files/how_fast_can_a_distributed_tx_commit.pdf$$zn/a$$s475176$$yn/a
000225579 909C0 $$xU10407$$0252114$$pDCL
000225579 909CO $$ooai:infoscience.tind.io:225579$$qGLOBAL_SET$$pIC$$preport
000225579 917Z8 $$x232934
000225579 937__ $$aEPFL-REPORT-225579
000225579 973__ $$aEPFL
000225579 980__ $$aREPORT