A task duplication scheme for resolving deadlocks in clustered DAGs

Bassel R. Arafeh*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


This work introduces a duplication-based deadlock resolution (DBDR) scheme in clustered directed acyclic graphs using three methods for duplicating a task. The scheme can be embedded within any clustering technique for handling synchronous communication with an added cost of O(|E| + (|V|)2). The main objective of task duplication, besides to resolving deadlocks, has been the reduction of communication cost and the improvement in the program computation to communication ratio. The embedding of the DBDR scheme within a clustering technique is shown along with the analysis of its complexity. A comparison between deadlock resolution strategy using the DBDR and deadlock avoidance strategy using the same clustering technique is given.

Original languageEnglish
Pages (from-to)795-820
Number of pages26
JournalParallel Computing
Issue number6
Publication statusPublished - Jun 2003


  • Clustering
  • Duplication-based deadlock resolution
  • Network of workstations
  • Scheduling algorithms
  • Synchronous communication

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design
  • Artificial Intelligence


Dive into the research topics of 'A task duplication scheme for resolving deadlocks in clustered DAGs'. Together they form a unique fingerprint.

Cite this