Distributed Minimum Cut Approximation


We study the problem of computing approximate minimum edge cuts by distributed algorithms. We present two randomized approximation algorithms that both run in a standard synchronous message passing model where in each round, $O(log n)$ bits can be transmitted over every edge (a.k.a. the CONGEST model). The first algorithm is based on a simple and new approach for analyzing random edge sampling, which we call random layering technique. For any any weighted graph and any $\epsilon \in (0, 1)$, the algorithm finds a cut of size at most $O(\epsilon^{-1}\lambda)$ in $O(D) + \tilde{O}(n^{1/2 + \epsilon})$ rounds, where $\lambda$ is the minimum-cut size and the $\tilde{O}$-notation hides poly-logarithmic factors in $n$. In addition, using the outline of a centralized algorithm due to Matula [SODA '93], we present a randomized algorithm to compute a cut of size at most $(2+\epsilon)\lambda$ in $\tilde{O}((D+\sqrt{n})/\epsilon^5)$ rounds for any $\epsilon>0$. The time complexities of our algorithms almost match the $\tilde{\Omega}(D + \sqrt{n})$ lower bound of Das Sarma et al. [STOC '11], thus leading to an answer to an open question raised by Elkin [SIGACT-News '04] and Das Sarma et al. [STOC '11].
To complement our upper bound results, we also strengthen the $\tilde{\Omega}(D + \sqrt{n})$ lower bound of Das Sarma et al. by extending it to unweighted graphs. We show that the same lower bound also holds for unweighted multigraphs (or equivalently for weighted graphs in which $O(w\log n)$ bits can be transmitted in each round over an edge of weight $w$). For unweighted simple graphs, we show that computing an $\alpha$-approximate minimum cut requires time at least $\tilde{\Omega}(D + \sqrt{n}/\alpha^{1/4})$.

Guest: Mohsen Ghaffari (Electrical Engineering and Computer Science Department, Massachusetts Institute of Technology)

Host: Merav Parter

Metastability of Logit Dynamics for Coordination Games

Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale, Giuseppe Persiano


Logit Dynamics [Blume, Games and Economic Behavior, 1993] is a randomized best response dynamics for strategic games: at every time step a player is selected uniformly at random and she chooses a new strategy according to a probability distribution biased toward strategies promising higher payoffs. This process defines an ergodic Markov chain, over the set of strategy profiles of the game, whose unique stationary distribution is the long-term equilibrium concept for the game. However, when the mixing time of the chain is large (e.g. exponential in the number of players), the stationary distribution loses its appeal as equilibrium concept, and the transient phase of the Markov chain becomes important. In several cases it happens that on a time-scale shorter than mixing time the chain is “quasi-stationary”, meaning that it stays close to some small set of the state space, while in a time-scale multiple of the mixing time it jumps from one quasi-stationary configuration to another; this phenomenon is usually called “metastability”.
In this paper we give a quantitative definition of “metastable probability distributions” for a Markov chain and we study the metastability of the Logit dynamics for some classes of coordination games. In particular, we study no-risk-dominant coordination games on the clique (which is equivalent to the well-known Glauber dynamics for the Ising model) and coordination games on a ring (both the risk-dominant and no-risk-dominant case). We also describe a simple “artificial” game that highlights the distinctive features of our metastability notion based on distributions.

Guest: Francesco Pasquale

Host: Merav Parter

Wireless Connectivity and Capacity

Magnus M. Halldorsson, Pradipta Mitra


Given $n$ wireless transceivers located in a plane, a fundamental problem in wireless communications is to construct a strongly connected digraph on them such that the constituent links can be scheduled in fewest possible time slots, assuming the SINR model of interference.
In this paper, we provide an algorithm that connects an arbitrary point set in $O(\log n)$ slots, improving on the previous best bound of $O(\log^2 n)$ due to Moscibroda. This is complemented with a super-constant lower bound on our approach to connectivity. An important feature is that the algorithms allow for bi-directional (half-duplex) communication.
One implication of this result is an improved bound of $\Omega(1/\log n)$ on the worst-case capacity of wireless networks, matching the best bound known for the extensively studied average-case.
We explore the utility of oblivious power assignments, and show that essentially all such assignments result in a worst case bound of $\Omega(n)$ slots for connectivity. This rules out a recent claim of a $O(\log n)$ bound using oblivious power. On the other hand, using our result we show that $O(\min(\log \Delta, \log n \cdot (\log n + \log \log \Delta)))$ slots suffice, where $\Delta$ is the ratio between the largest and the smallest links in a minimum spanning tree of the points.
Our results extend to the related problem of minimum latency aggregation scheduling, where we show that aggregation scheduling with $O(\log n)$ latency is possible, improving upon the previous best known latency of $O(\log^3 n)$. We also initiate the study of network design problems in the SINR model beyond strong connectivity, obtaining similar bounds for biconnected and $k$-edge connected structures.

Guest: Magnus M. Halldorsson

Host: Merav Parter

Locality and checkability in wait-free computing

Pierre Fraigniaud, Sergio Rajsbaum and Corentin Travers

This paper studies  notions of locality that are inherent to the specification of a
distributed task and independent of the computing environment, in a shared
memory wait-free system.
A  task T =(I,O,D) is checkable if there exists a wait-free distributed algorithm that, given s in I and t in O,  determines whether t in D(s), i.e., if t is a valid output for s according to
the specification D of T. Determining whether a projection-closed task is
wait-free solvable remains undecidable, demonstrating the richness of this
class. A locality property called projection-closed is identified,  that completely characterizes tasks that are wait-free  checkable.
A stronger notion of locality considers tasks  where the outputs look identically to the inputs at every vertex (input value of  a process). A task T =(I,O,D)  is said to be locality-preserving} if  O is a  covering complex of I. This topological property yields obstacles for wait-free  solvability different in nature from the classical agreement impossibility
results. On the other hand, locality-preserving tasks are projection-closed and
therefore always wait-free checkable.  A classification of locality-preserving
tasks in term of their relative computational power is provided.
A correspondence between locality-preserving tasks and subgroups of the edgepath
group of an input complex shows the existence of  hierarchies of  locality-preserving tasks, each one containing at the top the universal task  (induced by the universal covering complex), and at the bottom the trivial identity task.
Guest: Pierre Fraigniaud
Host: Merav Parter

Oblivious Collaboration

Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial and Benny Sudakov.

Communication is a crucial ingredient in every kind of collaborative work. But what is the least possible amount of communication required for a given task? We formalize
this question by introducing a new framework for distributed computation, called
oblivious protocols.
We investigate the power of this model by considering two concrete examples, the musical chairs task MC(n,m) and the well-known Renaming problem. The MC(n,m) game is played by n players (processors) with $m$ chairs. Players can occupy chairs, and the game terminates as soon as each player occupies a unique chair. Thus we say that player P is in conflict if some other player Q is occupying the same chair, i.e., termination means there are no conflicts. By known results from distributed computing, if m <= 2n-2, no strategy of the players can guarantee termination. However, there
is a protocol with m = 2n-1 chairs that always terminates. Here we consider an
oblivious protocol where in every time step the only communication is this: an
adversarial scheduler chooses an arbitrary nonempty set of players, and for each
of them provides only one bit of information, specifying whether the player is
currently in conflict or not. A player notified not to be in conflict halts and
never changes its chair, whereas a player notified to be in conflict changes its
chair according to its deterministic program. Remarkably, even with this minimal
communication termination can be guaranteed with only m=2n-1 chairs. Likewise,
we obtain an oblivious protocol for the Renaming problem whose name-space is
small as that of the optimal nonoblivious distributed protocol.
Other aspects suggest themselves, such as the efficiency
(program length) of our protocols. We make substantial progress here as well,
though many interesting questions remain open.

Guest: Eli Gafni
Host: Merav Parter

On Approximate Distance Labels and Routing Schemes with Affine Stretch

Ittai Abraham and Cyril Gavoille


For every integral parameter k > 1, given an unweighted
graph G, we construct in polynomial time, for each vertex u, a distance label
L(u) of size O(n^(2/(2k-1))). For any u,v in G, given L(u),L(v) we can return in
time O(k) an affine approximation h(u,v) on the distance d(u,v) between u and v
in G such that d(u,v) <= h(u,v) <= (2k-2)d(u,v) +1. Hence we say that our
distance label scheme has affine stretch of (2k-2)d+1.  For k=2 our construction
is comparable to the O(n^(5/3)) size, 2d+1 affine stretch of the distance oracle
of Patrascu and Roditty (FOCS’10), it incurs a o(log(n)) storage overhead while
providing the benefits of a distance label.

For any k>1, given a restriction of o(n^(1+1/(k-1))) on
the total size of the data structure, our construction provides distance
labels with affine stretch of (2k-2)d+1 which is better than the stretch (2k-1)d
scheme of Thorup and Zwick (J. ACM’05).

Our second contribution is a compact routing scheme with
poly-logarithmic addresses that provides affine stretch guarantees. With
O(n^(3/(3k-2)))-bit routing tables we obtain affine stretch of (4k-6)d+1, for
any k>1.

Given a restriction of o(n^(1/(k-1))) on the table size,
our  routing scheme provides affine stretch which is better than the stretch
(4k-5)d routing scheme of Thorup and Zwick (SPAA’01).

Guest: Ittai Abraham

Host:  Merav Parter


Parsimonious Flooding in Geometric Random-Walks

Andrea Clementi and Riccardo Silvestri

We study the information spreading yielded by the (Parsimonious) 1-Flooding
Protocol} in geometric Mobile Ad-Hoc Networks. We consider n agents on a convex
plane region of diameter D performing independent random walks with move radius
\rho. At any time step, every active agent $v$ informs every non-informed agent
which is within distance R from v (R>0 is the transmission radius). An agent
is only active at the time step immediately after the one in which has been
informed and, after that, she is removed. At the initial time step, a source
agent is informed and we look at the \emph{completion time} of the protocol,
i.e., the first time step (if any) in which all agents are informed. This random
process is equivalent to the well-known Susceptible-Infective-Removed (SIR)
infection process in Mathematical Epidemiology. No analytical results are
available for this random process over any explicit mobility model. The presence
of removed agents makes this process much more complex than the (standard)
flooding. We prove optimal bounds on the completion time depending on the
parameters n, D, R, and rho. The obtained bounds hold with high probability. We
remark that our method of analysis provides a clear picture of the dynamic shape
of the information spreading (or infection wave) over the time.
end of abstract.
Guest: Andrea Clementi

Host:  Merav Parter