A Fair Comparison of Pull and Push Strategies in Large Distributed Networks
- 15 July 2013
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 22 (3), 996-1006
- https://doi.org/10.1109/tnet.2013.2270445
Abstract
In this paper, we compare the performance of the pull and push strategies in a large homogeneous distributed system. When a pull strategy is in use, lightly loaded nodes attempt to steal jobs from more highly loaded nodes, while under the push strategy, more highly loaded nodes look for lightly loaded nodes to process some of their jobs. Given the maximum allowed overall probe rate R and arrival rate λ, we provide closed-form solutions for the mean response time of a job for the push and pull strategy under the infinite system model. More specifically, we show that the push strategy outperforms the pull strategy for any probe rate % > 0 when λ <; φ-1, where φ = (1 +√5)/2 ≈ 1.6180 is the golden ratio. More generally, we show that the push strategy prevails if and only if 2λ <; √(R+1) 2 + 4(R+1) √ (R+1). We also show that under the infinite system model, a hybrid pull-and-push strategy is always inferior to the pure pull or push strategy. The relation between the finite and infinite system model is discussed, and simulation results that validate the infinite system model are provided.Keywords
This publication has 14 references indexed in Scilit:
- Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web servicesPerformance Evaluation, 2011
- A mean field model of work stealing in large-scale systemsACM SIGMETRICS Performance Evaluation Review, 2010
- A class of mean field interaction models for computer and communication systemsPerformance Evaluation, 2008
- Analyses of Load Stealing Models Based on Families of Differential EquationsTheory of Computing Systems, 2000
- Analysis of task migration in shared-memory multiprocessor schedulingACM SIGMETRICS Performance Evaluation Review, 1991
- Adaptive load sharing in heterogeneous distributed systemsJournal of Parallel and Distributed Computing, 1990
- Analysis of the effects of delays on load sharingIEEE Transactions on Computers, 1989
- Uniqueness for Differential Equations Implies continuous Dependence only in Finite DimensionBulletin of the London Mathematical Society, 1986
- A comparison of receiver-initiated and sender-initiated adaptive load sharingPerformance Evaluation, 1986
- Lipschitz type conditionsPublished by Springer Science and Business Media LLC ,1977