Introduction Background

Introduction

• Introduction

• Background

• Distributed DBMS Architecture

• Distributed Database Design

• Distributed Query Processing

• Distributed Transaction Management

• Transaction Concepts and Models
• Distributed Concurrency Control
• Distributed Reliability

• Building Distributed Database Systems (RAID)

• Mobile Database Systems

• Privacy, Trust, and Authentication

• Peer to Peer Systems

Arise due to non-atomicity of log and message send actions

• Arise due to non-atomicity of log and message send actions

• Coordinator site fails after writing “begin_commit” log and before sending “prepare” command

• treat it as a failure in WAIT state; send “prepare” command

• Participant site fails after writing “ready” record in log but before “vote-commit” is sent

• treat it as failure in READY state
• alternatively, can send “vote-commit” upon recovery

• Participant site fails after writing “abort” record in log but before “vote-abort” is sent

• no need to do anything upon recovery

Coordinator site fails after logging its final decision record but before sending its decision to the participants

• Coordinator site fails after logging its final decision record but before sending its decision to the participants

• coordinator treats it as a failure in COMMIT or ABORT state
• participants treat it as timeout in the READY state

• Participant site fails after writing “abort” or “commit” record in log but before acknowledgement is sent

• participant treats it as failure in COMMIT or ABORT state
• coordinator will handle it by timeout in COMMIT or ABORT state

Blocking

• Blocking

• Ready implies that the participant waits for the coordinator
• If coordinator fails, site is blocked until recovery
• Blocking reduces availability

• Independent recovery is not possible

• However, it is known that:

• Independent recovery protocols exist only for single site failures; no independent recovery protocol exists which is resilient to multiple-site failures.

• So we search for these protocols – 3PC

3PC is non-blocking.

• 3PC is non-blocking.

• A commit protocols is non-blocking iff

• it is synchronous within one state transition, and
• its state transition diagram contains
• no state which is “adjacent” to both a commit and an abort state, and
• no non-committable state which is “adjacent” to a commit state

• Adjacent: possible to go from one stat to another with a single state transition

• Committable: all sites have voted to commit a transaction

• e.g.: COMMIT state

Global state vector containing the states of the local protocols.

• Global state vector containing the states of the local protocols.

• Outstanding messages in the network

• A global state transition occurs whenever a local state transition occurs at a participating site.

• Exactly one global transition occurs for each local transition.

Global state is inconsistent if its state vector contains both a commit and abort state.

• Global state is inconsistent if its state vector contains both a commit and abort state.

Two states are potentially concurrent if there exists a reachable global state that contains both local states.

• Two states are potentially concurrent if there exists a reachable global state that contains both local states.

• Concurrency set of s is set of all local states that are potentially concurrent with it. C(s)

• C(w1) = {q2, a2 , w2}

• The sender set for s,

• S(s) = {t/t sends message m & m  M}

• where M be the set of messages that are received by s.

• t is a local state.

Global state inconsistent if it contains both

• Global state inconsistent if it contains both

• local commit state
• local abort state

• Final state if

• All local states are final

• Terminal state if:

• there exists an immediately reachable successor state
•  deadlock

• Committable state (local) if:

• all sites have voted yes on committing the transaction

• Otherwise, non-committable

This site can safely abort the transaction if and only if the concurrency set for its local state does not contain a commit state

• This site can safely abort the transaction if and only if the concurrency set for its local state does not contain a commit state

• This site can safely commit only if

• Its local state must be “committable”
• And the concurrency set for its state must not contain an abort state.

• A blocking situation arises when

• The concurrency set for the local state contains both a commit and an abort state
• Or the site is in a “noncommittable” state and the concurrency set for that state contains a commit state
• The site can not commit because it can not infer that all sites have voted yes on committing
• It can not abort because another site may have committed the transaction before crashing.

• There observations imply the simple but power result in the next slide

Definition: protocol is synchronous within one state transition if one site never leads another site by more than one state transition.

• Definition: protocol is synchronous within one state transition if one site never leads another site by more than one state transition.

• Theorem Fundamental non-blocking: A protocol is non-blocking iff

• There exists no local state s
• C(s) = A (abort) and C (commit)
• And there exists no non-committable state s
• C(s) = C (commit)

• Lemma: A protocol that is synchronous within one state transition is non-blocking iff:

• No local state is adjacent to both a commit & an abort state
• No non-committable state is adjacent to a commit state