Hajek, Bruce Balanced loads in infinite networks. (English) Zbl 0863.60099 Ann. Appl. Probab. 6, No. 1, 48-75 (1996). Summary: A set of nodes and a set of consumers are given, and to each consumer there corresponds a subset of the nodes. Each consumer has a demand, which is a load to be distributed among the nodes corresponding to the consumer. The load at a node is the sum of the loads placed on the node by all consumers. The load is balanced if no single consumer can shift some load from one node to another to reduce the absolute difference between the total loads at the two nodes. The model provides a setting to study the performance of load balancing as an allocation strategy in large systems. The set of possible balanced load vectors is examined for infinite networks with deterministic or random demands. The balanced load vector is shown to be unique for rectangular lattice networks, and a method for computing the load distribution is explored for tree networks. An FKG-type inequality is proved. The concept of load percolation is introduced and is shown to be associated with infinite sets of nodes with identical load. Cited in 3 Documents MSC: 60K35 Interacting random processes; statistical mechanics type models; percolation theory 60G60 Random fields 60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.) 60C05 Combinatorial probability Keywords:load balancing; percolation; assignment problem PDFBibTeX XMLCite \textit{B. Hajek}, Ann. Appl. Probab. 6, No. 1, 48--75 (1996; Zbl 0863.60099) Full Text: DOI References: [1] ALANy ALI, M. and HAJEK, B. 1995. Analy sis of simple algorithms for dy namic load balancing. Unpublished manuscript. [2] ESARY, J. D., PROSCHAN, F. and WALKUP, D. W. 1967. Association of random variables, with applications. Ann. Math. Statist. 38 1466 1474. · Zbl 0183.21502 · doi:10.1214/aoms/1177698701 [3] GIBBENS, R. J., KELLY, F. P. and TURNER, S. R. E. 1993. Dy namic routing in multiparented networks. IEEE Trans. Networking 1 261 270. [4] GRIMMETT, G. 1989. Percolation. Springer, New York. · Zbl 0691.60089 [5] HAJEK, B. 1990. Global load balancing by local adjustment. IEEE Trans. Inform. Theory 36 1398 1414. · Zbl 0716.90065 · doi:10.1109/18.59935 [6] TURNER, S. 1993. Personal communication. [7] URBANA, ILLINOIS 61801 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.