M.Sc Thesis

M.Sc StudentKrivitski Denis
SubjectA Local Facility Location Algorithm for Large-Scale
Distributed Systems
DepartmentDepartment of Computer Science
Supervisor PROF. Assaf Schuster


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.