--- title: "Flat/nested transactions; concurrency control" subject: "Distributed System" chapter: 8 key: "semester_7/distributed_system:flat-nested-cc-methods" source: https://www.bctengineer.com/q/semester_7/distributed_system/flat-nested-cc-methods site: BCT Engineering --- # Flat/nested transactions; concurrency control Distributed System · Chapter 8: Transaction and Concurrency Control - Asked in: 2069 Chaitra, 3+4 marks - Video: [Concurrency Control in Distributed System](https://www.youtube.com/watch?v=37GNuOlsSuY) — Norman Dias - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/flat-nested-cc-methods - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-8 ## Question What are the flat and nested transactions? Describe the methods for concurrency control in distributed system. ## Short answer A flat transaction is single-level and all-or-nothing. A nested transaction consists of sub-transactions in a tree, allowing internal concurrency and independent abort. Concurrency control methods include locking (strict 2PL), timestamp ordering (operations ordered by timestamp, no deadlock), and optimistic control (conflict check at commit). ## Answer #### Flat and nested transactions - **Flat transaction**: a single-level transaction that issues its requests one after another on one or more objects. If any step fails, the whole transaction aborts and everything is undone. Example: a bank transfer *withdraw(A, 100); deposit(B, 100)*. Its drawback is that it cannot commit part of its work and has no internal concurrency. - **Nested transaction**: a transaction made of sub-transactions in a tree. The top-level transaction contains child transactions, which may contain their own children. Sub-transactions at the same level can run **concurrently**, and a sub-transaction can abort without aborting its parent; the parent may retry or choose another action. Example: a *book trip* transaction with sub-transactions *book flight*, *book hotel*, *book taxi*. If the taxi booking fails, the parent can try another company. #### Concurrency control methods Concurrency control ensures that concurrent transactions leave the data in a state equivalent to some serial execution (serial equivalence) and avoid problems like lost update and inconsistent retrieval. 1. **Locking** (pessimistic): a transaction locks data before access and holds it (strict 2PL) until commit. Conflicts cause waiting; deadlock is possible. 2. **Timestamp ordering**: each transaction gets a timestamp; conflicting operations must be executed in timestamp order; late operations abort the transaction. No deadlock. 3. **Optimistic concurrency control**: work on private copies, validate at commit time, and abort if there was a conflict. A **lock** is a variable associated with a data item that controls concurrent access. A transaction must obtain the lock before it reads or writes the item, and releases it when finished. Common modes are **read (shared) lock** and **write (exclusive) lock**; several transactions can hold read locks together, but a write lock excludes all others. In **two-phase locking (2PL)** a transaction has a growing phase (acquires locks) followed by a shrinking phase (releases locks, never acquires again). **Strict 2PL** holds all locks until commit or abort, which prevents dirty reads and cascading aborts. **Timestamp ordering** gives each transaction a unique timestamp when it starts (a Lamport clock or a global timestamp from server id and local clock in a distributed system). Conflicting operations are executed in timestamp order, so the result is equivalent to running transactions serially in timestamp order. No locks are used, so no deadlock. Each object keeps a **write timestamp** (of the last committed write) and **read timestamps** (of transactions that read it). For a transaction T with timestamp Tc: - **Write rule**: T's write is allowed only if Tc ≥ the maximum read timestamp of the object and Tc > the write timestamp of the committed version. Otherwise T is aborted (it would invalidate a later read). - **Read rule**: T's read is allowed if Tc > the write timestamp of the committed version; if a tentative version from an earlier transaction exists, T waits until it commits or aborts. If Tc is smaller than the write timestamp, T is too late and is aborted. An aborted transaction restarts with a new, later timestamp. Timestamp ordering is deadlock-free, but it causes restarts; keeping multiple versions of objects reduces the number of aborts. **Optimistic concurrency control** (Kung and Robinson) assumes conflicts are rare, so transactions proceed without locks and are checked for conflicts only when they want to commit. A transaction goes through three phases. 1. **Working phase**: it reads and writes tentative copies of objects (private versions). Reads see the last committed values; no locks are taken. The system records the read set and write set. 2. **Validation phase**: when the client requests commit, the server checks for conflicts with other transactions that overlapped in time. If validation fails, the transaction is aborted (or conflict resolution is used). 3. **Update phase**: if validation succeeds, tentative versions are made permanent (written to permanent storage) and the transaction commits. **Validation (backward validation)**: transaction Tv is checked against earlier overlapping transactions Ti that committed before Tv started validation. Rules: - If Ti writes an object that Tv reads (Ti's write set ∩ Tv's read set ≠ ∅), validation fails, because Tv read stale data. - Otherwise Tv passes validation. (Writes are applied in commit order, so write-write conflicts cannot occur.) **Forward validation** checks Tv's write set against the read sets of still-active transactions; it allows a choice of aborting Tv or the others. In a distributed system, each server validates its own part of the transaction during the first phase of two-phase commit, and all servers must validate in the same global order to avoid commitment deadlock and inconsistent serial orders. **Advantages** - No locking, so no deadlock and no lock overhead. - High concurrency when conflicts are rare; with forward validation, read-only transactions always pass validation. - Abort is cheap because nothing was written permanently. **Disadvantages** - Under heavy conflicts many transactions abort and restart; starvation is possible. - Wasted work for aborted transactions. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. Which describes a flat transaction? A. A tree of concurrent sub-transactions B. A single-level transaction where any failed step aborts the whole transaction C. A transaction that can commit part of its work D. A transaction running on many servers by definition Answer: B. A flat transaction issues requests one after another and, if any fails, everything is undone; it cannot commit part of its work. (Key point: Flat vs nested transaction) 2. What does strict 2PL do that prevents dirty reads and cascading aborts? A. Releases locks as soon as the operation finishes B. Holds all locks until commit or abort C. Uses no locks D. Allows only read locks Answer: B. Holding locks until the end prevents others from reading uncommitted data. (Key point: Strict two-phase locking) 3. Under timestamp ordering, why would a write by T be rejected? A. T's timestamp is too late relative to a later read or write, which would invalidate it B. The object has no timestamp C. T holds a lock D. T is a read-only transaction Answer: A. A write is allowed only if Tc is at least the maximum read timestamp and greater than the committed write timestamp; otherwise T is aborted. (Key point: Timestamp write rule) 4. What is the correct order of phases in optimistic concurrency control? A. Validation, working, update B. Working, validation, update C. Update, working, validation D. Working, update, validation Answer: B. Transactions work on tentative copies, are validated at commit request, and only then made permanent. (Key point: Optimistic phases) 5. In backward validation, Tv fails if: A. Tv's read set overlaps the write set of an earlier committed overlapping transaction B. Tv writes any object C. Tv is read-only D. Another transaction is still active Answer: A. If an earlier transaction wrote something Tv read, Tv read stale data and must abort. (Key point: Backward validation) ## Related in Distributed System - [Flat/nested transactions; optimistic CC](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aflat-nested-optimistic) — Distributed System, chapter 8 - [Distributed concurrency control methods](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adistributed-cc-methods) — Distributed System, chapter 8 - [Distributed and nested distributed transactions](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adistributed-transaction-nested) — Distributed System, chapter 8 - [Nested transactions; optimistic CC advantages](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Anested-optimistic-advantages) — Distributed System, chapter 8 - [Nested vs distributed transaction; 2PC](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Anested-vs-distributed-2pc) — Distributed System, chapter 8, asked 2× - [Short note: Flat versus nested locks](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Aflat-vs-nested-locks-note) — Distributed System, chapter 8