CCDS Examples Class 2

Audio transcript and materials used on 28th October 2021 for part Ib Computer Science Concurrent and Distributed Systems Examples Class 2.

If your voice is audible and you want to be removed, please let DJG know.

Based on 2000 Paper 4 Question 1

In a banking system where accounts cannot become overdrawn, some of the following types transactions often run concurrently:

  • Debit (D) transactions to make payments from customer accounts to an external agency, such as a credit card company.
  • Interest (I) transactions to add daily interest to customer account balances.
  • Transfer (T) transactions which first check whether the source account contains sufficient funds then either abort or continue the transfer from source to destination accounts. Customer x may run Tx to transfer £1000 from A to B. Customer y may run Ty to transfer £200 from B to A.

     

    (a) Discuss the potential for interference between any of these transactions. [7 marks]

    (b) Demonstrate the effect of concurrency control based on strict two-phase locking in relation to the discussion in (a). Does it help? [8 marks]

    (c) Does 2PL help when customer x might issue several transfer requests from their account A? [5 marks]

    [Hint: you may assume that operations on bank account objects, such as debit, credit and add-interest are atomic.]

    2007 Paper 4 Question 1

    This question has more bookwork than suitable for open book examinations?

     

    (a) What is meant by a serializable order for two or more transactions? [2 marks]

    (b) Explain how timestamp ordering (TSO) enforces isolation. [5 marks]

    (c) Draw and explain a history graph for two transactions whose invocations of a set of conflicting operations are serializable but which are rejected by TSO. [5 marks]

    (d) Considering Optimistic Concurrency Control (OCC):
    (i) State the properties of a transaction’s set of shadow copies that must be verified at commit time. [2 marks]
    (ii) Carefully explain the algorithm used by a single-threaded commit-time validator. [4 marks] [ONLINE ANSWER IS JUST A REPLICATION OF THE LECTURE NOTES!]

    (e) [DISTRIBUTED SYSTEMS] Consider a system in which the transactions cause updates to objects which are not all located on a single server but which are distributed widely around the Internet. What factors would influence your choice of using TSO or OCC to enforce isolation? [2 marks]

    Agents and Monitors Discussion

    Differences between monitors and active objects (and commonalities).

    Synchronous vs Asynchronous Composition Discussion

    Which do actor models use and why/when is the other important?

    Types of Proof Discussion

    Of interest perhaps, but this material is certainly not on the syllabus for this course (and DJG is not an expert).

    I pulled up this Wikipedia page: Dekker Algorithm.

    (C)2021 DJ Greaves, University of Cambridge Computer Laboratory.