Table of contents

1 Transactions

2 Transaction models

3 Documents

4 Results


Editor: Monika Moser

Transaction model, distributed algorithms, how to put it on top of an overlay.



A transaction is a unit of data processing in an information system. It can be viewed as a portion of a program delimited by the primitives begin and end. The information system should guarantee the following ACID-properties for each transaction:

  • Atomicity: Operations of a transaction are performed in an all-or-nothing manner.
  • Consistency: A transaction does not violate the systems consistency rules. After completion the system is in a legal state.
  • Isolation: Each transaction is independent from other transactions. Concurrent transactions can't observe one another's intermediate results.
  • Durability: Once a transaction is committed the results are persistent.

Distributed Transactions

A distributed transaction involves objects which are managed by different servers. Three main issues have to be considered:

  • Each of the participating servers has to decide on the same outcome of the transaction to ensure the atomicity property. Therefore an atomic commit protocol is used.
  • Transaction have to be serializable which is realized by certain concurrency control mechanisms.
  • Objects involved in transactions have to be recoverable. Besides that a recovery mechanism ensures that values of objects only reflect changes made by committed transactions.

Transaction models

Transactions in SONs are rather costly in terms of message delays. Solutions with as little message delays as possible have to be found to provide transactions with acceptable performance. An approach with optimistic concurrency control may support this purpose. However when having a high update rate this could lead to many transactions aborting. To prevent transactions from frequent aborts in such a case a pessemistic concurrency control has to be used. Interesting issues arise from the combination of the transaction mechanisms and replication mechanisms. While those two mechanisms could be treated as orthogonal services an interleaving may provide better performance.

We try to identify different transaction models ranging from optimistic schemes to pessimistic schemes. The different models will be analyzed regarding the following properties:

  • The probability for a transaction to abort.
  • Number of message delays.
  • Number of messages.
  • Amount of data that has to be sent between nodes

These properties will be studied using the following parameters:

  • Read/update rates
  • Durations of a transaction
  • Amount of data that is touched
  • Availability of nodes

Next Steps

The next steps will be:

  • Defining different models for transactions:
    • One which is as cheap as possible using an optimistic concurrency control.
    • One pessimistic model which prevents transactions from aborting when the update rate is high
    • Hybrid model
  • Create a scheme to analyze different transaction models.


Slides from the meeting at ZIB in Berlin, February 15-16, 2007

Atomic Commitment in DHTs

Slides from the meeting at UCL, May 30-31, 2007

Deliverable 3.1a, Atomic Commitment in transactional DHTs


M. Moser, S. Haridi. Atomic Commitment in Transactional DHTs. In proceedings of the CoreGRID Symposium, Rennes, France, August, 2007.

Abstract: We investigate the problem of atomic commit in transactional database systems built on top of Distributed Hash Tables. Therefore we present a framework for DHTs to provide strong data consistency and transactions on data stored in a decentralized way. To solve the atomic commit problem within distributed transactions, we propose to use an adaption of Paxos commit as a non-blocking algorithm. We exploit the symmetric replication technique existing in the DKS DHT to determine which nodes are necessary to execute the commit algorithm. By doing so, we achieve a lower number of communication rounds in contrast to applying traditional Three-Phase-Commit protocols. We also show how the proposed solution can cope with dynamism due to churn in DHTs. Our solution works correctly relying only on an inaccurate failure detection of node failure, what is necessary for systems running over the Internet.

S. Plantikow, A. Reinefeld, and F. Schintke. Distributed Wikis on Structured Overlays. CoreGRID Workshop on Grid Programming Model, Grid and P2P System Architecture, Grid Systems, Tools and Environments, Heraklion, Crete, June 2007.

An improved version has been accepted by DSOM 2007.

Abstract: We present a transaction processing scheme for structured overlay networks and use it to develop a distributed Wiki application that is based on a relational data model. The Wiki supports rich metadata and additional indexes for navigation purposes. Ensuring consistency and durability requires handling of node failures. We mask such failures by providing high availability of nodes by constructing the overlay from replicated state machines (Cell model). Atomicity is realized using two phase commit with additional support for failure detection and restoration of the transaction manager. The developed transaction processing scheme provides the application with a mixture of pessimistic, hybrid optimistic and multiversioning concurrency control techniques to minimize the impact of replication on latency and optimize for read operations. We present pseudocode of the relevant Wiki functions and evaluate the different concurrency control techniques in terms of message complexity.