The Taub Faculty of Computer Science Events and Talks

Most communication networks exhibit a large variety of links that may differ significantly in terms of the cost incurred for sending messages over them. While this fact is reflected in many centralized network optimization problems, it is not yet taken into account in the design of distributed algorithms: The de facto standard approach for measuring the communication burden of distributed message passing algorithms is to minimize their message complexity — the total number of messages sent by the algorithm, irrespective of the link over which each message has been sent. Motivated by this observation, the goal of the current talk is to extend the classic distributed controller problem [Afek et al. JACM 1996], that provides an abstraction for online management of a global resource in a network, to accommodate heterogeneous edge costs. This extension naturally calls for applying competitive analysis, an evaluation method that is usually missing from the field of distributed algorithms. Abstract optimization problems studied in almost all relevant disciplines, including supply chain and logistics, typically model the network as a graph with different edge costs. Thus the centralized version of the controller problem with heterogeneous edge costs is also interesting.

The talk will be self contained.