Category Archives: Conferences Spoilers

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

Mohsen Gaffari, Nancy Lynch, Calvin Newport

Posted on by
Reply

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

Podcast: Play in new window | Download

Stone Age Distributed Computing

Yuval Emek and Roger Wattenhofer

Posted on by
Reply

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

Podcast: Play in new window | Download

What can be decided locally without identifiers?

Pierre Fraigniaud, Mika Göös, Amos Korman, and Jukka Suomela

Posted on by
Reply

Abstract

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

Podcast: Play in new window | Download

Storage and Search in Dynamic Peer-to-Peer Networks

John Augustine, Anisur Rahaman Molla, Ehab Morsy, Gopal Pandurangan, Peter Robinson, and Eli Upfal

Posted on by
Reply

Abstract: We study robust and efficient distributed algorithms for searching, storing, and maintaining data in dynamic Peer-to-Peer (P2P) networks. P2P networks are highly  dynamic networks that experience heavy node churn (i.e., nodes join and leave the network continuously over time). Our goal is to guarantee, despite high node churn rate, that a large number of nodes in the network can store, retrieve, and maintain a large number of data items. Our main contributions are fast randomized distributed algorithms that guarantee the above with high probability even under high adversarial churn. In particular, we present the following main results:
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 first-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

Podcast: Play in new window | Download

Fast Byzantine Agreement

Nicolas Braud-Santoni, Rachid Guerraoui, Florian Huc

Posted on by
Reply

Abstract: This paper presents the first probabilistic Byzantine Agreement algorithm whose communication and time complexities are poly-logarithmic. So far, the most effective probabilistic Byzantine Agreement algorithm had communication complexity O*(sqrt n), and time complexity O*(1). Our algorithm is based on a novel, unbalanced, almost everywhere to everywhere Agreement protocol which is interesting in its own right.

Guest: Florian Huc
Host: Stefan Schmid

Podcast: Play in new window | Download

The SkipTrie: Low-Depth Concurrent Search without Rebalancing

Rotem Oshman and Nir Shavit

Posted on by
Reply

Abstract: To date, all concurrent search structures that can support predecessor queries have had depth logarithmic in m, the number of elements. This paper introduces the SkipTrie, a new concurrent search structure supporting predecessor queries in amortized
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 first such proof for a tree-based data structure.

Guests: Rotem Oshman and Nir Shavit
Host: Stefan Schmid

Podcast: Play in new window | Download

IRIS: A Robust Information System Against Insider DoS-Attacks

Martina Eikel and Christian Scheideler

Posted on by
Reply

Abstract: In this work we present the first scalable distributed information system, i.e., a system with low storage overhead, that is provably robust against Denial-of-Service (DoS) attacks by a current insider. We allow a current insider to have complete knowledge about the information system and to have the power to block any eps-fraction of its servers by a DoS-attack, where eps can be chosen up to a constant. The task of the system is to serve any collection of lookup requests with at most one per non-blocked server in an efficient way despite this attack. Previously, scalable solutions were only known for DoS-attacks of past insiders, where a past insider only has complete knowledge about some past time point t0 of the information system. Scheideler et al. [2,3] showed that in this case it is possible to design an information system so that any information that was inserted or last updated after t0 is safe against a DoS-attack. But their constructions would not work at all for a current insider. The key idea behind our IRIS system is to make extensive use of coding. More precisely, we present two alternative distributed coding strategies with an at most logarithmic storage overhead that can handle up to a constant fraction of blocked servers.

Guests: Martina Eikel and Christian Scheideler
Host: Stefan Schmid

Podcast: Play in new window | Download

Dense Subgraphs on Dynamic Networks

Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan

Posted on by
Reply

Abstract
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 dynamic diameter , i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that -approximate the densest subgraph and -approximate the at-least-k-densest subgraph (for a given parameter k). Our algorithms work for a wide range of parameter values and run in time. Further, a special case of our results also gives the first fully decentralized approximation algorithms for densest and at-least-k-densest subgraph problems for static distributed graphs.

 

Guest: Amitabh Trehan
Host: Shantanu Das

Podcast: Play in new window | Download

“Tri, Tri again”: Finding Triangles and Small Subgraphs in a Distributed Setting

Danny Dolev, Christoph Lenzen, and Shir Peled

Posted on by
Reply

Abstract:
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

Podcast: Play in new window | Download

Position Discovery for a System of Bouncing Robots

Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Oscar Morales Ponce, and Eduardo Pacheco

Posted on by
Reply

Abstract:
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 position discovery, in which the task of each robot is to detect
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 infeasible — no position detection algorithm exists for them. We give complete characterizations of all infeasible initial configurations for both the ring and the segment, and we design optimal position detection algorithms for all feasible configurations. For the case of the ring, we show that all robot configurations in which not all the robots have the same initial direction are feasible. We give a position detection algorithm working for all feasible configurations. The cost of our algorithm depends on the number of robots starting their movement in each direction.

Guest: Jurek Czyzowicz
Host: Shantanu Das

Podcast: Play in new window | Download