**Guest:** Arne Ludwig

**Host:** Yvonne-Anne Pignolet

**Guest:** Merav Parter

**Host:** Yvonne-Anne Pignolet

**Guest:** Nicolas Schabanel

**Host:** Stefan Schmid

In this paper we consider a related process which we call two-sample voting: every vertex chooses two random neighbours in each step. If the opinions of these neighbours coincide, then the vertex revises its opinion according to the chosen sample. Otherwise, it keeps its own opinion. We consider the performance of this process in the case where two di?erent opinions reside on vertices of some (arbitrary) sets A and B, respectively. Here, |A|+|B|=n is the number of vertices of the graph.

We show that there is a constant K such that if the initial imbalance between the two opinions is of a certain value then with high probability two sample voting completes in a random d regular graph in O(logn) steps and the initial majority opinion wins. We also show the same performance for any regular graph, for some bounds of the second largest eigenvalue of the transition matrix. In the graphs we consider, standard pull voting requires Ω(n) steps, and the minority can still win with probability |B|/n.

**Guest**: Robert Elsässes, Universität Salzburg, http://uni-salzburg.at/index.php?id=53909

**Host**: Yvonne-Anne Pignolet

In this paper, we suggest and analyze a slightly simplified model. It focuses on the assignment of shared continuous resources to the processors. The job assignment to processors and the ordering of the jobs have already been fixed. It is shown that, even for unit size jobs, finding an optimal solution is NP-hard if the number of processors is part of the input. Positive results for unit size jobs include an efficient optimal algorithm for 2 processors. Moreover, we prove that *balanced* schedules yield a 2-*1/m*-approximation for a fixed number of processors. Such schedules are computed by our GreedyBalance algorithm, for which the bound is tight.

**Guest**: Sören Riechers, Universität Paderborn, https://www.hni.uni-paderborn.de/alg/mitarbeiter/soerenri/

**Host**: Yvonne-Anne Pignolet

process on a random hypergraph: vertices with degree less than

until there are no vertices of degree less than

is known as the

where in each round, all vertices of degree less than

known that, below a specific edge density threshold, the

with high probability. We show that, with high probability, below this threshold,

only

the empty

that above this threshold,

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.

and then uses combinations

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

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.

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 Ω(n^{3/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 s_{i} in S, with O(sqrt(σ)n^{3/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(σ)n^{3/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

]]>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

]]>——– SODA 2014 ————

Title: An Optimal Lower Bound for Distinct Elements in the Message Passing Model

Abstract: In the message-passing model of communication, there are k players each with their own private input, who try to compute or approximate a function of their inputs by sending messages to one another over private channels. We consider the setting in which each player holds a subset S_i of elements of a universe of size n, and their goal is to output a (1+\eps)-approximation to the total number of distinct elements in the union of the sets S_i with constant probability, which can be amplified by independent repetition. This problem has applications in data mining, sensor networks, and network monitoring. We resolve the communication complexity of this problem up to a constant factor, for all settings of n, k and \eps, by showing a lower bound of \Omega(k \cdot \min(n, 1/\eps^2) + k \log n) bits. This improves upon previous results, which either had non-trivial restrictions on the relationships between the values of n, k and \eps, or were suboptimal by logarithmic factors, or both.

———- DISC 2013 —————–

Title: When Distributed Computation is Communication Expensive

Abstract: We consider a number of fundamental statistical and graph problems in the message-passing model, where we have k machines (sites), each holding a piece of data, and the machines want to jointly solve a problem defined on the union of the k data sets. The communication is point-to-point, and the goal is to minimize the total communication among the k machines. This model captures all point-to-point distributed computational models with respect to minimizing communication costs. Our analysis shows that exact computation of many statistical and graph problems in this distributed setting requires a prohibitively large amount of communication, and often one cannot improve upon the communication of the simple protocol in which all machines send their data to a centralized server. Thus, in order to obtain protocols that are communication-efficient, one has to allow approximation, or investigate the distribution or layout of the data sets.

Guest: Qin Zhang

Host: Yvonne-Anne Pignolet

]]>**Guest**: David Harris

**Host**: Yvonne-Anne Pignolet

We study the convergence of influence networks, where each node changes its state according to the majority of its neighbors. Our main result is a new bound on the convergence time in the synchronous model, solving the classic “Democrats and Republicans” problem. Furthermore, we give a bound for the sequential model in which the sequence of steps is given by an adversary and a bound for the sequential model in which the sequence of steps is given by a benevolent process.

Guest: Barbara Keller

Host: Shantanu Das

]]>Guest: James Hegeman

Host: Yvonne-Anne Pignolet

Our main result is that efficient distributed algorithms from sleeping-expert regret learning can be used to obtain constant-factor approximations if channel availability is stochastic and independently distributed among links. In general, sublinear approximation factors cannot be obtained without the assumption of stochastic independence among links. A direct application of the no-external regret property is not sufficient to guarantee small approximation factors.

Guest: Johannes Dams

Host: Yvonne-Anne Pignolet

On first glance, it seems that broadcast-based information diffusion is a “blunt” targeting mechanism, and must necessarily suffer from low precision. Somewhat surprisingly, we present preliminary experimental and analytical evidence to the contrary: it is possible to simultaneously have high precision (i.e. is bounded below by a constant), high recall, and low diameter!

We start by presenting a set of conditions on the structure of user interests, and analytically show the necessity of each of these conditions for obtaining high precision. We also present preliminary experimental evidence from Twitter verifying that these conditions are satisfied. We then prove that the Kronecker-graph based generative model of Leskovec et al. satisfies these conditions given an appropriate and natural definition of user interests. Further, we show that this model also has high precision, high recall, and low diameter. We finally present preliminary experimental evidence showing Twitter has high precision, validating our conclusion. This is perhaps a first step towards a formal understanding of the immense popularity of online social networks as an information dissemination mechanism.

Guest: Aneesh Sharma

Host: Yvonne-Anne Pignolet

Guest: David Garcia

Host: Yvonne-Anne Pignolet

]]>

Frequency hopping is a central method in wireless communication, offering improved resistance to adversarial interference and interception attempts, and easy non-coordinated control in dynamic environments. In this paper, we introduce a new model that supports a rigorous study of frequency hopping in adversarial settings. We then propose new frequency hopping protocols that allow a sender-receiver pair to essentially use the full communication capacity, despite a powerful adversary that can scan and jam a significant amount of the ongoing transmissions.

```
Guest: Yuval Emek
```

```
Host: Zvi Lotker
```

]]>Guest: Bojun Huang

Host Prof. Zvi Lotker

In this paper we initiate this line of work by comparing various notions of equilibria (particularly Nash equilibria and no-regret behavior) when using a supposedly “better” technology. We show a version of Braess’s Paradox for all of them: in certain networks, upgrading technology can actually make the equilibria \emph{worse}, despite an increase in the capacity. We construct instances where this decrease is a constant factor for power control, interference cancellation, and improvements in the SINR threshold beta, and is Omega(log Delta) when power control is combined with interference cancellation. However, we show that these examples are basically tight: the decrease is at most O(1)for power control, interference cancellation, and improved beta, and is at most

O(log Delta) when power control is combined with interference cancellation.

O(log Delta) when power control is combined with interference cancellation.

Guest: Michael Dinitz

Host: Yvonne-Anne Pignolet

]]>We present a deterministic obstruction-free implementation of leader election from O(n^{1/2}) atomic O(log n)-bit registers in the stan- dard asynchronous shared memory system with n processes. We provide also a technique to transform any deterministic obstruction-free algo- rithm, in which any process can finish if it runs for b steps without interference, into a randomized wait-free algorithm for the oblivious ad- versary, in which the expected step complexity is polynomial in n and b. This transformation allows us to combine our obstruction-free algo- rithm with the leader election algorithm by Giakkoupis and Woelfel [21], to obtain a fast randomized leader election (and thus test-and-set) im- plementation from O(n^{1/2}) O(log n)-bit registers, that has expected step complexity O(log n) against the oblivious adversary. Our algorithm provides the first sub-linear space upper bound for obstru- ction-free leader election. A lower bound of $\Omega(log n)$ has been known since 1989 [29]. Our research is also motivated by the long-standing open problem whether there is an obstruction-free consensus algorithm which uses fewer than n registers.]]>

Little research explores the activity of sharing mobile num- bers on OSNs, in particular via public posts. In this work, we understand the characteristics and risks of mobile num- bers shared on OSNs either via profile or public posts and focus on Indian mobile numbers. We collected 76,347 unique mobile numbers posted by 85,905 users on Twitter and Face- book and analyzed 2,997 numbers, prefixed with +91. We observed that most users shared their own mobile numbers to spread urgent information and to market products, IT facilities and escort business. Users resorted to applications like Twitterfeed and TweetDeck to post and popularize mo- bile numbers on multiple OSNs. To assess risks associated with mobile numbers exposed on OSNs, we used mobile numbers to gain sensitive information (e.g. name, Voter ID) about their owners. We communicated the observed risks to the owners by calling them on their mobile num- ber. Few users were surprised to know the online presence of their number, while few users intentionally put it online for business purposes. With these observations, we highlight that there is a need to monitor leakage of mobile numbers via profile and public posts. To the best of our knowledge, this is the first exploratory study to critically investigate the exposure of mobile numbers on OSNs.

Guest: Prof Ponnurangam Kumaraguru

Host: Prof Zvi Lotker, Ben-Gurion University.

]]>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

]]>Guest: Chen Avin

Host: Shantanu Das

]]>We propose and demonstrate the feasibility of a probabilistic framework for mining user interests from their tweet times alone, by exploiting the known timing of external events associated with these interests. This approach allows for making inferences on the interests of a large number of users for which text-based mining may become cumbersome, and also sidesteps the difficult problem of semantic/contextual analysis required for such text-based inferences. The statistic that we propose for gauging the user’s interest level is the probability that he/she tweets more frequently at certain times when this topic is in the “public eye” than at other times. We report on promising experimental results using Twitter data on detecting whether or not a user is a fan of a given baseball team, leveraging the known timing of games played by the team. Since people often interact with others who share similar interests, we extend our probabilistic frame- work to use the interest level estimates for other users with whom a person interacts (by referring to them in his/her tweets). We demonstrate that it is possible to significantly improve the detection probability (for a given false alarm rate) by such information pooling on the social graph.

Guest: Dinesh Ramasamy (UCSB)

Host: Chen Avin

]]>Similarity estimation between nodes based on structural properties of graphs is a basic building block used in the analysis of massive networks for diverse purposes such as link prediction, product rec- ommendations, advertisement, collaborative filtering, and community discovery. While local similarity measures, based on proper- ties of immediate neighbors, are easy to compute, those relying on global properties have better recall. Unfortunately, this better qual- ity comes with a computational price tag. Aiming for both accuracy and scalability, we make several contributions. First, we define closeness similarity, a natural measure that compares two nodes based on the similarity of their relations to all other nodes. Second, we show how the all-distances sketch (ADS) node labels, which are efficient to compute, can support the estimation of closeness similarity and shortest-path (SP) distances in logarithmic query time. Third, we propose the randomized edge lengths (REL) technique and define the corresponding REL distance, which captures both path length and path multiplicity and therefore improves over the SP distance as a similarity measure. The REL distance can also be the basis of closeness similarity and can be estimated using SP computation or the ADS labels. We demonstrate the effectiveness of our measures and the accuracy of our estimates through experiments on social networks with up to tens of millions of nodes.

Guest: Daniel Delling (Microsoft Research)

Host: Chen Avin

]]>Graph matching is a generalization of the classic graph isomorphism problem. By using only their structures a graph-matching algorithm finds a map between the vertex sets of two similar graphs. This has applications in the de- anonymization of social and information networks and, more generally, in the merging of structural data from different domains.

One class of graph-matching algorithms starts with a known seed set of matched node pairs. Despite the success of these algorithms in practical applications, their performance has been observed to be very sensitive to the size of the seed set. The lack of a rigorous understanding of parameters and performance makes it difficult to design systems and predict their behavior.

In this paper, we propose and analyze a very simple per- colation -based graph matching algorithm that incrementally maps every pair of nodes (i,j) with at least r neighboring mapped pairs. The simplicity of this algorithm makes pos- sible a rigorous analysis that relies on recent advances in bootstrap percolation theory for the G(n, p) random graph. We prove conditions on the model parameters in which per- colation graph matching succeeds, and we establish a phase transition in the size of the seed set. We also confirm through experiments that the performance of percolation graph match- ing is surprisingly good, both for synthetic graphs and real social-network data.

Guest: Lyudmila Yartseva

Host: Chen Avin

]]>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

]]>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

]]>Guest: George Giakkoupis

Host: Stefan Schmid

]]>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

]]>Guest: Stacy Patterson

Host: Stefan Schmid

]]>We show that starting from any initial configuration, the fat robots eventually reach such a configuration and terminate yielding a solution to the gathering problem.

Guest: Chrysovalandis Agathangelou

Host: Shantanu Das

**Guest**: Rachid Guerraoui

**Host**: Yvonne-Anne Pignolet

Guest: Calvin Newport

Host: Yvonne-Anne Pignolet

Guest: Yuval Emek

Host: Yvonne-Anne Pignolet

Do unique node identifiers help in deciding whether a network G has a prescribed property P? We study this question in the context of distributed local decision, where the objective is to decide whether G \in P by having each node run a constant-time distributed decision algorithm. If G \in P, all the nodes should output yes; if G \notin P, at least one node should output no. A recent work (Fraigniaud et al., OPODIS 2012) studied the role of identifiers in local decision and gave several conditions under which identifiers are not needed. In this article, we answer their original question. More than that, we do so under all combinations of the following two critical variations on the underlying model of distributed computing: (B): the size of the identifiers is bounded by a function of the size of the input network; as opposed to (\neg B): the identifiers are unbounded. (C): the nodes run a computable algorithm; as opposed to (\neg C): the nodes can compute any, possibly uncomputable function. While it is easy to see that under (\neg B, \neg C) identifiers are not needed, we show that under all other combinations there are properties that can be decided locally if and only if identifiers are present. Our constructions use ideas from classical computability theory.

Guest: Mika Göös

Host: Stefan Schmid

1. A randomized distributed search algorithm that with high probability guarantees that searches from as many as n−o(n) nodes (n is the stable network size) succeed in O(logn)- rounds despite O(n/log^(1+δ) n) churn, for any small constant δ >= 0, per round. We assume that the churn is controlled by an oblivious adversary (that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm).

2. A storage and maintenance algorithm that guarantees, with high probability, data items can be efficiently stored (with only Θ(logn) copies of each data item) and maintained in a dynamic P2P network with churn rate up to O(n/log^(1+δ) n) per round. Our search algorithm together with our storage and maintenance algorithm guarantees that as many as n − o(n) nodes can efficiently store, maintain, and search even under O(n/log^(1+δ) n) churn per round. Our algorithms require only polylogarithmic in n bits to be processed and sent (per round) by each node. To the best of our knowledge, our algorithms are the ﬁrst-known, fully-distributed storage and search algorithms that provably work under highly dynamic settings (i.e., high churn rates per step). Furthermore, they are localized (i.e., do

not require any global topological knowledge) and scalable. A technical contribution of this paper, which may be of independent interest, is showing how random walks can be provably used to derive scalable distributed algorithms in dynamic networks with adversarial node churn.

Guests: Gopal Pandurangan and Peter Robinson

Host: Stefan Schmid

Guest: Florian Huc

Host: Stefan Schmid

expected O(log log u + c) steps, insertions and deletions in O(c log log u), and using O(m) space, where u is the size of the key space and c is the contention during the recent past.

The SkipTrie is a probabilistically-balanced version of a y-fast trie consisting of a very shallow skiplist from which randomly chosen elements are inserted into a hash-table based x-fast trie. By inserting keys into the x-fast-trie probabilistically, we eliminate the need for rebalancing, and can provide a lock-free linearizable implementation. To the best of our knowledge, our proof of the amortized expected performance of the SkipTrie is

the ﬁrst such proof for a tree-based data structure.

Guests: Rotem Oshman and Nir Shavit

Host: Stefan Schmid

Guests: Martina Eikel and Christian Scheideler

Host: Stefan Schmid

In distributed networks, it is often useful for the nodes to be aware of dense subgraphs, e.g., such a dense subgraph could reveal dense substructures in otherwise sparse graphs (e.g. the World Wide Web or social networks); these might reveal community clusters or dense regions for possibly maintaining good communication infrastructure. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs that the member nodes are aware of. The only knowledge that the nodes need is that of the

Guest: Amitabh Trehan

Host: Shantanu Das

Let be an n-vertex graph and a d-vertex graph, for some constant d. Is a subgraph of G? We consider this problem in a model where all n processes are connected to all other processes, and each message contains up to bits. A simple deterministic algorithm that requires communication rounds is presented. For the special case that is a triangle, we present a probabilistic algorithm that requires an expected rounds of communication, where t is the number of triangles in the graph, and with high probability. We also present deterministic algorithms specially suited for sparse graphs.

Guest: Christoph Lenzen

Host: Shantanu Das

A collection of n anonymous mobile robots is deployed on a unit-perimeter ring or a unit-length line segment. Every robot starts moving at constant speed, and bounces each time it meets any other robot or segment endpoint, changing its walk direction. We study the problem of

the presence and the initial positions of all other robots. The robots cannot communicate or perceive information about the environment in any way other than by bouncing. Each robot has a clock allowing it to observe the times of its bounces. The robots have no control on their walks, which are determined by their initial positions and the starting directions. Each robot executes the same position detection algorithm, which receives input data in real-time about the times of the bounces, and terminates when the robot is assured about the existence and the positions of all the robots.

Some initial configuration of robots are shown to be

Guest: Jurek Czyzowicz

Host: Shantanu Das

**Guest:** Sotiris Kentros

**Host**: Yvonne-Anne Pignolet

**Guest:** Merav Parter

**Host:** Yvonne-Anne Pignolet

]]>

Our result holds for so-called simple PO-checkable graph optimisation problems; this includes many classical packing and covering problems such as vertex covers, edge covers, matchings, independent sets, dominating sets, and edge dominating sets. We focus on the case of bounded-degree graphs and show that if a local algorithm finds a constant-factor approximation of a simple PO-checkable graph problem with the help of unique identifiers, then the same approximation ratio can be achieved on anonymous networks.

As a corollary of our result and by prior work, we derive a tight lower bound on the local approximability of the minimum edge dominating set problem.

Our main technical tool is an algebraic construction of homogeneously ordered graphs: We say that a graph is $(\alpha,r)$-homogeneous if its nodes are linearly ordered so that an $\alpha$ fraction of nodes have pairwise isomorphic radius-$r$ neighbourhoods. We show that there exists a finite $(\alpha,r)$-homogeneous $2k$-regular graph of girth at least $g$ for any $\alpha < 1$ and any $r$, $k$, and $g$.

Guest: Jukka Suomela

Host: Merav Parter

In the Byzantine agreement problem, a set of n processors, any f of whom may be arbitrarily faulty, must reach agreement on a value proposed by one of the correct processors. It is a celebrated result that unless n > 3 f , Byzantine agreement is impossible in a variety of computation and communication models. This is due to the fact that faulty processors can equivocate, that is, say different things to different processors. If this ability is mitigated, for example by assuming a global broadcast channel, then n > 2 f is sufficient. With very few exceptions, the literature on Byzantine agreement has been confined to the n > 2 f and n > 3 f paradigms.

We bridge the gap between these two paradigms by assuming partial broadcast channels among sets of three processors, observing that equivocation is fundamentally an act involving three parties: a faulty processor that lies (inconsistently) to two correct processors. We characterize the conditions under which Byzantine agreement is possible for all n = 2 f +h, h an integer in [1.. f ], by giving asymptotically tight bounds on the number of necessary and sufficient partial broadcast channels. We prove these bounds by

a reduction to a problem in extremal combinatorics, which itself is a natural generalization of a well-studied hypergraph coloring problem. Algorithmically, we show that deciding whether a given set of broadcast channels enables Byzantine agreement is co-NP complete. Although partial broadcast channels have been studied in prior work, the bounds obtained on the number of required channels were sub-optimal by up to a factor of . Moreover, this work has been confined to the synchronous model. In contrast, we apply our results to several distinct models and provide stronger motivation for using partial broadcast channels in practice, drawing from recent work in the systems community.

Guest: Siddhartha Sen

Host: Shantanu Das

This paper initiates the formal study of a fundamental problem: How to efficiently allocate a shared communication medium among a set of K co-existing networks in the presence of arbitrary external interference? While most literature on medium access focuses on how to share a medium among nodes, these approaches are often either not directly applicable to co-existing networks as they would violate the independence requirement, or they yield a low throughput if applied to multiple networks. We present the randomized medium access (MAC) protocol COMAC which guarantees that a given communication channel is shared fairly among competing and independent networks, and that the available bandwidth is used efficiently. These performance guarantees hold in the presence of arbitrary external interference or even under adversarial jamming. Concretely, we show that the co-existing networks can use a -fraction of the non-jammed time steps for successful message transmissions, where is the (arbitrarily distributed) fraction of time which is not jammed.

Guest: Andrea Richa

Host: Shantanu Das

We analyze two different scenarios. In the first case we assume that the attractiveness of the nodes follows a power law distribution with some exponent less than $3$, as observed in real world examples. Then, we show that even if each agent may spread the disease for $f(n)$ time steps, where $f(n) =\smallO(\log n)$ is a (slowly) growing function, at least a small (but still polynomial) number of agents remains uninfected and the epidemic is stopped after a logarithmic number of rounds. In the second scenario we assume that the power law exponent increases to some large constant, which can be seen as an implication of certain countermeasures against the spreading process.

Then, we show that if each agent is allowed to spread the disease for a constant number of time steps, the epidemic will only affect a polylogarithmic number of agents and the disease is stopped after $(\log \log n)^{\bigO(1)}$ steps. Our results explain possible courses of a disease, and point out why cost-efficient countermeasures may reduce the number of total infections from a high percentage of the population to a negligible fraction.

Guest: Robert Elsaesser

Host: Zvi Lotker

Guest: James Aspnes

Host: Zvi Lotker

We begin by establishing a lower bound of $\Omega\big( \frac{ \log^2{N} }{ (\freq -t)\log{\log{N}}} + \frac{ \freq t }{ \freq – t} \cdot \log{N}\big)$ rounds, through reduction to an existing result in this model. We then set out to prove this bound tight (within $\log\log{N}$ factors). For the case where $t=0$, we present a novel randomized algorithm, based on a strategy of recruiting {\em herald nodes}, that works in $O\big(\frac{\log^2{N}}{\freq}+\log N\big)$ time. For $1 \leq t \leq \freq/6$, we present a variant of our herald algorithm in which multiple real (potentially disrupted) frequencies are used to simulate each non-disrupted frequency from the $t=0$ case. This algorithm works in $O\big(\frac{\log^2{N}}{\freq} + t\log{N}\big)$ time. Finally, for $t > \freq/6$ we show how to improve the {\em trapdoor protocol} of~\cite{podc09}, used to solve a similar problem in a non-optimal manner, to solve leader election in optimal $O\big( \frac{\log{N} + \freq t}{\freq-t} \cdot \log{N} \big)$ time, for (only) these large values of $t$. We also observe that if $\freq=\omega(1)$ and $t \leq (1-\eps)\freq$ for a constant $\eps>0$, our protocols beat the classic $\Omega(\log^{2}{N})$ bound on wake-up in a single frequency radio network, underscoring the observation that more frequencies in a radio network allows for more algorithmic efficiency—even if devices can each only participate on a single frequency at a time, and a significant fraction of these frequencies are disrupted adversarially.

Guest: Sebastian Daum

Host: Yvonne-Anne Pignolet

This paper studies the reception zones of a wireless network in the SINR model with receivers that employ interference cancellation (IC). IC is a recently developed technique that allows a receiver to decode interfering signals, and cancel them from the received signal in order to decode its intended message.

We first derive the important topological properties of the reception zones and their relation to high-order Voronoi diagrams and other geometric objects. We then discuss the computational issues that arise when seeking an efficient description of the zones. Our main fundamental result states that although potentially there are exponentially many possible cancellation orderings, and as a result, reception zones, in fact there are much fewer nonempty such zones. We prove a linear bound (hence tight) on the number of zones and provide a polynomial time algorithm to describe the diagram. Moreover, we introduce a novel parameter, the

Guest: Merav Parter

Host: Shantanu Das

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

]]>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

]]>knapsack problem with uncertain item sizes and the deterministic orienteering problem of using a limited travel time to maximize gathered rewards located at nodes.

In this paper, we present a constant-factor ap-approximation algorithm for the best non-adaptive policy for the Stochastic Orienteering problem. We also show a small adaptivity gap, i.e., the existence of a non-adaptive policy whose reward is at least an fraction of the optimal expected reward, and hence we also get an approximation algorithm for the adaptive problem.

Finally we address the case when the node rewards are also random and could be correlated with the waiting time, and give a non-adaptive policy which is an -approximation to the best adaptive policy on n-node metrics with budget B.

Guest: Ravishankar Krishnaswamy

Host: Zvi Lotker

Our main result is a combinatorial, polynomial time algorithm for ADNB. It turns out that the reason for infeasibility of logarithmic RCPs is quite different from that for LPs and quadratic RCPs. We believe that our ideas for surmounting the new difficulties will be useful for dealing with other non-total RCPs as well. We give an application of our combinatorial algorithm for ADNB to an important “fair” throughput allocation problem on a wireless channel. Finally, we present a number of interesting questions that the new notion of RCP raises.

Guest: Vijay Vazirani

Host: Zvi Lotker

]]>We show that for any , a -approximation requires a communication complexity of .

We also consider the natural restrictingon of the problem in which and are only allowed to share vertices on one side of the bipartition, which is motivated by applications to one-pass streaming with vertex arrivals. We show that a 3/4-approximation can be achieved with a linear size message in this case, and this result is best possible in that super-linear space is needed to achieve any better approximation.

Finally, we build on our techniques for the restricted version above to design one-pass streaming algorithm for the case when vertices on one side are known in advance, and the vertices on the other side arrive in a streaming manner together with all their incident edges. This is precisely the setting of the celebrated (1-1/e)-competitive randomized algorithm of Karp-Vazirani-Vazirani (KVV) for the online bipartite matching problem. We present here the first deterministic one-pass streaming (1-1/e)-approximation algorithm using O(n) space for this setting.

Guest: Michael Kaparalov

Host: Yvonne-Anne Pignolet

Given an integer h, a graph with arbitrary positive edge capacities and k pairs of vertices , called terminals, an h-route cut is a set of edges such that after the removal of the edges in F no pair is connected by h edge-disjoint paths (i.e., the connectivity of every pair is at most in . The h-route cut is a natural generalization of the classical cut problem for multicommodity flows (take h = 1). The main result of this paper is an -approximation algorithm for the minimum h-route cut problem in the case that , called the single source case. As a corollary of it we obtain an approximate duality theorem for multiroute multicommodity flows and cuts with a single source. This partially answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems.

Guest: Christian Scheideler

Host: Shantanu Das

We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following:

- Given a desired space allocation S \in \[ n \log\log n, n^2 \], we show how to construct in time a data structure of size O(S) that answers distance queries in time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever .
- We provide a linear-space exact distance oracle for planar graphs with query time for any constant . This is the first such data structure with provable sublinear query time.
- For edge lengths , we provide an exact distance oracle of space such that for any pair of nodes at distance the query time is . Comparable query performance had been observed experimentally but could not be proven.

Our data structures are based on the following new tool: given a non-self-crossing cycle C with nodes, we can preprocess G in time to produce a data structure of size that can answer the following queries in time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA’05), which reports distances to the boundary of a face, rather than a cycle.

The best distance oracles for planar graphs until the current work are due to Cabello (SODA’06), Djidjev (WG’96), and Fakcharoenphol and Rao (FOCS’01). For and space , we essentially improve the query time from to .

Guest: Shay Mozes

Host: Shantanu Das

We analyze the popular push-pull protocol for spreading a rumor in networks. Initially, a single node knows of a rumor. In each succeeding round, every node chooses a random neighbor, and the two nodes share the rumor if one of them is already aware of it. We present the first theoretical analysis of this protocol on random graohs that have a power law degree distribution with an arbitrary exponent β ≥ 2.

Our main ﬁndings reveal a striking dichotomy in the performance of the protocol that depends on the exponent of the power law. More speciﬁcally, we show that if 2 < β < 3, then the rumor spreads to almost all nodes in Θ(log log n) rounds with high probability. On the other hand, if β > 3, then Ω(log n) rounds are necessary.

We also investigate the asynchronous version of the push-pull protocol, where the nodes do not operate in rounds, but exchange information according to a Poisson process with rate 1. Surprisingly, we are able to show that, if 2 < β < 3, the rumor spreads even in constant time, which is much smaller than the typical distance of two nodes. To the best of our knowledge, this is the ﬁrst result that establishes a gap between the synchronous and the asynchronous protocol.

Guest: Thomas Sauerwald

Host: Chen Avin

We study a natural information dissemination problem for multiple mobile agents in a bounded Euclidean space. Agents are placed uniformly at random in the d-dimensional space {-n, …, n}^d at time zero, and one of the agents holds a piece of information to be disseminated. All the agents then perform independent random walks over the space, and the information is transmitted from one agent to another if the two agents are sufficiently close. We wish to bound the total time before all agents receive the information (with high probability). Our work extends Pettarin et al’s work [10], which solved the problem for d = 2. We present tight bounds up to polylogarithmic factors for the case d = 3. (While our results extend to higher dimensions, for space and readability considerations we provide only the case d = 3 here.) Our results show the behavior when d >= 3 is qualitatively different from the case d = 2. In particular, as the ratio between the volume of the space and the number of agents varies, we show an interesting phase transition for three dimensions that does not occur in one or two dimensions.

Guest: Henry Lam

Host: Chen Avin

We study the problem of computing the diameter of a network in a distributed way. The model of distributed computation we consider is: in each synchronous round, each node can transmit a different (but) short message to each of its neighbors. We provide an lower bound for the number of communication rounds needed, where n denotes the number of nodes in the network. This lower bound is valid even if the diameter of the network is a small constant. We also show that a -approximation of the diameter requires rounds. Furthermore we use our new technique to prove an lower bound on approximating the girth of a graph by a factor

.

Guest: Stephan Holzer

Host: Chen Avin

We study the relation between the rate at which rumors spread throughout a graph and the vertex expansion of the graph. We consider the standard rumor spreading protocol where every node chooses a random neighbor in each round and the two nodes exchange the rumors they know. For any n-node graph with vertex expansion , we show that this protocol spreads a rumor from a single node to all other nodes in rounds with high probability. Further, we construct graphs for which rounds are needed. Our results complement a long series of works that relate rumor spreading to edge-based notions of expansion, resolving one of the most natural questions on the connection between rumor spreading and expansion.

Guest: George Giakkoupis

Host: Chen Avin

Motivated by the need for robust and fast distributed computation in highly dynamic Peer-to-Peer (P2P) networks, we study algorithms for the fundamental distributed agreement problem. P2P networks are highly dynamic networks that experience heavy node {\em churn} (i.e., nodes join and leave the network continuously over time). Our main contributions are randomized distributed algorithms that guarantee {\em stable almost-everywhere agreement} with high probability even under high adversarial churn in polylogarithmic number of rounds. In particular, we present the following results:

1. An -round (n is the stable network size) randomized algorithm that achieves almost-everywhere agreement with high probability under up to {\em linear} churn {\em per round} (i.e., , for some small constant ), assuming that the churn is controlled by an oblivious adversary (has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm).

2. An -round randomized algorithm that achieves almost-everywhere agreement with high probability under up to churn per round (for some small ), where m is the size of the input value domain, that works even under an adaptive adversary (that also knows the past random choices made by the algorithm).

Our algorithms are the first-known, fully-distributed, agreement algorithms that work under highly dynamic settings (i.e., high churn rates per step). Furthermore, they are localized (i.e., do not require any global topological knowledge), simple, and easy to implement. These algorithms can serve as building blocks for implementing other non-trivial distributed computing tasks in dynamic P2P networks.

Guests: Gopal Pandurangan with John Augustine and Peter Robinson

Host: Chen Avin

For even dimensions $d\ge{}2$, the maximum values are attained if $P_1$ and $P_2$ are cyclic $d$-polytopes with disjoint vertex sets. For odd dimensions $d\ge{}3$, the maximum values are attained if $P_1$ and $P_2$ are $\lfloor\frac{d}{2}\rfloor$-

Guest: Menelaos I. Karavelas

Host: Zvi Lotker

]]>

Guest: Claire Mathieu

Host: Zvi Lotker

Guest: Kirk Pruhs

Host: Zvi Lotker

]]>Host: Zvi Lotker

In this paper, we prove the Boyd-Carr conjecture. In the case that a fractional 2-matching has no cut edge, we can further prove that an optimal 2-matching is at most 10/9 times the cost of the fractional 2-matching.

Guest: Anke Van Zuylen

Host: Zvi Lotker

]]>Host: Zvi Lotker

A new weak shared coin protocol yields a randomized wait-free shared-memory consensus protocol that uses an optimal expected total work with single-writer registers despite asynchrony and process crashes. Previously, no protocol was known that achieved this bound without using multi-writer registers.

Guest: James Aspnes

Host: Yvonne-Anne Pignolet

We consider the problem of locating a black hole in synchronous anonymous networks using finite-state agents. A black hole is a harmful node in the network that destroys any agent visiting that node without leaving any trace. The objective is to locate the black hole without destroying too many agents. This is difficult to achieve when the agents are initially scattered in the network and are unaware of the location of each other. Previous studies for black hole search used more powerful models where the agents had non-constant memory, were labelled with distinct identifiers and could either write messages on the nodes of the network or mark the edges of the network. In contrast, we solve the problem using a small team of finite-state agents each carrying a constant number of identical tokens that could be placed on the nodes of the network. Thus, all resources used in our algorithms are independent of the network size. We restrict our attention to oriented torus networks and first show that no team of finite-state agents can solve the problem in such networks, when the tokens are not movable. In case the agents are equipped with movable tokens, we determine lower bounds on thenumber of agents and tokens required for solving the problem in torus networks of arbitrary size. Further, we present a deterministic solution to the black hole search problem for oriented torus networks, using the minimum number of agents and tokens, thus providing matching upper bounds for the problem.

Guest: Jeremie Chalopin

Host: Zvi Lotker

Traceroute measurements are one of our main instruments to shed light onto the structure and properties of today’s complex networks such as the Internet. This paper studies the feasibility and infeasibility of inferring the network topology given traceroute data from a worst-case perspective, i.e., without any probabilistic assumptions on, e.g., the nodes’ degree distribution. We attend to a scenario where some of the routers are anonymous, and propose two fundamental axioms that model two basic assumptions on the traceroute data: (1) each trace corresponds to a real path in the network, and (2) the routing paths are at most a factor 1/alpha off the shortest paths, for some parameter alpha in (0,1]. In contrast to existing literature that focuses on the cardinality of the set of (often only minimal) inferrable topologies, we argue that a large number of possible topologies alone is often unproblematic, as long as the networks have a similar structure. We hence seek to characterize the set of topologies inferred with our axioms. We introduce the notion of star graphs whose colorings capture the differences among inferred topologies; it also allows us to construct inferred topologies explicitly. We find that in general, inferrable topologies can differ significantly in many important aspects, such as the nodes’ distances or the number of triangles. These negative results are complemented by a discussion of a scenario where the trace set is best possible, i.e., “complete”. It turns out that while some properties such as the node degrees are still hard to measure, a complete trace set can help to determine global properties such as the connectivity.

Guest: Stefan Schmid

Host: Zvi Lotker

In an asymmetric rendezvous system, such as an unfair synchronous queue and an elimination array, threads of two types, consumers and producers, show up and are matched, each with a unique thread of the other type. Here we present a new highly scalable, high throughput asymmetric rendezvous system that outperforms prior synchronous queue and elimination array implementations under both symmetric and asymmetric workloads (more operations of one type than the other). It is a fast matching machine. Consequently, we also present a highly scalable and competitive stack implementation

Guest: Yehuda Afek

Host: Zvi Lotker

Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and (∆ + 1)-coloring algorithms by Barenboim and Elkin [6], by Kuhn [22], and by Panconesi and Srinivasan [33], as well as the O(∆^2)-coloring algorithm by Linial [27]. Unfortunately, most known local algorithms (including, in particular, the aforementioned algorithms) are non-uniform, that is, they assume that all nodes know good estimations of one or more global parameters of the network, e.g., the maximum degree ∆ or the number of nodes n. This paper provides a rather general method for transforming a non-uniform local algorithm into a uniform one. Furthermore, the resulting algorithm enjoys the same asymptotic running time as the original non-uniform algorithm. Our method applies to a wide family of both deterministic and randomized algorithms. Speciﬁcally, it applies to almost all of the state of the art non-uniform algorithms regarding MIS and Maximal Matching, as well as to many results concerning the coloring problem. (In particular, it applies to all aforementioned algorithms.) To obtain our transformations we introduce a new distributed tool called pruning algorithms, which we believe may be of independent interest.

Guest: Amos Korman

Host: Zvi Lotker

We consider the model of fully connected networks, where

in each round each node can send an O(log n)-bit message

to each other node (this is the congest model with diame-

ter 1). It is known that in this model, min-weight spanning

trees can be found in O(log log n) rounds. In this paper we

show that distributed sorting, where each node has at most

n items, can be done in time O(log log n) as well. It is also

shown that selection can be done in O(1) time. (Using a con-

current result by Lenzen and Wattenhofer, the complexity of

sorting is further reduced to constant.) Our algorithms are

randomized, and the stated complexity bounds hold with

high probability.

Guest: Boaz Patt-Shamir

Host: Chen Avin

We study problems of data aggregation, such as approximate counting and computing the minimum input value, in synchronous directed networks with bounded message bandwidth B = Ω(log n). In undirected networks of diameter D, many such problems can easily be solved in O(D) rounds, using O(log n)-size messages. We show that for directed networks this is not the case: when the bandwidth B is small, several classical data aggregation problems have a time complexity that depends polynomially on the size of the network, even when the diameter of the network is constant.

Guest: Rotem Oshman

Host: Chen Avin

In this paper, we propose a new distributed construction of constant-degree expanders motivated by their application in P2P overlay networks and in particular in the design of robust tree overlays. Our key result can be stated as follows. Consider a complete binary tree T and construct a random pairing Π between leaf nodes and internal nodes. We prove that the graph GΠ obtained from T by contracting all pairs (leaf-internal nodes) achieves a constant node expansion with high probability. In the context of P2P overlays our result can be interpreted as follows: if each physical node participating to the tree overlay manages a random pair that couples one virtual internal node and one virtual leaf node then the physical-node layer exhibits a constant expansion with high probability. We encompass the diﬃculty of obtaining the random tree virtualization by proposing a local, self-organizing and churn resilient uniformly-random pairing algorithm with O(log2 n) running time. Our algorithm has the merit to not modify the original tree overlay (we just control the mapping between physical nodes and virtual nodes). Therefore, our scheme is general and can be easilly extended to a large class of overlays.

Guest: Taisuke Izumi

Host: Chen Avin

We study the edge-coloring problem in the message-passing model of distributed computing. This is one of the most fundamental problems in this area. Currently, the best-known deterministic algorithms for (2∆− 1)-edge-coloring requires O(∆) + log∗ n time [23], where ∆ is the maximum degree of the input graph. Also, recent results of [5] for vertex-coloring imply that one can get an O(∆)-edge-coloring in O(∆^ϵ ·log n) time, and an O(∆^{1+ϵ})-edge-coloring in O(log ∆ log n) time, for an arbitrarily small constant ϵ > 0. In this paper we devise a signiﬁcantly faster deterministic edge-coloring algorithm. Speciﬁcally, our algorithm computes an O(∆)-edge-coloring in O(∆^ϵ ) + log∗ n time, and an O(∆^{1+ϵ} )-edge-coloring in O(log ∆) + log∗ n time. This result improves the state-of-the-art running time for deterministic edge-coloring with this number of colors in almost the entire range of maximum degree ∆. Moreover, it improves it exponentially in a wide range of ∆, speciﬁcally, for 2^Ω(log* n) ≤ ∆ ≤ polylog(n). In addition, for small values of ∆ (up to log^{1−δ} n, for some ﬁxed δ > 0) our deterministic algorithm outperforms all the existing randomized algorithms for this problem.

Guest: Leonid Barenboim

Host: Chen Avin

We study several variants of coordinated consensus in dynamic networks. We assume a synchronous model, where the communication graph for each round is chosen by a worst-case adversary. The network topology is always connected, but can change completely from one round to the next. The model captures mobile and wireless networks, where communication can be unpredictable. In this setting we study the fundamental problems of eventual, simultaneous, and ∆-coordinated consensus, as well as their relationship to other distributed problems, such as determining the size of the network. We show that in the absence of a good initial upper bound on the size of the network, eventual consensus is as hard as computing deterministic functions of the input, e.g., the minimum or maximum of inputs to the nodes. We also give an algorithm for computing such functions that is optimal in every execution.

Guest: Rotem Oshman

Host: Chen Avin

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.

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.

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

]]>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.

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

**Abstract:**

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

]]>

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.

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

]]>Guest: Maurice Herlihy

Host: Zvi Lotker and Yvonne-Anne Pignolet

Guest: Antonio Fernandez Anta

Host: Yvonne-Anne Pignolet

Guest: Chryssis Georgiou

Host: Yvonne-Anne Pignolet

Guest: Srikanta Tirthapura

Host: Yvonne-Anne Pignolet

However, in the protocols with honest majority, parties must generate and hold local secret values which are assumed to be perfectly hidden from malicious parties: an assumption which is crucial to proving the resulting common coin is unbiased. This assumption unfortunately does not seem to hold in practice, as attackers can launch side-channel attacks on the local state of honest parties and leak information on their secrets.

In this work, we present an O(1)-round protocol for collectively generating an unbiased common coin, in the presence of leakage on the local state of the honest parties. We tolerate t ≤ ( 1/3 − ϵ)n computationally-unbounded Byzantine faults and in addition a Ω(1)-fraction leakage on each (honest) party’s secret state. Our results hold in the memory leakage model (of Akavia, Goldwasser, Vaikuntanathan ’08) adapted to the distributed setting.

Additional contributions of our work are the tools we introduce to achieve the collective coin toss: a procedure for disjoint committee election, and leakage-resilient verifiable secret sharing.

Guest: Elette Boyle

Host: Yvonne-Anne Pignolet

Guest: Thomas Moscibroda

Host: Yvonne-Anne Pignolet

Guest: Calvin Newport

Host: Yvonne-Anne Pignolet

monotone-consistent counter with logarithmic step complexity (at the cost of adding a max register) or a linearizable fetch-and-increment register (at the cost of increasing the step complexity by a logarithmic factor).

Guest: Dan Alistarh

Host: Yvonne-Anne Pignolet

Host: Yvonne-Anne Pignolet ]]>

Guest: Valerie King

Host: Yvonne-Anne Pignolet

We consider the problem of computing a maximal independent set (MIS, a maximal set of nodes in a network such that no two of them are neighbors) in an extremely harsh broadcast model that relies only on carrier sensing. The model consists of an anonymous broadcast network in which nodes have no knowledge about the topology of the network or even an upper bound on its size. Furthermore, it is assumed that nodes wake up asynchronously. At each time slot a node can either beep (i.e., emit a signal) or be silent. At a particular time slot, beeping nodes receive no feedback, while silent nodes can only differentiate between none of its neighbors beeping, or at least one neighbor beeping.

We start by proving a lower bound that shows that in this model, it is not possible to locally converge to an MIS in sub-polynomial time. We then study four different relaxations of the model which allow us to circumvent the lower bound and compute an MIS in polylogarithmic time.

Guest: Ziv Bar-Joseph

Host: Chen Avin

So far, the distributed computing community has either assumed that the processes of a distributed system all have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. In a sense, these are two extremes of the same general model: namely, n processes can use l authenticated identifiers, where 1 ≤ l ≤ n. This paper studies Byzantine agreement in this general model assuming several processes can share the same identifier.

We study Byzantine agreement in a message-passing system with homonyms. We assume up to t < n of the processes can be Byzantine. We prove the following results: (i) synchronous agreement is possible if and only if l > 3t; (ii) partially synchronous agreement is possible if and only if 3t < l ≤ n < 2l−3t; (iii) asynchronous eventual agreement is possible if and only if l > 3t.

Guset: Rachid Guerraoui

Host: Zvi Lotker