Toward more Localized Local Algorithms: Removing Assumptions concerning Global Knowledge

Amos Korman, Jean-Sébastien Sereni and Laurent Viennot

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. Specifically, 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

The Round Complexity of Distributed Sorting

Boaz Patt-Shamir and Marat Teplitsky

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

Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence

Leonid Barenboim and Michael Elkin

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 significantly faster deterministic edge-coloring algorithm. Specifically, 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 ∆, specifically, for 2^Ω(log* n) ≤ ∆ ≤ polylog(n). In addition, for small values of ∆ (up to log^{1−δ} n, for some fixed δ > 0) our deterministic algorithm outperforms all the existing randomized algorithms for this problem.

Guest: Leonid Barenboim
Host: Chen Avin

Coordinated Consensus in Dynamic Networks

Fabian Kuhn, Yoram Moses and Rotem Oshman

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

The Impact of Memory Models on Software Reliability in Multiprocessors

Alexander Jaffe, Thomas Moscibroda, Laura Effinger-Dean, Luis Ceze, and Karin Strauss

Abstract: The memory consistency model is a fundamental system property characterizing a multiprocessor. The relative merits of strict versus relaxed memory models have been widely debated in terms of their impact on performance, hardware complexity and programmability. This paper adds a new dimension to this discussion: the impact of memory models on software reliability. By allowing some instructions to reorder, weak memory models may expand the window between critical memory operations. This can increase the chance of an undesirable thread-interleaving, thus allowing an otherwise-unlikely concurrency bug to manifest. To explore this phenomenon, we define and study a probabilistic model of shared-memory parallel programs that takes into account such reordering. We use this model to formally derive bounds on the vulnerability to concurrency bugs of different memory models. Our results show that for 2 concurrent threads, weaker memory models do indeed have a higher likelihood of allowing bugs. On the other hand, we show that as the number of parallel, buggy threads increases, the gap between the different memory models becomes proportionally insignificant, and thus the importance of using a strict memory model diminishes.

Guest: Thomas Moscibroda
Host: Yvonne-Anne Pignolet

Structuring Unreliable Radio Networks

Keren Censor-Hillel, Seth Gilbert, Fabian Kuhn, Nancy Lynch and Calvin Newport

Abstract: In this paper we study the problem of building a connected dominating set with constant degree (CCDS) in the dual graph radio network model [5, 10, 11]. This model includes two types of links: reliable, which always deliver messages, and unreliable, which sometimes fail to deliver messages. Real networks compensate for this differing quality by deploying low-layer detection protocols to filter unreliable from reliable links. With this in mind, we begin by presenting an algorithm that solves the CCDS problem in the dual graph model under the assumption that every process u is provided a local link detector set consisting of every neighbor connected to u by a reliable link. A natural follow up question is whether the link detector must be perfectly reliable to solve the CCDS problem. With this in mind, we first describe an algorithm that builds a CCDS in O(∆polylog(n)) time under the assumption of O(1) unreliable links included in each link detector set. We then prove this algorithm to be (almost) tight by showing that the possible inclusion of only a single unreliable link in each process’s local link detector set is sufficient to require Ω(∆) rounds to solve the CCDS problem, regardless of message size. We conclude by discussing how to apply our algorithm in the setting where the topology of reliable and unreliable links can change over time.

Guest: Calvin Newport
Host: Yvonne-Anne Pignolet

Optimal-Time Adaptive Strong Renaming with Applications to Counting

Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert and Morteza Zadimoghaddam

Abstract: We give two new randomized algorithms for strong renaming, both of which work against an adaptive adversary in asynchronous shared memory. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of n processes with step complexity O(log^3 n). The second transforms any sorting network into a strong adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a strong adaptive renaming algorithm with step complexity O(log k), where k is the contention in the current execution. We show this to be optimal based on a classic lower bound of Jayanti. We also show that any such strong renaming protocol can be used to build a
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

Distributed Coloring in Few Rounds

Kishore Kothapalli and Sriram Pemmaraju

Guests: Kishore Kothapalli and Sriram Pemmaraju
Host: Yvonne-Anne Pignolet

Conflict on a Communication Channel

Valerie King, Jared Saia, Maxwell Young

Abstract: Imagine that Alice wants to send a message to Bob, and that Carol wants to prevent this. Assume there is a communication channel between Alice and Bob, but that Carol is capable of blocking this channel. Furthermore, there is a cost of S dollars to send on the channel, L dollars to listen on the channel and B to block the channel. How much will Alice and Bob need to spend in order to guarantee transmission of the message? This problem abstracts many types of conflict in information networks including: jamming attacks in wireless networks and distributed denial-of-service (DDoS) attacks on the Internet, where the costs to Alice, Bob and Carol represent an expenditure of energy and network resources. The problem allows us to quantitatively analyze the economics of information exchange in an adversarial setting and ask: Is communication cheaper than censorship? We answer this question in the affirmative by showing that it is significantly more costly for Carol to block communication of the message than for Alice to communicate it to Bob.

Guest: Valerie King
Host: Yvonne-Anne Pignolet

Byzantine Agreement with Homonyms

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert and Hung Tran-The

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