Locally Optimal Load BalancingReportar como inadecuado

Locally Optimal Load Balancing - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 ENS Cachan - École normale supérieure - Cachan 2 Department of Information and Computer Science Aalto

Abstract : This work studies distributed algorithms for locally optimal load-balancing: We are given a graph of maximum degree ∆, and each node has up to L units of load. The task is to distribute the load more evenly so that the loads of adjacent nodes differ by at most 1. If the graph is a path ∆ = 2, it is easy to solve the fractional version of the problem in OL communication rounds, independently of the number of nodes. We show that this is tight, and we show that it is possible to solve also the discrete version of the problem in OL rounds in paths. For the general case ∆ > 2, we show that fractional load balancing can be solved in polyL,∆ rounds and discrete load balancing in fL,∆ rounds for some function f, independently of the number of nodes.

Autor: Laurent Feuilloley - Juho Hirvonen - Jukka Suomela -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados