Facility Location in Evolving Metrics

David Eisenstat, Claire Mathieu, Nicolas Schabanel

Understanding the dynamics of evolving social or infrastructure networks is a challenge in applied areas such as epidemiology, viral marketing, or urban planning. During the past decade, data has been collected on such networks but has yet to be fully analyzed. We propose to use information on the dynamics of the data to find stable partitions of the network into groups. For that purpose, we introduce a time-dependent, dynamic version of the facility location problem, that includes a switching cost when a client’s assignment changes from one facility to another. This might provide a better representation of an evolving network, emphasizing the abrupt change of relationships between subjects rather than the continuous evolution of the underlying network. We show that in realistic examples this model yields indeed better fitting solutions than optimizing every snapshot independently. We present an O(log nT)-approximation algorithm and a matching hardness result, where n is the number of clients and T the number of time steps. We also give an other algorithms with approximation ratio O(log nT) for the variant where one pays at each time step (leasing) for each open facility.

Guest: Nicolas Schabanel

Host: Stefan Schmid

Parallel Peeling Algorithms

Justin Thaler, Michael Mitzenmacher, Jiayang Jiang

The analysis of several algorithms and data structures can be framed as a peeling
process on a random hypergraph: vertices with degree less than k are removed
until there are no vertices of degree less than k left. The remaining hypergraph
is known as the k-core. In this paper, we analyze parallel peeling processes,
where in each round, all vertices of degree less than k are removed. It is
known that, below a specific edge density threshold, the k-core is empty
with high probability. We show that, with high probability, below this threshold,
only 1 / log((k-1)(r-1)) log log n + O(1) rounds of peeling are needed to obtain
the empty k-core for r-uniform hypergraphs. Interestingly, we show
that above this threshold, Ω(log n) rounds of peeling are required to find the non-empty
k-core. Since most algorithms and data structures aim to peel to an empty k-core,
this asymmetry appears fortunate. We verify the theoretical results both with simulation
and with a parallel implementation using graphics processing units (GPUs). Our
implementation provides insights into how to structure parallel peeling algorithms
for efficiency in practice.

Guest: Michael Mitzenmacher
Host: Stefan Schmid

Balanced Allocations and Double Hashing

Michael Mitzenmacher

With double hashing, for an item x, one generates two hash values f(x) and g(x),
and then uses combinations (f(x) + ig(x)) mod n for i = 0, 1, 2, … to generate
multiple hash values from the initial two. We show that the performance difference between double hashing and fully random hashing appears negligible in the standard balanced allocation paradigm, where each item is placed in the least loaded of
d choices, as well as several related variants. We perform an empirical study,
and consider multiple theoretical approaches. While several techniques can be used to
show asymptotic results for the maximum load, we demonstrate how fluid limit methods
explain why the behavior of double hashing and fully random hashing are essentially
indistinguishable in this context.

Guest: Michael Mitzenmacher
Host: Stefan Schmid

Fault Tolerant Approximate BFS Trees

Merav Parter and David Peleg

Abstract: A fault-tolerant structure for a network is required to continue functioning following the failure of some of the network’s edges or vertices. This paper considers breadth- first search (BFS) spanning trees, and addresses the problem of designing a sparse fault-tolerant BFS tree, or FT-BFS tree for short, namely, a sparse subgraph T of the given network G such that subsequent to the failure of a single edge or vertex, the surviving part T’ of T still contains a BFS spanning tree for (the surviving part of) G. For a source node s, a target node t and an edge e in G, the shortest s-t path P that does not go through e is known as a replacement path. Thus, our FT-BFS tree contains the collection of all replacement paths Ps,t,e for every t in V (G) and every failed edge e in E(G).

Our main results are as follows. We present an algorithm that for every n-vertex graph G and source node s constructs a (single edge failure) FT-BFS tree rooted at s with O(n min(Depth(s), sqrt(n)) edges where Depth(s) is the depth of the BFS tree rooted at s. This result is complemented by a matching lower bound, showing that there exist n-vertex graphs with a source node s for which any edge (or vertex) FT-BFS tree rooted at s has Ω(n3/2) edges. We then consider fault-tolerant multi-source BFS trees, or FT-MBFS trees for short, aiming to provide (following a failure) a BFS tree rooted at each source s in S for some subset of sources. Again, tight bounds are provided, showing that there exists a poly-time algorithm that for every n-vertex graph and source set S of size σ constructs a (single failure) FT-MBFS tree T*(S) from each source si in S, with O(sqrt(σ)n3/2) edges, and on the other hand there exist n-vertex graphs with source sets S of cardinality σ, on which any FT-MBFS tree from S has Ω(sqrt(σ)n3/2) edges.

Finally, we propose an O(log n) approximation algorithm for constructing FT-BFS and FT-MBFS structures. The latter is complemented by a hardness result stating that there exists no (log n) approximation algorithm for these problems under standard complexity assumptions. In comparison with the randomized FT-BFS construction implicit in [14], our algorithm is deterministic and may improve the number of edges by a factor of up to sqrt(n) for some instances. All our algorithms can be extended to deal with one vertex failure as well, with the same performance.

Guest: Merav Parter
Host: Stefan Schmid

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage

Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, and Rocco Servedio

Abstract: We consider a problem which has received considerable attention in systems literature because of its applications to routing in delay tolerant networks and replica placement in distributed storage systems. We provide an additive EPTAS for this problem. Our approach is inspired by, and extends, recent structural results from the complexity-theoretic study of linear threshold functions. Furthermore, in spite of the objective function being non-smooth, we give a unicriterion PTAS while previous work for such objective functions has typically led to a bicriterion PTAS. We believe our techniques may be applicable to get unicriterion PTAS for other non-smooth objective functions.

Guest: Anindya De, Berkeley, USA
Host: Stefan Schmid

Distributed Protocols for Leader Election: a Game-Theoretic Perspective

Ittai Abraham, Danny Dolev, and Joseph Y. Halpern

Abstract. We do a game-theoretic analysis of leader election, under the assumption
that each agent prefers to have some leader than to have no leader at all. We
show that it is possible to obtain a fair Nash equilibrium, where each agent has
an equal probability of being elected leader, in a completely connected network,
in a bidirectional ring, and a unidirectional ring, in the synchronous setting. In
the asynchronous setting, Nash equilibrium is not quite the right solution concept.
Rather, we must consider ex post Nash equilibrium; this means that we
have a Nash equilibrium no matter what a scheduling adversary does. We show
that ex post Nash equilibrium is attainable in the asynchronous setting in all the
networks we consider, using a protocol with bounded running time. However,
in the asynchronous setting, we require that n > 2. We can get a fair e-Nash
equilibrium if n = 2 in the asynchronous setting, under some cryptographic assumptions
(specifically, the existence of a pseudo-random number generator and
polynomially-bounded agents), using ideas from bit-commitment protocols. We
then generalize these results to a setting where we can have deviations by a coalition
of size k. In this case, we can get what we call a fair k-resilient equilibrium
if n > 2k; under the same cryptographic assumptions, we can a get a k-resilient
equilibrium if n = 2k. Finally, we show that, under minimal assumptions, not
only do our protocols give a Nash equilibrium, they also give a sequential equilibrium
[23], so players even play optimally off the equilibrium path.

Guests: Danny Dolev and Joseph Y. Halpern

Host: Stefan Schmid

Atomic snapshots in O(log^3 n) steps using randomized helping

James Aspnes and Keren Censor-Hillel

Abstract: A randomized construction of unbounded snapshots objects
from atomic registers is given. The cost of each snapshot operation is
O(log^3 n) atomic register steps with high probability, where n is the
number of processes, even against an adaptive adversary. This is an exponential
improvement on the linear cost of the previous best known
unrestricted snapshot construction [7, 8] and on the linear lower bound
for deterministic constructions [9], and does not require limiting the number
of updates as in previous sublinear constructions [4]. One of the main
ingredients in the construction is a novel randomized helping technique
that allows out-of-date processes to obtain up-to-date information without
running into covering lower bounds.

Guest: Keren Censor-Hillel

Host: Stefan Schmid

Gossip Protocols for Renaming and Sorting

George Giakkoupis, Anne-Marie Kermarrec, and Philipp Woelfel


Abstract: We devise efficien gossip-based protocols for some fundamental distributed tasks. The protocols assume an n-node network supporting point-to-point communication, and in every round, each node exchanges information of size O(log n) bits with (at most) one other node. We first consider the renaming problem, that is, to assign distinct IDs from a small ID space to all nodes of the network.We propose a renaming protocol that divides the ID space among nodes using a natural push or pull approach, achieving logarithmic round complexity. A variant of this protocol solves the tight renaming problem, where each node obtains a unique ID in {1,…,n}, in O(log^2 n) rounds. Next we study the following sorting problem. Nodes have consecutive IDs 1 up to n, and they receive numerical values as inputs. They then have to exchange those inputs so that in the end the input of rank k is located at the node with ID k. Jelasity and Kermarrec [20] suggested a simple and natural protocol, where nodes exchange values with peers chosen uniformly at random, but it is not hard to see that this protocol requires Omega(n) rounds. We prove that the same protocol works in O(log^2 n) rounds if peers are chosen according to a non-uniform power law distribution.

Guest: George Giakkoupis

Host: Stefan Schmid

Adaptive Register Allocation with a Linear Number of Registers

Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, and Leslie Lamport

Abstract: We give an adaptive algorithm in which processes use multi-
writer multi-reader registers to acquire exclusive write access to their own
single-writer, multi-reader registers. It is the first such algorithm that
uses a number of registers linear in the number of participating processes.
Previous adaptive algorithms require at least O(n^{3/2}) registers.

Guest: Eli Gafni

Host: Stefan Schmid

In-Network Analytics for Ubiquitous Sensing

Ittay Eyal, Idit Keidar, Stacy Patterson, and Raphi Rom

Abstract: We address the problem of in-network analytics for data that is generated by sensors at the edge of the network. Specifically, we consider the problem of summarizing a continuous physical phenomenon, such as temperature or pollution, over a geographic region like a road network. Samples are collected by sensors placed alongside roads as well as in cars driving along them. We divide the region into sectors with a summary for each sector, so that their union is a continuous function that minimizes some global error function. We designate a node (either virtual or physical) that is responsible for estimating the function in each sector. Each node computes its estimate based on the samples taken in its sector and information from adjacent nodes. The algorithm works in networks with bounded, yet unknown, latencies. It accommodates the addition and removal of samples and the arrival and departure of nodes, and it converges to a globally optimal solution using only pairwise message exchanges between neighbors. The algorithm relies on a weakly-fair scheduler to implement these pairwise exchanges, and we present an implementation of such a scheduler. Our scheduler, which may be of independent interest, is locally quiescent, meaning that it only sends messages when required by the algorithm. It achieves quiescence on every link where the algorithm ceases to schedule pairwise exchanges; in particular, if the algorithm converges, it globally quiesces.

Guest: Stacy Patterson

Host: Stefan Schmid