Adaptive reputation-based scheduling on unreliable distributed infrastructures

Research output: Contribution to journalArticlepeer-review

79 Scopus citations


This paper addresses the inherent unreliability and instability of worker nodes in large-scale donationbased distributed infrastructures such as P2P and Grid systems. We present adaptive scheduling techniques that can mitigate this uncertainty and significantly outperform current approaches. In this work, we consider nodes that execute tasks via donated computational resources and may behave erratically or maliciously. We present a model in which reliability is not a binary property but a statistical one based on a node's prior performance and behavior. We use this model to construct several reputationbased scheduling algorithms that employ estimated reliability ratings of worker nodes for efficient task allocation. Our scheduling algorithms are designed to adapt to changing system conditions as well as non-stationary node reliability. Through simulation we demonstrate that our algorithms can significantly improve throughput, while maintaining a very high success rate of task completion. Our results suggest that reputation-based scheduling can handle wide variety of worker populations, including non-stationary behavior, with overhead that scales well with system size. We also show that our adaptation mechanism allows the application designer fine-grain control over desired performance metrics.

Original languageEnglish (US)
Pages (from-to)1551-1564
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number11
StatePublished - Nov 2007


  • Adaptive
  • Distributed scheduling
  • Grids
  • Reliability
  • Reputation


Dive into the research topics of 'Adaptive reputation-based scheduling on unreliable distributed infrastructures'. Together they form a unique fingerprint.

Cite this