# Convergence in (Social) Influence Networks

## Silvio Frischknecht, Barbara Keller, and Roger Wattenhofer

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

# Faster Rumor Spreading: Breaking the log n Barrier

## Chen Avin and Robert Elsässer

Abstract. $O(\log{n})$ rounds has been a well known upper bound for rumor spreading using push&pull in the random phone call model (i.e., uniform gossip in the complete graph). A matching lower bound of $\Omega(\log{n})$ is also known for this special case. Under the assumptions of this model and with a natural addition that nodes can call a partner once they learn its address (e.g., its IP address) we present a new distributed, address-oblivious and robust algorithm that uses push&pull with pointer jumping to spread a rumor to all nodes in only $O(\sqrt{\log{n}})$ rounds, w.h.p. This algorithm can also cope with $F = o( n/2^{\sqrt{\log{n}}} )$ node failures, in which case all but $O(F)$ nodes become informed within $O(\sqrt{\log{n}})$ rounds, w.h.p.

Guest: Chen Avin

Host: Shantanu Das

# A Distributed Algorithm for Gathering Many Fat Mobile Robots in the Plane

## Chrysovalandis Agathangelou, Chryssis Georgiou, and Marios Mavronicolas

Abstract: We revisit the problem of gathering autonomous robots in the plane. In particular, we consider non-transparent unit-disc robots (i.e., fat) in an asynchronous setting with vision as the only means of coordination and robots only make local decisions. We use a state-machine representation to formulate the gathering problem and develop a distributed algorithm that solves the problem for any number of fat robots. The main idea behind the algorithm is to enforce the robots to reach a configuration in which all the following hold: (a) The robots’ centers form a convex hull in which all robots are on the convex, (b) Each robot can see all other robots, and (c) The configuration is connected: every robot touches another robot and all robots form together a connected formation.
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

# Dense Subgraphs on Dynamic Networks

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

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 $D$, 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 $(2+\epsilon)$-approximate the densest subgraph and $(3 + \epsilon)$-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 $O(D \log_{1+\epsilon} n)$ 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

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

## Danny Dolev, Christoph Lenzen, and Shir Peled

Abstract:
Let $G = (V,E)$ be an n-vertex graph and $M_d$ a d-vertex graph, for some constant d. Is $M_d$ 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 $O(log n)$ bits. A simple deterministic algorithm that requires $O(n^{(d-2)/d}/ \log n)$ communication rounds is presented. For the special case that $M_d$ is a triangle, we present a probabilistic algorithm that requires an expected $O(n^{1/3}/(t^{2/3} + 1))$ rounds of communication, where t is the number of triangles in the graph, and $O(\min\{n^{1/3} \log^{2/3}n/(t^{2/3} + 1), n^{1/3}\})$ with high probability. We also present deterministic algorithms specially suited for sparse graphs.

Guest: Christoph Lenzen
Host: Shantanu Das

# Position Discovery for a System of Bouncing Robots

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

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

# On the Price of Equivocation in Byzantine Agreement

## Alexander Jaffe, Thomas Moscibroda, and Siddhartha Sen

Abstract:

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 $\Theta(n^2)$. 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

# Competitive and Fair Throughput for Co-Existing Networks Under Adversarial Interference

## Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang

Abstract:
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 $\Omega(\epsilon^2 \min\{\epsilon,1/poly(K)\}$-fraction of the non-jammed time steps for successful message transmissions, where $\epsilon$ is the (arbitrarily distributed) fraction of time which is not jammed.

Guest: Andrea Richa
Host: Shantanu Das

# SINR Diagram with Interference Cancellation

## Chen Avin, Asaf Cohen, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter and David Peleg

Abstract:
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
Compactness Parameter, which influences the tightness of our bounds. We then utilize these properties to devise a logarithmic time algorithm to answer point-location queries for networks with IC.

Guest: Merav Parter
Host: Shantanu Das

# Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case

## Petr Kolman and Christian Scheideler

Abstract:

Given an integer h, a graph $G = (V, E)$ with arbitrary positive edge capacities and k pairs of vertices $(s_1,t_1),(s_2, t_2),\dots,(s_k,t_k)$, called terminals, an h-route cut is a set $F \subset E$ of edges such that after the removal of the edges in F no pair $s_i-t_i$ is connected by h edge-disjoint paths (i.e., the connectivity of every $s_i-t_i$ pair is at most $h-1$ in $(V, E \setminus F))$. 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 $O(h^{5}2^{2h}(h+log k)^2)$-approximation algorithm for the minimum h-route cut problem in the case that $s_1 = s_2 =\dots= s_k$, 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