Supporting and Controlling Complex Concurrency in Fault- Tolerant\n Distributed Systems

Jie Xu, Brian Randell, Alexander Romanovsky, Robert J. Stroud, Avelino F. Zorzo

Abstract

Distributed computing often gives rise to complex concurrent and interacting activities. In some cases several concurrent activities may be working together, i.e. cooperating, to solve a given problem; in other cases, the activities may be independent but needing to share common system resources for which they must compete. Many difficulties and limitations occur in the widely advocated objects and (trans)actions model when it is supposed to support cooperating activities. We have introduced previously the concept of coordinated atomic (CA) actions [Xu et al. 1995]; this paper analyzes and examines the derived objects and CA actions model for constructing fault-tolerant distributed systems and providing unified support for both cooperative and competitive concurrency. Our investigation reveals and clarifies several significant problems that have not previously been studied extensively, including the problem of ensuring consistent access to shared objects from a joint action as opposed to a set of independent actions. Conceptual and implementation-related solutions are proposed and illustrated.

Introduction

In distributed computing, concurrency typically manifests in two distinct forms: competitive and cooperative. Competitive concurrency involves independent tasks vying for shared resources, such as two users booking the same flight seat. Traditional atomic transactions handle this well by enforcing isolation. Conversely, cooperative concurrency involves tasks working together toward a common goal, like a group of robots coordinating movements. Here, isolation is a hindrance; threads must share information in real-time.

Traditional transaction models often fail to support cooperative work effectively because their core design principle—isolation—prevents necessary interaction. While generalized transaction models attempt to relax these rules, they often compromise on atomicity or provide insufficient support for multi-threaded cooperation. This research addresses this gap by introducing a unified framework that supports both concurrency types without sacrificing safety guarantees.

The Coordinated Atomic (CA) Action Model

The authors propose the Coordinated Atomic (CA) action as a control abstraction designed to enclose multi-threaded interactions. Unlike traditional transactions that focus on a single thread of control, a CA action manages a group of interacting threads within strict boundaries to prevent the "domino effect" of cascading rollbacks.

Key features of the CA action model include:

  • Coordinated Error Recovery: If a failure occurs within the action, all participating threads must cooperate to reach a consistent state, utilizing either backward recovery (rolling back to a recovery line) or forward recovery.
  • Shared Object Management: The model distinguishes between internal objects used for cooperation and external "atomic objects" used for competition between different actions.
  • Atomicity Maintenance: CA actions maintain atomicity at every level of nesting, ensuring system state remains consistent even during complex failures.
  • The Test Line: Beyond recovery points, CA actions utilize a "test line" of acceptance tests that all participating threads must pass before an action can successfully commit.
Comparison of concurrency control models for CA actions and nested transactions.

As shown in the table above, the CA action model specifically addresses cooperating threads and nested actions, contrasting with the competing nature of standard nested transactions.

Architectural Implementation and Results

A significant contribution of this work is the architectural blueprint for implementing CA actions on top of existing infrastructure. The authors propose a "CA Action Manager" and a "Mapping Subsystem" that interface with standard transaction processing systems. This allows the complex, multi-threaded logic of CA actions to be translated into sequences manageable by underlying systems like Arjuna.

Architecture of a Distributed CA Action Processing System.

The prototype implementation using Java and the Arjuna fault-tolerant system demonstrated the feasibility of this model. By leveraging a mapping layer, the system can utilize established transaction processing research while supporting the more sophisticated requirements of cooperative concurrency.

Discussion and Future Work

While the CA action model provides a robust framework, it introduces architectural complexity and potential performance overhead due to the mapping layer. The authors identify several areas for future research:

  • Software Fault Tolerance: While hardware faults are addressed, residual software design faults in complex cooperative systems require further investigation.
  • Performance Optimization: Direct control mechanisms for shared objects might offer better performance than the current mapping approach.
  • Nesting Semantics: The complexity of nested CA actions requires disciplined programming practices to ensure correctness.

In conclusion, CA actions offer a unified approach to managing the duality of cooperation and competition in distributed systems, providing a path toward more reliable and flexible fault-tolerant architectures.

Summary updated

Abstract

Distributed computing often gives rise to complex concurrent and interacting\nactivities. In some cases several concurrent activities may be working\ntogether, i.e. cooperating, to solve a given problem; in other cases, the\nactivities may be independent but needing to share common system resources for\nwhich they must compete. Many difficulties and limitations occur in the widely\nadvocated objects and (trans)actions model when it is supposed to support\ncooperating activities. We have introduced previously the concept of\ncoordinated atomic (CA) actions [Xu et al. 1995]; this paper analyzes and\nexamines the derived objects and CA actions model for constructing\nfault-tolerant distributed systems and providing unified support for both\ncooperative and competitive concurrency. Our investigation reveals and\nclarifies several significant problems that have not previously been studied\nextensively, including the problem of ensuring consistent access to shared\nobjects from a joint action as opposed to a set of independent actions.\nConceptual and implementation-related solutions are proposed and illustrated.\n
BibTeX
@misc{xu2021supporting,
  author = {Jie Xu and Brian Randell and Alexander Romanovsky and Robert J. Stroud and Avelino F. Zorzo},
  title = {{Supporting and Controlling Complex Concurrency in Fault- Tolerant\textbackslash\{\}n Distributed Systems}},
  year = {2021},
  eprint = {2111.06339},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.06339},
}

Loading related content...

Figure