Dr. Abdolhamid Ghodselahi
Ph.D. Student (2012 - 2018)
I moved to "Technische Universität Hamburg". See my new homepage there.
Background
I am a PhD candidate in the Department of Computer Science at the University of Freiburg. I am advised by Prof. Dr. Fabian Kuhn . I have a M.Sc. in Algorithms and Computation from Tehran University. My main advisor was Prof. Dr. Mohammad Ali Safari . I received a Bachelor's degree in Software Engineering from Kharazmi University (previously known as Tarbiat Moallem University of Tehran).
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 to design and analyze online algorithms for such problems, specifically online allocation problems.
Teaching Assistance
Graduate Course "Theoretical Computer Science (Bridge Course)": Summer Semester
2017
Graduate Course "Network Algorithms": Summer Semesters
2014 -
2015 -
2016
Graduate Course "Algorithm Theory": Winter Semesters
12/13 -
13/14 -
14/15 -
15/16 -
16/17
Seminar: Winter Semesters
14/15 -
15/16 -
Summer Semesters
2015 -
2016
Publications
Years: 2020 |
2019 |
2017 |
2015 | show all Journal Papers Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, Anisur Rahaman MollaThe Cost of Global Broadcast in Dynamic Radio Networks 2020 Theor Comput Sci , volume : 806, pages : 363 - 387» show abstract « hide abstract 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. Conference papers Conference papers Abdolhamid Ghodselahi, Fabian KuhnDynamic Analysis of the Arrow Distributed Directory Protocol
in General Networks 2017 31st Symposium on Distributed Computing (DISC) » show abstract « hide abstract Abstract The Arrow protocol is a simple and elegant protocol to coordinate exclusive access to a shared object in a network. The protocol solves the underlying distributed queueing problem by using path reversal on a pre-computed spanning tree (or any other tree topology simulated on top of the given network).
It is known that the Arrow protocol solves the problem with a competitive ratio of O(log D) on trees of diameter D. This implies a distributed queueing algorithm with competitive ratio O(s · log D) for general networks with a spanning tree of diameter D and stretch s. In this work we show that when running the Arrow protocol on top of the well-known probabilistic tree embedding of Fakcharoenphol, Rao, and Talwar [STOC03], we obtain a randomized distributed queueing algorithm with a competitive ratio of O(log n) even on general network topologies. The result holds even if the queueing requests occur in an arbitrarily dynamic and concurrent fashion and even if communication is asynchronous. From a technical point of view, the main of the paper shows that the competitive ratio of the Arrow protocol is constant on a special family of tree topologies, known as hierarchically well separated trees. Conference papers Mohamad Ahmadi, Abdolhamid Ghodselahi, Fabian Kuhn, Anisur Rahaman MollaThe Cost of Global Broadcast in Dynamic Radio Networks 2015 19th Int. Conf. on Principles of Distributed Systems (OPODIS), Rennes, France » show abstract « hide abstract Abstract We study the single-message broadcast problem in dynamic radio
networks. We show that the time complexity of the problem depends on
the amount of stability and connectivity of the dynamic network
topology and on the adaptiveness of the adversary providing the
dynamic topology. More formally, we model communication using the
standard graph-based radio network model. To model the dynamic
network, we use a variant of the synchronous dynamic graph model
introduced in [Kuhn et al., STOC 2010]. For integer parameters
$T\geq 1$ and $k\geq 1$, we call a dynamic graph $T$-interval
$k$-connected if for every interval of $T$ consecutive rounds, there
exists a $k$-vertex-connected stable subgraph. Further, for an
integer parameter $\tau\geq 0$, we say that the adversary providing
the dynamic network is $\tau$-oblivious if for constructing the
graph of some round $t$, the adversary has access to all the
randomness (and states) of the algorithm up to round $t-\tau$.
As our main result, we show that for any $T\geq 1$, any $k\geq 1$,
and any $\tau\geq 1$, for a $\tau$-oblivious adversary, there is a
distributed algorithm to broadcast a single message in time
$O\big(\big(1+\frac{n}{k\cdot \min \set{\tau,T}} \big ) \cdot n \log^3
n \big)$. We further show that even for large interval
$k$-connectivity, efficient broadcast is not possible for the usual
adaptive adversaries. For a $1$-oblivious adversary, we show that
even for any $T\leq (n/k)^{1-\eps}$ (for any constant $\eps > 0$) and for
any $k\geq 1$, global broadcast in $T$-interval $k$-connected
networks requires at least $\Omega(n^2/k^2\log n)$ time. Further,
for a $0$-oblivious adversary, broadcast cannot be solved in
$T$-interval $k$-connected networks as long as $T<n-k$. Abdolhamid Ghodselahi, Fabian KuhnServing Online Requests with Mobile Servers 2015 26th Int. Symp. on Algorithms and Computation (ISAAC), Nagoya, Japan » show abstract « hide abstract Abstract We study an online problem in which mobile servers have to be moved
in order to efficiently serve a set of online requests. More
formally, there is a set of n nodes and a set of k mobile
servers that are placed at some of the nodes. Each node can
potentially host several servers and the servers can be moved
between the nodes. There are requests 1,2, ... that are
adversarially issued at nodes one at a time, where a request issued
at time t needs to be served at all times t' ≥ t. The cost
for serving the requests is a function of the number of servers and
requests at the different nodes. The requirements on how to serve
the requests are governed by two parameters ɑ ≥ 1 and
β ≥ 0. An algorithm needs to guarantee that at all times,
the total service cost remains within a multiplicative factor
of ɑ and an additive term β of the current optimal service
cost.
We consider online algorithms for two different minimization
objectives. We first consider the natural problem of minimizing the
total number of server movements. We show that in this case for
every k, the competitive ratio of every deterministic online
algorithm needs to be at least Ω(n). Given this negative
result, we then extend the minimization objective to also include
the current service cost. We give almost tight bounds on the
competitive ratio of the online problem where one needs to minimize
the sum of the total number of movements and the current service
cost. In particular, we show that at the cost of an additional
additive term which is roughly linear in k, it is possible to
achieve a multiplicative competitive ratio of 1+ε for every
constant ε>0.