Technical Report MSC-2006-14

Title: A Local Facility Location Algorithm for Large-Scale Distributed Systems
Authors: Denis Krivitski
Supervisors: Assaf Schuster
Abstract: In the facility location problem we are given a set of facilities and a set of clients, each of which is to be served by one facility. The goal is to decide which subset of facilities to open, such that the clients will be served at a minimal cost.

We investigate the facility location problem in a distributed setting. In this setting, the set of clients is partitioned among system nodes, the set of facilities is globally known, and eventually every node should have the solution. This setting typifies large scale distributed systems, such as peer-to-peer file sharing networks, and grid systems. All of them need to perform network organization, data placement, collective power management, and other tasks of this kind.

We propose a local algorithm that solves FLP in a distributed setting. Communication and time complexity of the algorithm we present, does not depend on the network size, which make it infinitely scalable. In addition, the algorithm is entirely decentralized, requires no routing capabilities, and is able to process constantly changing data. We simulate the algorithm on networks of thousands nodes, and assess its scalability, communication complexity, and the ability to process dynamic data.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2006
To the main CS technical reports page

Computer science department, Technion