*Proceedings of The 30th International Symposium on Algorithms and Computation (ISAAC 2019), LIPIcs, Vol. 149*, December 2019. Shanghai, China.

# Abdolhamid Ghodselahi

Dr. Abdolhamid Ghodselahi

## Research Interests

I am generally interested in combinatorial optimization and approximation algorithms. In particular, I mainly study problems that could have online nature in both distributed and centralized systems. I am interested in designing and analyzing online algorithms for such problems, especially online allocation problems.

## Short CV

I am a Postdoc researcher at the Hamburg University of Technology and working with Prof. Dr. Volker Turau since August 2018. I was a PhD student at the University of Freiburg under supervision of Prof. Dr. Fabian Kuhn. I have an M.Sc. in Algorithms and Computation from University of Tehran. My supervisor was Prof. Dr. Mohammad Ali Safari.

## Projects

- ToleranceZone - Fault tolerant middle-ware idioms based on self-stabilizing techniques

## Publications

Abdolhamid Ghodselahi, Fabian Kuhn and Volker Turau. Concurrent Distributed Serving with Mobile Servers. In

@InProceedings{Telematik_ISAAC_2019,
author = {Abdolhamid Ghodselahi and Fabian Kuhn and Volker Turau},
title = {Concurrent Distributed Serving with Mobile Servers},
booktitle = {Proceedings of The 30th International Symposium on Algorithms and Computation (ISAAC 2019), LIPIcs, Vol. 149},
pages = ,
day = {8-11},
month = dec,
year = 2019,
location = {Shanghai, China},
}

**Abstract**: This paper introduces a new resource allocation problem in distributed computing called distributed serving with mobile servers (DSMS). In DSMS, there are k identical mobile servers residing at the processors of a network. At arbitrary points of time, any subset of processors can invoke one or more requests. To serve a request, one of the servers must move to the processor that invoked the request. Resource allocation is performed in a distributed manner since only the processor that invoked the request initially knows about it. All processors cooperate by passing messages to achieve correct resource allocation. They do this with the goal to minimize the communication cost. Routing servers in large-scale distributed systems requires a scalable location service. We introduce the distributed protocol Gnn that solves the DSMS problem on overlay trees. We prove that Gnn is starvation-free and correctly integrates locating the servers and synchronizing the concurrent access to servers despite asynchrony, even when the requests are invoked over time. Further, we analyze Gnn for "one-shot" executions, i.e., all requests are invoked simultaneously. We prove that when running Gnn on top of a special family of tree topologies - known as hierarchically well-separated trees (HSTs) - we obtain a randomized distributed protocol with an expected competitive ratio of O(log n) on general network topologies with n processors. From a technical point of view, our main result is that Gnn optimally solves the DSMS problem on HSTs for one-shot executions, even if communication is asynchronous. Further, we present a lower bound of Omega(max {k, log n/log log n}) on the competitive ratio for DSMS. The lower bound even holds when communication is synchronous and requests are invoked sequentially.

Abdolhamid Ghodselahi, Fabian Kuhn and Volker Turau.

*Competitive Concurrent Distributed Scheduling*. Technical Report arxiv:1902.07354, arXiv.org e-Print Archive - Computing Research Repository (CoRR), Cornell University, February 2019.@TechReport{Telematik_DSMS_2019,
author = {Abdolhamid Ghodselahi and Fabian Kuhn and Volker Turau},
title = {Competitive Concurrent Distributed Scheduling},
number = {arxiv:1902.07354},
institution = {arXiv.org e-Print Archive - Computing Research Repository (CoRR)},
address = {Cornell University},
month = feb,
year = 2019,
}

**Abstract**: We introduce a new scheduling problem in distributed computing that we call the DSMS problem. We are given a set of k ≥ 1 mobile identical servers that are initially hosted by some processors of the given network. Further, we are given a set of requests that are issued by the processors possibly at any time in an online fashion, and the servers must serve them. A request must be scheduled before the request is served. The delay for scheduling a request is the time taken since the request is issued until it is scheduled. The goal is to minimize the average delay. Navigating mobile servers in a large-scale distributed system needs a scalable location service. We devise the distributed GNN protocol, a novel linked-reversal-based protocol for the DSMS problem that works on overlay trees. We prove that GNN is a starvation-free protocol that correctly integrates locating the servers and synchronizing the concurrent access to the servers despite asynchrony. Further, we analyze the GNN protocol for one-shot executions where all requests are simultaneously issued. We show that when running the GNN protocol on top of a special family of tree topologies---known as hierarchically well-separated trees (HSTs)---we obtain a randomized distributed protocol with an expected competitive ratio of O(log n) on general network topologies for the DSMS problem where n is the number of processors in the given network. From a technical point of view, the main result of our paper shows that the GNN protocol optimally solves the DSMS problem on HSTs for one-shot executions. Our results hold even if communication is asynchronous.

Abdolhamid Ghodselahi.

*Serving Online Requests with Mobile Resources*. PhD Thesis, University of Freiburg, Freiburg, Germany, 2018.@PhdThesis{Ghodselahi_2018_Diss,
author = {Abdolhamid Ghodselahi},
title = {Serving Online Requests with Mobile Resources},
school = {University of Freiburg},
address = {Freiburg, Germany},
year = 2018,
}

**Abstract**: Resource allocation problems have a large variety of applications in different areas of computer science and operations research. A resource allocation problem seeks to find an optimal allocation of a given type of expensive or limited resource to a set of clients that request the services of the given resource. Some of these problems have an online nature: The requests sequence is not revealed at the beginning, but the requests arrive in an online fashion. An algorithm for an online resource allocation problem must make its decision in response to a newly arriving request in an online fashion, i.e., typically before the subsequent request arrives. Depending on the definition of an online resource allocation problem, it might be allowed to postpone serving a request or to change an already made decision. However in this case, postponing a service and changing a decision come at a cost. In this thesis, we also study online allocation problems in the distributed setting, where in contrast to a centralized system, there is no central unit that controls everything and that is aware of the global state of the system. In addition to the uncertainty about the request sequence arising from the online arrivals, there is also uncertainty at each node in the network because the node does not directly learn about requests arriving in other parts of the network. The nodes of a distributed system therefore need to communicate in order to coordinate their actions and one typically assumes that this communication does not come for free. Two online problems are mainly studied in this thesis. First, we consider the distributed queuing problem as a basic problem that coordinates mutually exclusive access to shared data in distributed systems. We devise a randomized distributed queuing algorithm with an expected competitive ratio of O(log n) on general network topologies. We utilize the well-known probabilistic tree embedding of Fakcharoenphol, Rao, and Talwar [STOC 2003] that approximates the distances of a general metric space by mapping it to a special family of tree topologies known as hierarchically well-separated trees and often just referred to as HSTs. Our randomized distributed queuing algorithm is obtained by running the ARROW algorithm—a well-known distributed queuing algorithm—on top of the HST that is produced by applying the above embedding to the distances of the underlying network. It is shown that (under some assumptions) the simple and elegant ARROW algorithm outperforms all existing significantly more complicated distributed queueing algorithms. The second main problem that is studied in a centralized setting is the online facility location problem. We introduce the online mobile facility location (OMFL) problem, where the facilities are mobile. A lower bound for the OMFL problem that even holds on uniform metrics is provided. A natural approach to solve the OMFL problem for general metric spaces is to again use the above embedding into an HST and to directly solve the OMFL problem on HSTs. In this thesis, we provide a first step in this direction by solving a generalized version of the OMFL problem on uniform metrics. A simple deterministic online algorithm is devised and a tight analysis is provided for the algorithm. The second step remains as an open question. We further introduce and study another variant of the OMFL problem that is closer to the k-server problem, arguably one of the most influential problem in the area of online algorithms and competitive analysis.

The complete list of publications is available separately.