Load Balancing White Papers
Online Client-Server Load Balancing Without Global Information
Overview A distributed online algorithm is considered for maximizing throughput in a network of clients and servers, modeled as a bipartite graph. Unlike most prior work on online load balancing, it do not assume centralized control and seek algorithms and lower bounds for decentralized algorithms in which each participant has only local knowledge about the state of itself and its neighbors. This problem can be seen as analogous to the recent work on oblivious routing in, but with the objective of maximizing throughput rather than minimizing congestion. In contrast to that work, it proves a strong lower bound (polynomial in n, the size of the graph) on the competitive ratio of any oblivious algorithm.
| Publisher | Johns Hopkins University | File Format | |
|---|---|---|---|
| Date Published | January 2008 | ||
| Format | White Papers | ||
| Topics | |||
-
Did you find this white paper useful? 2 out of 3 users found this white paper useful
White Paper RSS
Download
Register
