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
Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn and Anisur Rahaman Molla. The cost of global broadcast in dynamic radio networks. Theoretical Computer Science, February 2020.
@Article{Theoretical_computer_science_global_broadcast_2019,
author = {Mohamad Ahmadi and Abdolhamid Ghodselahi and Fabian Kuhn and Anisur Rahaman Molla},
title = {The cost of global broadcast in dynamic radio networks},
pages = ,
journal = {Theoretical Computer Science},
publisher = {Elsevier},
month = feb,
year = 2020,
}
Abstract:
We study the time complexity of single and multi token broadcast in adversarial dynamic radio networks. Initially, k tokens (which are k pieces of information) are distributed among the n nodes of a network and all the tokens need to be disseminated to all the nodes in the network. We first consider the single-token broadcast problem (i.e., the case k=1). By presenting upper and lower bounds, we show that the time complexity of single-token broadcast depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. Then, we give two generic algorithms which allow to transform generalized forms of single-token broadcast algorithms into multi-token broadcast (k-token broadcast) algorithms. Based on these generic algorithms, we obtain k-token broadcast algorithms for a number of different dynamic network settings. For one of the modeling assumptions, our algorithm is complemented by a lower bound which shows that the upper bound is close to optimal.
Abdolhamid Ghodselahi, Fabian Kuhn and Volker Turau. Concurrent Distributed Serving with Mobile Servers. In Proceedings of The 30th International Symposium on Algorithms and Computation (ISAAC 2019), LIPIcs, Vol. 149, December 2019. Shanghai, China.
@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. Concurrent Distributed Serving with Mobile Servers. Technical Report arxiv:1902.07354, arXiv.org e-Print Archive - Computing Research Repository (CoRR), Cornell University, November 2019.
@TechReport{Telematik_DSMS_2019,
author = {Abdolhamid Ghodselahi and Fabian Kuhn and Volker Turau},
title = {Concurrent Distributed Serving with Mobile Servers},
number = {arxiv:1902.07354},
institution = {arXiv.org e-Print Archive - Computing Research Repository (CoRR)},
address = {Cornell University},
month = nov,
year = 2019,
}
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.
The complete list of publications is available separately.