SIROCCO 2017

Full program in PDF

Keynote lectures

Faith Ellen • University of Toronto, Canada
Ignorance is Bliss (for Proving Impossibility)

Abstract: This talk will present a survey of techniques for proving lower bounds and uncomputability in message passing and radio network models. All of them hinge on the processes' continued ignorance of one another's states or input values.

Christian Scheideler • University of Paderborn, Germany
Amoebots and beyond: Models and Approaches for Programmable Matter

Abstract: "Programmable matter" is a term originally coined by Toffoli and Margolus in 1991 to refer to an ensemble of fine-grained computing elements arranged in space. Since then, there has been a significant amount of work on programmable matter across multiple disciplines, including physics (e.g., crystals and complex fluids), chemistry (e.g., metamaterials and shape-changing molecules), bioengineering (DNA self-assembly and cell engineering), and robotics (modular robotics and nano robotics). So one can imagine that someday one can tailor-make programmable devices at nano-scale. However, before producing such devices, basic research is needed on the right primitives for these devices so that they can be used effectively in applications relevant for programmable matter. I will present the amoebot model and show that it can be used effectively for typical applications like shape formation and coating. In addition to that, I will discuss possible extensions of the amoebot model and present first results for these.

Christoph Lenzen • Max Planck Institut Saarbrücken, Germany
The many Faces of Clock Synchronization

Abstract: In this talk I present the clock synchronization problem – many times. This research area’s natural habitat is distributed computing, as by definition synchronizing clocks implies a distributed system. However, as I will seek to convince you in this talk, it has become a key issue in the development of reliable, scalable hardware systems as well. I will discuss a wide range of theoretical and practical issues arising from the challenge of providing a precise time base in face of various sources of uncertainty and faults, and point at a number of open problems that I consider of interest to the distributed computing community.

SIROCCO Prize lecture

Shmuel Zaks • Technion, Israel
Online and approximation algorithms for optical networks and scheduling

Accepted papers

Alexander Spiegelman and Idit Keidar
On Liveness of Dynamic Storage [abstract] Abstract: Dynamic distributed storage algorithms such as DynaStore, Reconfigurable Paxos, RAMBO, and RDS, do not ensure liveness (wait-freedom) in asynchronous runs with infinitely many reconfigurations. We prove that this is inherent for asynchronous dynamic storage algorithms. Our result holds even if only one process may fail, provided that machines that were successfully removed from the system's configuration can be switched off by a system administrator. To circumvent this result, we define a dynamic eventually perfect failure detector, and present an algorithm that uses it to emulate wait-free dynamic atomic storage. Though some of the previous algorithms used failure detectors as well, to the best of our knowledge, our algorithm is the first to ensure liveness for all operations without restricting the reconfiguration rate.

Yoav Rodeh and Amos Korman
Parallel Search with no Coordination [abstract] Abstract: We consider a parallel version of a classical Bayesian search problem. $k$ agents are looking for a treasure that is placed in one of the boxes indexed by $N^+$ according to a known distribution $p$. The aim is to minimize the expected time until the first agent finds it. Searchers run in parallel where at each time step each searcher can ``peek'' into a box. A basic family of algorithms which are inherently robust is \emph{non-coordinating} algorithms. Such algorithms act independently at each searcher, differing only by their probabilistic choices. We are interested in the price incurred by employing such algorithms when compared with the case of full coordination.
We first show that there exists a non-coordination algorithm, that knowing only the relative likelihood of boxes according to $p$, has expected running time of at most $10+4(1+\frac{1}{k})^2 T$, where $T$ is the expected running time of the best fully coordinated algorithm. This result is obtained by applying a refined analysis to the main algorithm suggested by Fraigniaud, Korman and Rodeh in STOC'16, which was designed for the context of parallel linear search.
We then describe an optimal non-coordinating algorithm for the case where the distribution $p$ is known. The running time of this algorithm is difficult to analyse in general, but we calculate it for several examples. In the case where $p$ is uniform over a finite set of boxes, then the algorithm just checks boxes uniformly at random among all non-checked boxes and is essentially $2$ times worse than the coordinating algorithm. We also show simple algorithms for Pareto distributions over $M$ boxes. That is, in the case where $p(x) \sim 1/x^b$ for $0< b < 1$, we suggest the following algorithm: at step $t$ choose uniformly from the boxes unchecked in $\{1, \ldots, \min(M, \lfloor t/\sigma \rfloor)\}$, where $\sigma = b/(b + k - 1)$. It turns out this algorithm is asymptotically optimal, and runs about $2+b$ times worse than the case of full coordination.

Arnaud Casteigts, Ralf Klasing, Yessin M. Neggaz, and Joseph G. Peters
A Generic Framework for Computing Parameters of Sequence-based Dynamic Graphs [abstract] Abstract: We presented in [11] an algorithm for computing a parameter called T-interval connectivity of dynamic graphs which are given as a sequence of static graphs. This algorithm operates at a high level, manipulating the graphs in the sequence as atomic elements with two types of operations: a composition operation and a test operation. The algorithm is optimal in the sense that it uses only O(δ) composition and test operations, where δ is the length of the sequence. In this paper, we generalize this framework to use various composition and test operations, which allows us to compute other parameters using the same high-level strategy that we used for T-interval connectivity. We illustrate the framework through the study of three minimization problems, namely BOUNDED-REALIZATION-OF-THE-FOOTPRINT, TEMPORAL-DIAMETER, and ROUND-TRIP-TEMPORAL-DIAMETER, which refer to various properties of dynamic graphs.

Yann Disser, Frank Mousset, Andreas Noever, Nemanja Skoric, and Angelika Steger
A general lower bound for collaborative tree exploration [abstract] Abstract: We consider collaborative graph exploration with a set of k agents. All agents start at a common vertex of an initially unknown graph and need to collectively visit all other vertices. We assume agents are deterministic, vertices are distinguishable, moves are simultaneous, and we allow agents to communicate globally. For this setting, we give the first non-trivial lower bounds that bridge the gap between small (k <= sqrt(n)) and large (k >= n) teams of agents. Remarkably, our bounds tightly connect to existing results in both domains.
First, we significantly extend a lower bound of Omega(log k / log log k) by Dynia et al. on the competitive ratio of a collaborative tree exploration strategy to the range k <= n log^c n for any positive integer c. Second, we provide a tight lower bound on the number of agents needed for any competitive exploration algorithm. In particular, we show that any collaborative tree exploration algorithm with k = Dn^(1+o(1)) agents has a competitive ratio of omega(1), while Dereniowski et al. gave an algorithm with k = Dn^(1+epsilon) agents and competitive ratio O(1), for any constant epsilon > 0 and with D denoting the diameter of the graph. Lastly, we show that, for any exploration algorithm using k = n agents, there exist trees of arbitrarily large height D that require Omega(D^2) rounds, and we provide a simple algorithm that matches this bound for all trees.

Blanchard Peva and Rachid Guerraoui
On The Smallest Grain of Salt to Get a Unique Identity [abstract] Abstract: We study the fundamental \emph{enumeration} problem in asynchronous message-passing networks. Anonymous processes have to eventually decide on pairwise distinct identifiers, despite all starting in the same initial state. It is known since Angluin's seminal result \cite{Ang80} that some \emph{grain of salt} is required for distributed algorithms to solve the problem, e.g., the system needs to have a non-symmetrical topology or unbiased independent random bits.
The starting point of this paper is the observation that these approaches demand too strong assumptions. In short, by adding \emph{time} to the picture, we show that the enumeration problem can be solved with far less. The idea is to consider a schedule of events in a distributed system as a \emph{space-time structure} that is \emph{gradually learnt} by the processes. We introduce the notion of \emph{divergence time} which essentially measures the time by which the causal order induced by the system schedule has differentiated all the processes.
We prove lower bounds on the running time of any algorithm solving enumeration in terms of divergence time. In particular, we show that any adversary scheduler against which the enumeration problem can be solved \emph{necessarily} select schedules with \emph{finite divergence time}.
We prove that this last condition is \emph{sufficient} : we present the \torche algorithm which solves enumeration for all schedules with finite divergence time. In this sense, having finite divergence time is the smallest grain of salt required to solve the enumeration problem.

Laurent Feuilloley
How Long It Takes for an Ordinary Node with an Ordinary ID to Output? [abstract] Abstract: In the context of distributed synchronous computing, processors perform in rounds, and the time-complexity of a distributed algorithm is classically defined as the number of rounds before all computing nodes have output. Hence, this complexity measure captures the running time of the slowest node(s). In this paper, we are interested in the running time of the ordinary nodes, to be compared with the running time of the slowest nodes. The \emph{node-averaged} time-complexity of a distributed algorithm on a given instance is defined as the average, taken over every node of the instance, of the number of rounds before that node output. We compare the node-averaged time-complexity with the classical one in the standard $\LOCAL$ model for distributed network computing. We show that there can be an exponential gap between the node-averaged time-complexity and the classical time-complexity, as witnessed by, e.g., leader election. Our first main result is a positive one, stating that, in fact, the two time-complexities behave the same for a large class of problems on very sparse graphs. In particular, we show that, for $\LCL$ problems on cycles, the node-averaged time complexity is of the same order of magnitude as the ``slowest node'' time-complexity.
In addition, in the $\LOCAL$ model, the time-complexity is computed as a worst case over all possible identity assignments to the nodes of the network. In this paper, we also investigate the \emph{ID-averaged} time-complexity, when the number of rounds is averaged over all possible identity assignments. Our second main result is that the ID-averaged time-complexity is essentially the same as the expected time-complexity of \emph{randomized} algorithms (where the expectation is taken over all possible random bits used by the nodes, and the number of rounds is measured for the worst-case identity assignment).
Finally, we study the node-averaged ID-averaged time-complexity. We show that 3-coloring the $n$-node ring requires $\Theta(\log^*n)$ rounds if the number of rounds is averaged over the nodes, or if the number of rounds is averaged over the identity assignments. In contrast, we show that 3-coloring the ring requires only $O(1)$ rounds if the number of rounds is averaged over the nodes, and over the identity assignments.

Sebastian Brandt, Klaus-Tycho Förster, Benjamin Richner, and Roger Wattenhofer
Wireless Evacuation on m Rays with k Searchers [abstract] Abstract: We study the online problem of evacuating k robots on m concurrent rays to a single unknown exit. All k robots start on the same point s, not necessarily on the junction j of the m rays, move at unit speed, and can communicate wirelessly. The goal is to minimize the competitive ratio, i.e., the ratio between the time it takes to evacuate all robots to the exit and the time it would take if the location of the exit was known in advance, on a worst-case instance.
When k = m, we show that a simple waiting strategy yields a competitive ratio of 4 and present a lower bound of 2 + \sqrt{7/3} \approx 3.52753 for all k = m \geq 3. For k = 3 robots on m = 3 rays, we give a class of parametrized algorithms with a nearly matching competitive ratio of 2 + \sqrt{3} \approx 3.73205.
We also present an algorithm for 1 < k < m, achieving a competitive ratio of 1 + 2(m - 1)/k \cdot (1 + k/(m - 1))^{1 + (m-1)/k}, obtained by parameter optimization on a geometric search strategy. Interestingly, the robots can be initially oblivious to the value of m > 2. Lastly, by using a simple but fundamental argument, we show that for k < m robots, no algorithm can reach a competitive ratio better than 3 + 2\lfloor (m-1)/k \rfloor, for every k, m with k < m.

Jurek Czyzowicz, Konstantinos Georgiou, Maxime Godon, Evangelos Kranakis, Danny Krizanc, Wojciech Rytter, and Michal Wlodarczyk
Evacuation from a Disc in the Presence of a Faulty Robot [abstract] Abstract: We consider the evacuation problem on a circle for three robots, at most one of which is faulty. The three robots search for an exit placed at an unknown location on the perimeter of the circle. During the search, robots can communicate wirelessly at any distance. The goal is to minimize the time that the latest non-faulty robot reaches the exit.
Our main contributions are two highly efficient and non intuitive evacuation protocols for the non-faulty robots to reach the exit in two well-studied fault-models, Crash and Byzantine. Moreover, we complement our positive results by lower bounds in both models. A summary of our results reads as follows: \begin{itemize} \item {\em Case of Crash Faults:} Lower Bound $ \approx 5.082$; Upper Bound $ \approx 6.309$, \item {\em Case of Byzantine Faults:} Lower Bound $ \approx 5.948$; Upper Bound $ \approx 6.921$, \end{itemize} For comparison, it is known (see~\cite{CGGKMP}) that in the case of three {\em non-faulty} robots with wireless communication we have a lower bound of $4.159$, and an upper bound.of $4.219$ for evacuation, while for two {non-faulty} robots $1 + 2\pi/3 + \sqrt{3} \approx 4.779$ is a tight upper and lower bound for evacuation.

Barun Gorain and Andrzej Pelc
Short Labeling Schemes for Topology Recognition in Wireless Tree Networks [abstract] Abstract: We consider the problem of topology recognition in wireless (radio) networks modeled as undirected graphs. Topology recognition is a fundamental task in which every node of the network has to output a map of the underlying graph i.e., an isomorphic copy of it, and situate itself in this map. In wireless networks, nodes communicate in synchronous rounds. In each round a node can either transmit a message to all its neighbors, or stay silent and listen. At the receiving end, a node $v$ hears a message from a neighbor $w$ in a given round, if $v$ listens in this round, and if $w$ is its only neighbor that transmits in this round. Nodes have labels which are (not necessarily different) binary strings. The length of a labeling scheme is the largest length of a label. We concentrate on wireless networks modeled by trees, and we investigate two problems. \begin{itemize} \item What is the shortest labeling scheme that permits topology recognition in all wireless tree networks of diameter $D$ and maximum degree $\Delta$? \item What is the fastest topology recognition algorithm working for all wireless tree networks of diameter $D$ and maximum degree $\Delta$, using such a short labeling scheme? \end{itemize} We are interested in deterministic topology recognition algorithms. For the first problem, we show that the minimum length of a labeling scheme allowing topology recognition in all trees of maximum degree $\Delta \geq 3$ is $\Theta(\log\log \Delta)$. For such short schemes, used by an algorithm working for the class of trees of diameter $D\geq 4$ and maximum degree $\Delta \geq 3$, we show almost matching bounds on the time of topology recognition: an upper bound $O(D\Delta)$, and a lower bound $\Omega(D\Delta^{\epsilon})$, for any constant $\epsilon<1$.
Our upper bounds are proven by constructing a topology recognition algorithm using a labeling scheme of length $O(\log\log \Delta)$ and using time $O(D\Delta)$. Our lower bounds are proven by constructing a class of trees for which any topology recognition algorithm must use a labeling scheme of length at least $\Omega(\log \log\Delta)$, and a class of trees for which any topology recognition algorithm using a labeling scheme of length $O(\log\log \Delta)$ must use time at least $\Omega(D\Delta^{\epsilon})$, on some tree of this class.

Lata Narayanan and Kangkang Wu
How to choose friends strategically [abstract] Abstract: Alice wants to join a new social network, and influence its members to adopt a new product or idea. Each person v in the network has a certain threshold t(v) for activation, i.e adoption of the product or idea. If v has at least t(v) activated neighbors, then v will also become activated. If Alice wants to make k new friends in the network, and thereby activate the most number of people, how should she choose these friends? We study the problem of choosing the k people in the network to befriend, who will in turn activate the maximum number of people. This Maximum Influence with Links Problem has applications in viral marketing and the study of epidemics. We show that the solution can be quite different from the related and widely studied influence maximization problem where the objective is to choose a seed or target set with maximum influence. We prove that the Maximum Influence with Links problem is NP-complete even for bipartite graphs in which all nodes have threshold 1 or 2. In contrast, we give polynomial time algorithms that find optimal solutions for the problem for trees, paths, cycles, and cliques.

Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, and Guido Proietti
Effective Edge-Fault-Tolerant Single-Source Spanners via Best (or Good) Swap Edges [abstract] Abstract: Computing \emph{all the best swap edges} (ABSE) of a spanning tree $T$ of a given $n$-vertex and $m$-edge undirected and weighted graph $G$, is by now a classic fault-tolerant algorithmic problem. Indeed, it presides over a very successful way of coping with a transient edge failure in a graph: just replace the failing edge with its respective swap edge, so as that the connectivity is promptly reestablished by minimizing the rerouting and set-up costs. Quite naturally, to optimize the transition to the swap tree, each swap edge has to be chosen carefully, in such a way that the obtained swap tree is a best possible one w.r.t. some prominent feature of the initial tree $T$. In this paper, we solve the ABSE problem for the case in which $T$ is a \emph{shortest-path tree}, and our two selected swap criteria aim to minimize either the \emph{maximum} or the \emph{average stretch} in the swap tree of all the paths emanating from the source. Having these criteria in mind, the obtained structures can then be reviewed as \emph{edge-faut-tolerant single-source spanners}. For them, we propose two efficient algorithms running in $O(m n +n^2 \log n)$ and $O(m n \log \alpha(m,n))$ time, respectively, and we show that the guaranteed (either maximum or average, respectively) stretch factor is equal to 3, and this is tight. Moreover, for the maximum stretch, we also propose an almost linear $O(m \log \alpha(m,n))$ time algorithm computing a set of \emph{good} swap edges, each of which will guarantee a relative approximation factor on the maximum stretch of $3/2$ (tight) as opposed to that provided by the corresponding BSE. Surprisingly, no previous results were known for these two very natural swap problems.

Pascal Bemmann, Felix Biermeier, Jan Bürmann, Arne Kemper, Till Knollmann, Steffen Knorr, Nils Kothe, Alexander Mäcker, Manuel Malatyali, Friedhelm Meyer Auf der Heide, Sören Riechers, Johannes Schaefer, and Jannik Sundermeier
Monitoring of Domain-Related Problems in Distributed Data Streams [abstract] Abstract: Consider a network in which n distributed nodes are connected to a single server. Each node continuously observes a data stream consisting of one value per discrete time step. The server has to, in any time step t, compute an output defined over all values currently observed across all streams. To do so, nodes can send messages to the server and the server can broadcast messages to the nodes. The objective is the minimisation of communication while allowing the server to compute the desired output. We consider problems related to the domain D_t defined to be the set of values observed by at least one node at time t. We provide randomised algorithms for monitoring D_t, (approximations of) the size |D_t| and the frequencies of all members of D_t. Besides classical worst-case analyses, we also obtain improved bounds when inputs are parameterised according to the similarity of observations between consecutive time steps. This parameterisation allows to exclude inputs with rapid and heavy changes, which usually lead to the worst-case bounds but are rather artificial in typical scenarios.

Rafail Ostrovsky, Mor Perry, and Will Rosenbaum
Space-Time Tradeoffs for Distributed Verification [abstract] Abstract: Verifying that a network configuration satisfies a given boolean predicate is a fundamental problem in distributed computing. Many variations of this problem have been studied, for example, in the context of proof labeling schemes (PLS), locally checkable proofs (LCP), and non-deterministic local decision (NLD). In all of these contexts, verification time is assumed to be constant. Korman, Kutten and Masuzawa [PODC 2011] presented a proof-labeling scheme for MST, with poly-logarithmic verification time, and logarithmic memory at each vertex.
In this paper we introduce the notion of a t-PLS, which allows the verification procedure to run for super-constant time. Our work analyzes the tradeoffs of t-PLS between time, label size, message length, and computation space. We construct a universal t-PLS and prove that it uses the same amount of total communication as a known one-round universal PLS, and t factor smaller labels. In addition, we provide a general technique to prove lower bounds for space-time tradeoffs of t-PLS. We use this technique to show an optimal tradeoff for testing that a network is acyclic (cycle free). Our optimal t-PLS for acyclicity uses label size and computation space O((log n)/t). We further describe a recursive O(log* n) space verifier for acyclicity which does not assume previous knowledge of the run-time t.

Mikaël Rabie
Global Versus Local Computations: Fast Computing with Identifiers [abstract] Abstract: This paper studies what can be computed by using probabilistic local interactions with agents with a very restricted power in polylogarithmic parallel time. It is known that if agents are only finite state (corresponding to the Population Protocol model by Angluin {\em et al.}), then only semilinear predicates over the global input can be computed. In fact, if the population starts with a unique leader, these predicates can even be computed in a polylogarithmic parallel time. If identifiers are added (corresponding to the Community Protocol model by Guerraoui and Ruppert), then more global predicates over the input multiset can be computed. Local predicates over the input sorted according to the identifiers can also be computed, as long as the identifiers are ordered. The time of some of those predicates might require exponential parallel time. In this paper, we consider what can be computed with Community Protocol in a polylogarithmic number of parallel interactions. We introduce the class $CPPL$ corresponding to protocols that use $O(n\log^kn)$, for some $k$, expected interactions to compute their predicates, or equivalently a polylogarithmic number of parallel expected interactions. We provide some computable protocols, some boundaries of the class, using the fact that the population can compute its size. We also prove two impossibility results providing some arguments showing that local computations are no longer easy: the population does not have the time to compare a linear number of consecutive identifiers. The {\em Linearly Local} languages, such that the rational language $(ab)^*$, are not computable.

Magnus M. Halldorsson, Stephan Holzer, and Evangelia Anna Markatou
Leader Election in SINR Model with Arbitrary Power Control [abstract] Abstract: In this article, we study the Leader Election Problem in the Signal-to-Interference-plus-Noise-Ratio (SINR) model where nodes can adjust their transmission power. We show that in this setting it is possible to solve the leader election problem in two communication rounds, with high probability. Previously, it was known that Omega(log n) rounds were sufficient and necessary when using uniform power, where n is the number of nodes in the network.
We then examine how much power control is needed to achieve fast leader election. We show that any 2-round leader election algorithm in the SINR model running correctly w.h.p. requires a power range 2^{Omega(n)} even when n is known. We match this with an algorithm that uses power range 2^{\tilde{Theta}(n)}, when n is known and 2^{\tilde{O}(n^{1.5})} when n is not known. We also explore tradeoffs between time and power used, and show that to elect a leader in t rounds, a power range exp(n^{1/Theta(t)}) is sufficient and necessary.

Magnus M. Halldorsson and Christian Konrad
Improved Distributed Algorithms for Coloring Interval Graphs with Application to Multicoloring Trees [abstract] Abstract: We give a distributed (1+ε)-approximation algorithm for the minimum vertex coloring problem on interval graphs, which runs in the LOCAL model and operates in O((1/ε) log* n) rounds. If nodes are aware of their interval representations, then the algorithm can be adapted to the CONGEST model using the same number of rounds. Prior to this work, only constant factor approximations using O(log* n) rounds were known. Linial's ring coloring lower bound implies that the dependency on log* n cannot be improved. We further prove that the dependency on 1/ε is also optimal.
To obtain our CONGEST model algorithm, we develop a color rotation technique that may be of independent interest. We demonstrate that color rotations can also be applied to obtain a (1+ε)-approximate multicoloring of directed trees in O((1/ε) log* n) rounds.

Giuseppe Antonio Di Luna, Paola Flocchini, Linda Pagli, Giuseppe Prencipe, Nicola Santoro and Giovanni Viglietta
Gathering in Dynamic Rings [abstract] Abstract: The gathering (or multi-agent rendezvous) problem requires a set of mobile agents, arbitrarily positioned at different nodes of a network to group within finite time at the same location, not fixed in advanced.
The extensive existing literature on this problem shares the same fundamental assumption: the topological structure does not change during the rendezvous or the gathering; this is true also for those investigations that consider faulty nodes. In other words, they only consider static graphs.
In this paper we start the investigation of gathering in dynamic graphs, that is networks where the topology changes continuously and at unpredictable locations. We study the feasibility of gathering mobile agents, identical and without explicit communication capabilities, in a dynamic ring of anonymous nodes; the class of dynamics we consider is the classic 1-interval-connectivity. We focus on the impact that factors such as chirality (i.e., a common sense of orientation) and cross detection (i.e., the ability to detect, when traversing an edge, whether some agent is traversing it in the other direction), have on the solvability of the problem; and we establish several results.
We provide a complete characterization of the classes of initial configurations from which the gathering problem is solvable in presence and in absence of cross detection and of chirality. The feasibility results of the characterization are all constructive: we provide distributed algorithms that allow the agents to gather within low polynomial time. In particular, the protocols for gathering with cross detection are time optimal.
We also show that cross detection is a powerful computational element. We prove that, without chirality, knowledge of the ring size is strictly more powerful than knowledge of the number of agents; on the other hand, with chirality, knowledge of n can be substituted by knowledge of k, yielding the same classes of feasible initial configurations.
From our investigation it follows that, for the gathering problem, the computational obstacles created by the dynamic nature of the ring can be overcome by the presence of chirality or of cross-detection.

François Bonnet, Quentin Bramas, Xavier Défago, and Thanh Dang Nguyen
Killing Nodes as a Countermeasure to Virus Expansion [abstract] Abstract: The spread of a virus and the containment of such spread have been widely studied in the literature. These two problems can be abstracted as a two-players stochastic game in which one side tries to spread the infection to the entire system, while the other side aims to contain the infection to a finite area. Three parameters play a particularly important role: (1) the probability $p$ of successful infection, (2) the topology of the network, and (3) the probability $\alpha$ that a strategy message has priority over the infection.
This paper studies the effect of killing strategies, where a node sacrifices itself and possibly some of its neighbors, to contain the spread of a virus in an infinite grid. Our contribution is threefold: (1) We prove that the simplest killing strategy is equivalent to the problem of site percolation; (2) when killing messages are priority, we prove that there always exists a killing strategy that contains a virus, for any probability $0<=p<1$; In contrast, (3) when killing message are not priority, there is not always a killing strategy, and we study the virus propagation for various ${0<=\alpha <= 1}$.

Keren Censor-Hillel, Ami Paz, and Mor Perry
Approximate Proof-Labeling Schemes [abstract] Abstract: We study a new model of verification of boolean predicates over distributed networks. Given a network configuration, the proof-labeling scheme (PLS) model defines a distributed proof in the form of a label that is given to each node, and all nodes locally verify that the network configuration satisfies the desired boolean predicate by exchanging labels with their neighbors. The \emph{proof size} of the scheme is defined to be the maximum size of a label.
In this work, we extend this model by defining the \emph{approximate proof-labeling scheme} (APLS) model. In this new model, the predicates for verification are of the form $\psi\le \varphi$, where $\psi, \varphi: \cF \to \bbN$ for a family of configurations $\cF$. Informally, the predicates considered in this model are a comparison between two values of the configuration. As in the PLS model, nodes exchange labels in order to locally verify the predicate, and all must accept if the network satisfies the predicate. The soundness condition is relaxed with an approximation ration $\alpha$, so that only if $\psi> \alpha\varphi$ some node must reject.
We show that in the APLS model, the proof size can be much smaller than the proof size of the same predicate in the PLS model. Moreover, we prove that there is a tradeoff between the approximation ratio and the proof size.

Tomasz Jurdzinski, Michał Różański, and Grzegorz Stachowiak
Token Traversal in Ad Hoc Wireless Networks via Implicit Carrier Sensing [abstract] Abstract: Communication problems in ad hoc wireless networks have been already widely studied under the SINR model, but a vast majority of results concern networks with constraints on connectivity, so called strongly-connected networks. In such networks, connectivity is dened based on highly reliable links, that is, where both ends are located far closer from their transmission boundaries. What happens if the network is not strongly-connected, e.g., it contains some long but still viable \shortcut links" connecting transmission boundaries? It is known that even a single broadcast in such ad hoc weakly-connected networks with uniform transmission powers requires (n) communication rounds, where n is the number of nodes in the network. The result holds even if the network is of constant diameter, algorithms may use randomization, nodes of the network have access to their own coordinates and have carrier sensing capabilities. The best up-to-date (randomized) distributed algorithm, designed by Daum et al. [12], accomplishes broadcast task in O(n log2 n) communication rounds with high probability. In this work, inspired by the work on broadcasting, we show a novel deterministic distributed implementation of token traversal | a fundamental tool in distributed systems | in the SINR model with uniform transmission powers and no restriction on connectivity. We show that it is ecient even in a very harsh model of weakly-connected networks without GPS, carrier sensing and other helping features. We apply this method to span a traversal tree and accomplish broadcast in O(n logN) communication rounds, deterministically, provided nodes are equipped with unique IDs in the range [1;N] for some integer N n. This result implies an O(n log n)-round randomized solution that does not require ids, matching the lower bound (n log n) proved in this work and thus closing the gap left in [12]. Our implementation of token traversal routine, ecient in terms of time and memory, is based on a novel implicit algorithmic carrier sensing method and a new type of selectors, which might be of independent interest and applicable to other communication tasks in distributed ad hoc setting.

Karol Gotfryd, Marek Klonowski, and Dominik Pajak
On Location Hiding in Distributed Systems [abstract] Abstract: We consider the following problem - a group of mobile agents perform some task on a terrain modeled as a graph. In a given moment of time an adversary gets an access to the graph and positions of the agents. Shortly before adversary's observation the mobile agents have a chance to relocate themselves in order to hide their initial configuration. We assume that the initial configuration may possibly reveal to the adversary some information about the task they performed. Clearly agents have to change their location in possibly short time using minimal energy. In our paper we introduce a definition of a well hiding algorithm in which the starting and final configurations of the agents have small mutual information. Then we discuss the influence of various features of the model on the running time of the optimal well-hiding algorithm. We show that if the topology of the graph is known to the agents, then the number of steps proportional to the diameter of the graph is sufficient and necessary. In the unknown topology scenario we only consider a single agent case. We first show that the task is impossible in the deterministic case if the agent has no memory. Then we present a polynomial randomized algorithm. Finally in the model with memory we show that the number of steps proportional to the number of edges of the graph is sufficient and necessary. In some sense we investigate how complex is the problem of "losing" information about location (both physical and logical) for different settings.