Static assignment of stochastic tasks using majorization

David M. Nicol, Rahul Simha, Don Towsley

Research output: Contribution to journalArticlepeer-review


We consider the problem of statically assigning many tasks to a (smaller) system of homogeneous processors, where a task's structure is modeled as a branching process, all tasks are assumed to have identical behavior, and the tasks may synchronize frequently. We show how the theory of majorization can be used to obtain a partial order among possible task assignments. We show that if the vector of numbers of tasks assigned to each processor under one mapping is majorized by that of another mapping, then the former mapping is better than the latter with respect to a large number of objective functions. In particular, we show how the metrics of finishing time, the space-time product, and reliability are all captured. We also apply majorization to the problem of partitioning a pool of processors for distribution among parallelizable tasks. Limitations of the approach, which include the static nature of the assignment, are also discussed.

Original languageEnglish (US)
Pages (from-to)730-740
Number of pages11
JournalIEEE Transactions on Computers
Issue number6
StatePublished - 1996
Externally publishedYes


  • Load balancing
  • Majorization
  • Performance of parallel systems
  • Processor allocation
  • Resource allocation
  • Task allocation
  • Task assignment

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Static assignment of stochastic tasks using majorization'. Together they form a unique fingerprint.

Cite this