Introducing Speculation in Self-Stabilization – An Application to Mutual Exclusion

Swan Dubois and Rachid Guerraoui

Abstract: Self-stabilization ensures that, after any transient fault, the system recovers in a finite time and eventually exhibits. Speculation consists in guaranteeing that the system satisfies its requirements for any execution but exhibits significantly better performances for a subset of executions that are more probable. A speculative protocol is in this sense supposed to be both robust and efficient in practice. We introduce the notion of speculative stabilization which we illustrate through the mutual exclusion problem. We then present a novel speculatively stabilizing mutual exclusion protocol. Our protocol is self-stabilizing for any asynchronous execution. We prove that its stabilization time for synchronous executions is diam(g)/2 steps (where diam(g) denotes the diameter of the system). This complexity result is of independent interest. The celebrated mutual exclusion protocol of Dijkstra stabilizes in n steps (where n is the number of processes) in synchronous executions and the question whether the stabilization time could be strictly smaller than the diameter has been open since then (almost 40 years). We show that this is indeed possible for any underlying topology. We also provide a lower bound proof that shows that our new stabilization time of diam(g)/2 steps is optimal for synchronous executions, even if asynchronous stabilization is not required.

Guest: Rachid Guerraoui
Host: Yvonne-Anne Pignolet

The Cost of Radio Network Broadcast for Different Models of Unreliable Links

Mohsen Gaffari, Nancy Lynch, Calvin Newport

Abstract: We study upper and lower bounds for the global and local broadcast problems in the dual graph model combined with different strength adversaries. The dual graph model is a generalization of the standard graph-based radio network model that includes unreliable links controlled by an adversary. It is motivated by the ubiquity of unreliable links in real wireless networks. Existing results in this model assume an offline adaptive adversary – the strongest type of adversary considered in standard randomized analysis. In this paper, we study the two other standard types of adversaries: online adaptive and oblivious. Our goal is to find a model that captures the unpredictable behavior of real networks while still allowing for efficient broadcast solutions.

Guest: Calvin Newport
Host: Yvonne-Anne Pignolet

Stone Age Distributed Computing

Yuval Emek and Roger Wattenhofer

Abstract: A new model that depicts a network of randomized finite state machines operating in an asynchronous environment is introduced. This model, that can be viewed as a hybrid of the message passing model and cellular automata is suitable for applying the distributed computing lens to the study of networks of sub-microprocessor devices, e.g., biological cellular networks and man-made nano-networks. Although the computation and communication capabilities of each individual device in the new model are, by design, much weaker than those of an abstract computer, we show that some of the most important and extensively studied distributed computing problems can still be solved efficiently.

Guest: Yuval Emek
Host: Yvonne-Anne Pignolet

Lower Bounds for Local Approximation

Mika Göös, Juho Hirvonen, Jukka Suomela

Abstract: In the study of deterministic distributed algorithms it is commonly assumed that each node has a unique $O(\log n)$-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributed algorithms) do not need such identifiers: a port numbering and orientation is sufficient.
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

Ultra-Fast Rumor Spreading in Social Networks

Nikolaos Fountoulakis, Konstantinos Panagiotou and Thomas Sauerwald

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 findings reveal a striking dichotomy in the performance of the protocol that depends on the exponent of the power law. More specifically, 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 first result that establishes a gap between the synchronous and the asynchronous protocol.

Guest: Thomas Sauerwald
Host: Chen Avin

Information Dissemination via Random Walks in d-Dimensional Space

Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun and Yajun Wan

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

Networks Cannot Compute Their Diameter in Sublinear Time

Silvio Frischknecht, Stephan Holzer and Roger Wattenhofer

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

Rumor Spreading and Vertex Expansion

George Giakkoupis and Thomas Sauerwald

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

Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks

John Augustine, Gopal Pandurangan, Peter Robinson and Eli Upfal

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

Randomized Consensus in Expected O(n^2) Total Work using Single-Writer Registers

James Aspnes

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