On the intractability of task allocation in distributed systems

Hesham H. Ali, Hesham El-Rewini

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

The fast progress of large integration technology has made distributed computing economically attractive for many computer applications. Task allocation is one of the most important and challenging problems in distributed computing systems that has received considerable attention in recent years. Several researchers have introduced different heuristics to solve this problem with the assumption that it is computationally intractable. These researchers have been referring to an early work by Stone and some private communication as their sources of the problem's intractability. However, neither Stone's paper nor any other related work in the literature provided a formal proof of intractability. Due to the importance of the task allocation problem, we believe that a formal proof of its complexity must be provided. In this paper we provide a proof that the problem of task allocation is intractable even in the restricted case when there are only two values of the communication cost: zero or one. We introduce a new model to represent the problem of allocating tasks on heterogeneous distributed systems using split graphs. This model allows us to relate the task allocation problem with the problem of weighted clique partitioning in complete split graphs. We provide a two-step reduction method to prove the intractability of task allocation in the restricted case mentioned above. In the first step, we prove that the problem of weighted clique partitioning in complete split graph is NP-complete using a transformation from the problem of partition into triangles. In the second step, we show that the task allocation problem is NP-complete using a transformation from the weighted clique partitioning problem.

Original languageEnglish (US)
Pages (from-to)149-157
Number of pages9
JournalParallel Processing Letters
Volume4
Issue number1-2
StatePublished - Jun 1994

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'On the intractability of task allocation in distributed systems'. Together they form a unique fingerprint.

Cite this