Access Restriction

Author Kameda, Hisao ♦ Pourtallier, Odile
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2002
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Braess paradox ♦ Nash equilibrium ♦ Wardrop equilibrium ♦ Distributed decision ♦ Homogeneous distributed system ♦ Load balancing ♦ Noncooperative game ♦ Performance optimization
Abstract In completely symmetric systems that have homogeneous nodes (hosts, computers, or processors) with identical arrival processes, an optimal static load balancing scheme does not involve the forwarding of jobs among nodes. Using an appropriate analytic model of a distributed computer system, we examine the following three decision schemes for load balancing: completely distributed, intermediately distributed, and completely centralized. We show that there is no forwarding of jobs in the completely centralized and completely distributed schemes, but that in an intermediately distributed decision scheme, mutual forwarding of jobs among nodes is possible, leading to degradation in system performance for every decision maker. This result appears paradoxical, because by adding communication capacity to the system for the sharing of jobs between nodes, the overall system performance is degraded. We characterize conditions under which such paradoxical behavior occurs, and we give examples in which the degradation of performance may increase without bound. We show that the degradation reduces and finally disappears in the limit as the intermediately distributed decision scheme tends to a completely distributed one.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2002-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 49
Issue Number 3
Page Count 27
Starting Page 407
Ending Page 433

Open content in new tab

   Open content in new tab
Source: ACM Digital Library