A very large number of applications that are currently deployed on large scale distributed systems such as grids or volunteer computing systems are Bag-of-Tasks (BoT) applications. Up until now, simple mechanisms have been used to ensure a fair sharing of resources amongst these applications. Although these mechanisms have proved efficient for CPU-bound applications, they are known to be ineffective in the presence of network-bound applications. In this article, we propose a fully distributed algorithm for fairly scheduling BoT applications on a computing grid while respecting resource constraints. This algorithm is inspired by techniques used in flow control mechanisms in multi-path networks. Yet, we prove that the context of BoT scheduling is significantly more difficult in practice and that a set of non-trivial adaptations are required to ensure convergence. We prove their effectiveness through an extensive set of simulations that enables to deeply understand the potential benefits as well as the limitations of this technique in the context of grid computing.

Keywords: Lagrangian optimization, steady-state scheduling, distributed scheduling, grid computing

Multiple applications that execute concurrently on heterogeneous platforms compete for CPU and network resources. In this paper we analyze the behavior of K non-cooperative schedulers using the optimal strategy that maximize their efficiency. Meanwhile fairness is ensured at a system level ignoring applications characteristics. We limit our study to simple single-level master-worker platforms and the case where applications consist of a large number of independent tasks. The tasks of a given application all have the same computation and communication requirements, but these requirements can vary from one application to another. Therefore, each scheduler aims at maximizing its throughput. We give closed-form formula of the equilibrium reached by such a system and study its performances. We characterize the situations where this Nash equilibrium is Pareto-optimal and show that even though no catastrophic situation (Braess-like paradox) can occur, such an equilibrium can be arbitrarily bad for any classical performance measure.

Keywords: Nash equilibria, scheduling, bag-of-tasks applications, Braess paradox

Keywords: fairness, non-convex optimization

Keywords: combinatorial optimization, satellite networks, MFTDMA systems, linear programming

Keywords: fairness, satellite networks, resource allocation, combinatorial optimization

Keywords: fairness, generalized Nash Bargaining Solution