Hierarchical Dynamics, Interarrival Times, and Performance

15 November 2003

proceedings article
Published by Association for Computing Machinery (ACM)

Abstract

We report on a model of the distribution of job submission interarrival times in supercomputers.Interarrival times are modeled as a consequence of a complicated set of decisions between users, the queuing algorithm, and other policies.This cascading hierarchy of decision-making processes leads to a particular kind of heavy-tailed distribution.Specifically, hierarchically constrained systems suggest that fatter tails are due to more levels coming into play in the overall decision-making process.The key contribution of this paper is that heavier tials resulting from more complex decision-making processes, that ismore hierarchical levels, will lead to overall worse performance, even when the average interarrival time is the same.Finally, we offer some suggestions for how to overcome these issues and the tradeoffs involved.

Keywords

This publication has 10 references indexed in Scilit:

Scaling phenomena in the Internet: Critically examining criticality
Proceedings of the National Academy of Sciences, 2002
Self-similarity in file systems
Published by Association for Computing Machinery (ACM) ,1998
Stretched exponential distributions in nature and economy: “fat tails” with characteristic scales
Zeitschrift für Physik B Condensed Matter, 1998
Extreme Deviations and Applications
Journal de Physique I, 1997
Wide area traffic: the failure of Poisson modeling
IEEE/ACM Transactions on Networking, 1995
Long-range dependence in variable-bit-rate video traffic
IEEE Transactions on Communications, 1995
A fair share scheduler
Communications of the ACM, 1988
On the relationship among three theories of relaxation in disordered systems
Proceedings of the National Academy of Sciences, 1986
Models of Hierarchically Constrained Dynamics for Glassy Relaxation
Physical Review Letters, 1984
Theorie des elektrischen Rückstandes in der Leidener Flasche
Annalen der Physik, 1854