Abstract: In this work, we study the following basic question: “How much parallelism does a distributed task permit?” Our definition of parallelism (or symmetry) here is not in terms of speed, but in terms of identical roles that processes have at the same time in the execution. For example, we may ask: “Can a given task be solved by a protocol that always has at least two processes in the same role at the same time?” (i.e., by a protocol that never elects a unique leader). We choose to initiate this study in population protocols, a very simple model that not only allows for a straightforward definition of what a role is, but also encloses the challenge of isolating the properties that are due to the protocol from those that are due to the adversary scheduler, who controls the interactions between the processes. In particular, we define the role of a process at a given time to be equivalent to the state of the process at that time. Moreover, we isolate the symmetry that is due to the protocol (inherent symmetry) by focusing on those schedules that maximize symmetry for that protocol and observing how much symmetry breaking the protocol is forced to achieve in order to solve the problem. To allow for such symmetry maximizing schedules we consider parallel schedulers that in every step may select a whole collection of pairs of nodes (up to a perfect matching) to interact and not just a single pair. Based on these definitions of symmetric computation, we (i) give a partial characterization of the set of predicates on input assignments that can be stably computed with maximum symmetry, i.e., $\Theta(N_\min)$, where $N_\min$ is the minimum multiplicity of a state in the initial configuration, and (ii) we turn our attention to the remaining predicates (that have some essentially different properties) and prove a strong impossibility result for the parity predicate: the inherent symmetry of any protocol that stably computes it is upper bounded by a constant that depends on the size of the protocol.

Abstract: Like distributed systems, biological multicellular processes are subject to dynamic changes and a biological system will not pass the survival-of-the-fittest test unless it exhibits certain features that enable fast recovery from these changes. In most cases, the types of dynamic changes a biological process may experience and its desired recovery features differ from those traditionally studied in the distributed computing literature. In particular, a question seldomly asked in the context of distributed digital systems and that is crucial in the context of biological cellular networks, is whether the system can keep the changing components confined so that only nodes in their vicinity may be affected by the changes, but nodes sufficiently far away from any changing component remain unaffected. Based on this notion of confinement, we propose a new metric for measuring the dynamic changes recovery performance in distributed network algorithms operating under the Stone Age model (Emek & Wattenhofer, PODC 2013), where the class of dynamic topology changes we consider includes inserting/deleting an edge, deleting a node together with its incident edges, and inserting a new isolated node. Our main technical contribution is a distributed algorithm for maximal independent set (MIS) in synchronous networks subject to these topology changes that performs well in terms of the aforementioned new metric. Specifically, our algorithm guarantees that nodes which do not experience a topology change in their immediate vicinity are not affected and that all surviving nodes (including the affected ones) perform $O((C + 1) \log^{2} n)$ computationally-meaningful steps, where $C$ is the number of topology changes; in other words, each surviving node performs $O(\log^{2} n)$ steps when amortized over the number of topology changes. This is accompanied by a simple example demonstrating that the linear dependency on $C$ cannot be avoided.

Abstract: A fundamental question in the setting of anonymous graphs concerns the ability of nodes to spontaneously break symmetries, based on their local perception of the network. In contrast to previous work, which focuses on symmetry breaking under arbitrary port labelings, in this paper, we study the following design question: Given an anonymous graph $G$ without port labels, how to assign labels to the ports of $G$, in interval form at each vertex, so that symmetry breaking can be achieved using a message-passing protocol requiring as few rounds of synchronous communication as possible? More formally, for an integer $l>0$, the truncated view $\mathcal{V}_l(v)$ of a node $v$ of a port-labeled graph is defined as a tree encoding labels encountered along all walks in the network which originate from node $v$ and have length at most $l$, and we ask about an assignment of labels to the ports of $G$ so that the views $\mathcal{V}_l(v)$ are distinct for all nodes $v\in V$, with the goal being to minimize $l$. We present such efficient port labelings for any graph $G$, and we exhibit examples of graphs showing that the derived bounds are asymptotically optimal in general. More precisely, our results imply the following statements. 1. For any graph $G$ with $n$ nodes and diameter $D$, a uniformly random port labeling achieves $l = O(\min(D,\log n))$, w.h.p. 2. For any graph $G$ with $n$ nodes and diameter $D$, it is possible to construct in polynomial time a labeling that satisfies $l = O(\min(D,\log n))$. 3. For any integers $n\geq 2$ and $D \leq \log_2 n-\log_2\log_2 n$, there exists a graph $G$ with $n$ nodes and diameter $D$ which satisfies $l \geq 1/2 \cdot D - 5/2$.

Abstract: The fooling pairs method is one of the standard methods for proving lower bounds for deterministic two-player communication complexity. We study fooling pairs in the context of randomized communication complexity. We show that every fooling pair induces far away distributions on transcripts of private-coin protocols. We use the above to conclude that the private-coin randomized $\epsilon$-error communication complexity of a function $f$ with a fooling set $\mathcal{S}$ is at least order $\log(\log(|\mathcal{S}|)/\epsilon)$. This relationship was earlier known to hold only for constant values of $\epsilon$ [Yao, Hastad-Wigderson]. The bound we prove is tight, for example, for the equality and greater-than functions. As an application, we exhibit the following dichotomy: for every boolean function $f$ and integer $n$, the $(1/3)$-error public-coin randomized communication complexity of the function $\bigvee_{i=1}^{n}f(x_i,y_i)$ is either at most $c$ or at least $n/c$, where $c>0$ is a universal constant.

Abstract: In simultaneous number-in-hand multi-party communication protocols, we have k players, who each receive a private input, and wish to compute a joint function of their inputs. The players simultaneously each send a single message to a referee, who then outputs the value of the function. The cost of the protocol is the total number of bits sent to the referee. For two players, it is known that giving the players a public (shared) random string is much more useful than private randomness: public-coin protocols can be unboundedly better than deterministic protocols, while private-coin protocols can only give a quadratic improvement on deterministic protocols. We extend the two-player gap to multiple players, and show that the private-coin communication complexity of a $k$-player function $f$ is $\Omega(\sqrt{D(f)})$ for any $k \geq 2$. Perhaps surprisingly, this bound is tight: although one might expect the gap between private-coin and deterministic protocols to grow with the number of players, we show that the All-Equality function, where each player receives $n$ bits of input and the players must determine if their inputs are all the same, can be solved by a private-coin protocol with $\tilde{O}(\sqrt{nk}+k)$ bits. Since All-Equality has deterministic complexity $\Theta(nk)$, this shows that sometimes the gap scales only as the square root of the number of players, and consequently the number of bits each player needs to send actually decreases as the number of players increases. We also consider the Exists-Equality function, where we ask whether there is a pair of players that received the same input, and prove a nearly-tight bound of $\tilde{\Theta}(k \sqrt{n})$ for it.

Abstract: We present a uniform approach to derive message-time tradeoffs and message lower bounds for synchronous distributed computations using results from communication complexity theory. Since the models used in the classical theory of communication complexity are inherently asynchronous, lower bounds do not directly apply in a synchronous setting. To address this issue, we show a general result called Synchronous Simulation Theorem (SST) which allows to obtain message lower bounds for synchronous distributed computations by leveraging lower bounds on communication complexity. The SST is a by-product of a new efficient synchronizer for complete networks, called $\sigma$, which has simulation overheads that are only logarithmic in the number of synchronous rounds with respect to both time and message complexity in the CONGEST model. The $\sigma$ synchronizer is particularly efficient in simulating synchronous algorithms that employ silence. In particular, a curious property of this synchronizer, which sets it apart from its predecessors, is that it is time-compressing, and hence in some cases it may result in a simulation that is faster than the original execution. While the SST gives near-optimal message lower bounds up to large values of the number of allowed synchronous rounds $r$ (usually polynomial in the size of the network), it fails to provide meaningful bounds when a very large number of rounds is allowed. To complement the bounds provided by the SST, we then derive message lower bounds for the synchronous message-passing model that are unconditional, that is, independent of $r$, via direct reductions from multi-party communication complexity. We apply our approach to show (almost) tight message-time tradeoffs and message lower bounds for several fundamental problems in the synchronous message-passing model of distributed computation. These include sorting, matrix multiplication, and many graph problems. All these lower bounds hold for any distributed algorithms, including randomized Monte Carlo algorithms.

Abstract: This paper surveys recent results on fault-tolerant consensus in message-passing networks. We focus on two categories of works: (i) new problem formulations (including input domain, fault model, network model...etc.), and (ii) practical applications. For the second part, we focus on Crash Fault-Tolerant (CFT) systems that use Paxos or Raft, and Byzantine Fault-Tolerant (BFT) systems. We also briefly discuss Bitcoin, which can be related to solving Byzantine consensus in anonymous systems.

Abstract: Adaptive renaming can be viewed as a coordination task involving a set of asynchronous agents, each aiming at grabbing a single resource out of a set of resources totally ordered by their desirability. Similarly, musical chairs is also defined as a coordination task involving a set of asynchronous agents, each aiming at picking one of a set of available ressources, where every agent comes with an a priori preference for some ressource. We foresee instances in which some combinations of resources are allowed, while others are disallowed. We model these constraints, i.e., the restrictions on the ability to use some combinations of ressources, as an undirected graph whose nodes represent the ressources, and an edge between two ressources indicates that these two ressources cannot be used simultaneously. In other words, the sets of ressources that are allowed are those which form independent sets in the graph. E.g., renaming and musical chairs are specific cases where the graph is stable (i.e., it contains no edges). As for musical chairs, we assume that each agent comes with an a priori preference for some ressource. If an agent’s preference is not in conflict with the preferences of the other agents, then this preference can be grabbed by the agent. Otherwise, the agents must coordinate to resolve their conflicts, and potentially choose non preferred resources. We investigate the following problem: given a graph, what is the maximum number of agents that can be accommodated subject to non-altruistic behaviors of early arriving agents? We entirely solve this problem under the restriction that agents which cannot grab their preferred resources must then choose a resource among the nodes of a predefined independent set. However, the general case, where agents which cannot grab their preferred resource are then free to choose any resource, is shown to be far more complex. In particular, just for cyclic constraints, the problem is surprisingly difficult. Indeed, we show that, intriguingly, the natural algorithm inspired from optimal solutions to adaptive renaming or musical chairs is sub-optimal for cycles, but proven to be at most 1 to the optimal. The main message of this paper is that finding optimal solutions to the coordination with constraints and preferences task requires to design “dynamic” algorithms, that is, algorithms of a completely different nature than the “static” algorithms used for, e.g., renaming.

Abstract: We consider the problem of implementing general shared-memory objects on top of write-once bits, which can be changed from $0$ to $1$ but not back again. In a sequential setting, write-once memory (WOM) codes have been developed that allow simulating memory that support multiple writes, even of large values, setting an average of $1+o(1)$ write-once bits per write. We show that similar space efficiencies can be obtained in a concurrent setting, though at the cost of high time complexity and fixed bound on the number of write operations. As an alternative, we give an implementation that permits unboundedly many writes and has much better amortized time complexity, but at the cost of unbounded space complexity. Whether one can obtain both low time complexity and low space complexity in the same implementation remains open.

Abstract: It is common practice to use the epithet “highly concurrent” referring to data structures that are supposed to perform well in concurrent environments. But how do we measure the concurrency of a data structure in the first place? In this paper, we propose a way to do this, which allowed us to formalize the notion of a concurrency-optimal implementation. The concurrency of a program is defined here as the program’s ability to accept concurrent schedules, i.e., interleavings of steps of its sequential implementation. To make the definition sound, we introduce a novel correctness criterion, LS-linearizability, that, in addition to classical linearizability, requires that the interleavings of memory accesses to be locally indistinguishable from sequential executions. An implementation is then concurrency-optimal if it accepts all LS-linearizable schedules. We explore the concurrency properties of search data structures which can be represented in the form of directed acyclic graphs exporting insert, delete and search operations. We prove, for the first time, that pessimistic (e.g., based on conservative locking) and optimistic serializable (e.g., based on serializable transactional memory) implementations of search data-structures are incomparable in terms of concurrency. Thus, neither of these two implementation classes is concurrency-optimal, hence raising the question of the existence of concurrency-optimal programs.

Abstract: Aguilera, Gafni and Lamport introduced the signaling problem in [3]. In this problem, two processes numbered 0 and 1 can call two procedures: update and Fscan. A parameter of the problem is a two-variable function $F(x_0, x_1)$. Each process $p_i$ can assign values to variable $x_i$ by calling update($v$) with some data value $v$, and compute the value: $F(x_0, x_1)$ by executing an Fscan procedure. The problem is interesting when the domain of $F$ is infinite and the range of $F$ is finite. In this case, some "access restrictions" are imposed that limit the size of the registers that the Fscan procedure can access. Aguilera et al. provided a non-blocking solution and asked whether a wait-free solution exists. A positive answer can be found in [5]. The natural generalization of the two-process signaling problem to an arbitrary number of processes turns out to yield an interesting generalization of the fundamental snapshot problem, which we call the $F$-snapshot problem. In this problem $n$ processes can write values to an $n$-segment array (each process to its own segment), and can read and obtain the value of an $n$-variable function $F$ on the array of segments. In case that the range of $F$ is finite, it is required that only bounded registers are accessed when the processes apply the function $F$ to the array, although the data values written to the segments may be taken from an infinite set. We provide here an affirmative answer to the question of Aguilera et al. for an arbitrary number of processes. Our solution employs only single-writer atomic registers, and its time complexity is $O(n \log n)$.

Abstract: Immediate snapshot is the basic communication object on which relies the read/write distributed computing model made up of $n$ crash-prone asynchronous processes, called iterated distributed model. Each iteration step (usually called a round) uses a new immediate snapshot object, which allows the processes to communicate and cooperate. More precisely, the $x$-th immediate snapshot object can be used by a process only when it executes the $x$-th round. An immediate snapshot object can be implemented by an $(n-1)$-resilient algorithm, i.e. an algorithm that tolerates up to $(n-1)$ process crashes (also called wait-free algorithm). Considering a $t$-crash system model (i.e. a model in which up to $t$ processes are allowed to crash), this paper is on the construction of an extension of immediate snapshot objects to $t$-resiliency. In the $t$-crash system model, at each round each process may be ensured to get values from at least $n-t$ processes, and $t$-immediate snapshot has the properties of classical immediate snapshot ($1$-immediate snapshot) but ensures that each process will get values form at least $n-t$ processes. Its main result is the following. While there is a (deterministic) $t$-resilient read/write-based algorithm implementing $t$-immediate snapshot in a $t$-crash system when $t=n-1$, there is no $t$-resilient algorithm in a $t$-crash model when $t\in [1..(n-2)]$. This means that the notion of $t$-resilience is inoperative when one has to implement immediate snapshot for these values of $t$: the model assumption “at most $t<n-1$ processes may crash” does not provide us with additional computational power allowing for the design of genuine $t$-resilient algorithms (genuine meaning that such a $t$-resilient algorithm would work in the $t$-crash model, but not in the $(t+1)$-crash model). To show these results, the paper relies on well-known distributed computing agreement problems such as consensus and $k$-set agreement.

Abstract: Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with the robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result from [Chrobak et al., SOFSEM 2015, LNCS 8939, pp. 164–176] referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In addition, we consider also the wireless communication model, in which a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. In this model, we design an optimal strategy whenever the faster robot is at most 6 times faster than the slower one.

Abstract: Two mobile agents, starting at arbitrary, possibly different times from arbitrary locations in the plane, have to meet. Agents are modeled as discs of diameter 1, and meeting occurs when these discs touch. Agents have different labels which are integers from the set $\{0, \dotsc, L - 1\}$. Each agent knows $L$ and knows its own label, but not the label of the other agent. Agents are equipped with compasses and have synchronized clocks. They make a series of moves. Each move specifies the direction and the duration of moving. This includes a null move which consists in staying inert for some time, or forever. In a non-null move agents travel at the same constant speed, normalized to 1. We assume that agents have sensors enabling them to estimate the distance from the other agent (defined as the distance between centers of discs), but not the direction towards it. We consider two models of estimation. In both models an agent reads its sensor at the moment of its appearance in the plane and then at the end of each move. This reading (together with the previous ones) determines the decision concerning the next move. In both models the reading of the sensor tells the agent if the other agent is already present. Moreover, in the monotone model, each agent can find out, for any two readings in moments $t_1$ and $t_2$, whether the distance from the other agent at time $t_1$ was smaller, equal or larger than at time $t_2$. In the weaker binary model, each agent can find out, at any reading, whether it is at distance less than $\rho$ or at distance at least $\rho$ from the other agent, for some real $\rho > 1$ unknown to them. Such distance estimation mechanism can be implemented, e.g., using chemical sensors. Each agent emits some chemical substance (scent), and the sensor of the other agent detects it, i.e., sniffs. The intensity of the scent decreases with the distance. In the monotone model it is assumed that the sensor is ideally accurate and can measure any change of intensity. In the binary model it is only assumed that the sensor can detect the scent below some distance (without being able to measure intensity) above which the scent is too weak to be detected. We show the impact of the two ways of sensing on the time of meeting, measured from the start of the later agent. For the monotone model we show an algorithm achieving meeting in time $O(D)$, where $D$ is the initial distance between the agents. This complexity is optimal. For the binary model we show that, if agents start at distance smaller than $\rho$ (i.e., when they sense each other initially) then meeting can be guaranteed within time $O(\rho \log L)$, and that this time cannot be improved in general. Finally we observe that, if agents start at distance $\alpha\rho$, for some constant $\alpha > 1$ in the binary model, then sniffing does not help, i.e., the worst-case optimal meeting time is of the same order of magnitude as without any sniffing ability.

Abstract: We consider the problem of efficient evacuation using multiple exits. We formulate this problem as a discrete problem on graphs where mobile agents located in distinct nodes of a given graph must quickly reach one of multiple possible exit nodes, while avoiding congestion and bottlenecks. Each node of the graph has the capacity of holding at most one agent at each time step. Thus, the agents must choose their movements strategy based on locations of other agents in the graph, in order to minimize the total time needed for evacuation. We consider two scenarios: (i) the global communication model where the agents have full knowledge of initial positions of other agents, and (ii) the local communication model where the agents can communicate locally with nearby agents and they must modify their strategy in an online fashion while they move and obtain more information. In the offline case we present a polynomial time solution to compute the optimal strategy for evacuation of all agents. In the online version, we present a constant competitive algorithm when agents can communicate at distance two in the graph. We also show that when the agents are heterogeneous and each agent has access to only a subgraph of the original graph then computing the optimal strategy is NP-hard even with full global knowledge. This result holds even if there are only two types of agents.

Abstract: An oblivious mobile robot is a stateless computational entity located in a spatial universe, capable of moving in that universe. When activated, the robot observes the universe and the location of the other robots, chooses a destination, and moves there. The computation of the destination is made by executing an algorithm, the same for all robots, whose sole input is the current observation. No memory of all these actions is retained after the move. When the spatial universe is a graph, distributed computations by oblivious mobile robots have been intensively studied focusing on the conditions for feasibility of basic problems (e.g., gathering, exploration) in specific classes of graphs under different schedulers. In this paper, we embark on a different, more general, type of investigation. With their movements from vertices to neighboring vertices, the robots make the system transition from one configuration to another. Thus the execution of an algorithm from a given configuration defines in a natural way the computation of a discrete function by the system. Our research interest is to understand which functions are computed by which systems. In this paper we focus on identifying sets of systems that are universal, in the sense that they can collectively compute all finite functions. We are able to identify several such classes of fully synchronous systems. In particular, among other results, we prove the universality of the set of all graphs with at least one robot, of any set of graphs with at least two robots whose quotient graphs contain arbitrarily long paths, and of any set of graphs with at least three robots and arbitrarily large finite girths. We then focus on the minimum size that a network must have for the robots to be able to compute all functions on a given finite set. We are able to approximate the minimum size of such a network up to a factor that tends to 2 as $n$ goes to infinity. The main technique we use in our investigation is the simulation between algorithms, which in turn defines domination between systems. If a system dominates another system, then it can compute at least as many functions. The other ingredient is constituted by path and ring networks, of which we give a thorough analysis. Indeed, in terms of implicit function computations, they are revealed to be fundamental topologies with important properties. Understanding these properties enables us to extend our results to larger classes of graphs, via simulation.

Abstract: We consider the problem of collectively delivering some message from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has a limited energy which constrains the distance it can move. Hence multiple agents need to collaborate to move the message, each agent handing over the message to the next agent to carry it forward. Given the positions of the agents in the graph and their respective budgets, the problem of finding a feasible movement schedule for the agents can be challenging. We consider two variants of the problem: in non-returning delivery, the agents can stop anywhere; whereas in returning delivery, each agent needs to return to its starting location, a variant which has not been studied before. We first provide a polynomial-time algorithm for returning delivery on trees, which is in contrast to the known (weak) NP-hardness of the non-returning version. In addition, we give resource-augmented algorithms for returning delivery in general graphs. Finally, we give tight lower bounds on the required resource augmentation for both variants of the problem. In this sense, our results close the gap left by previous research.

Abstract: A set of mobile agents is deployed in the nodes of an edge-weighted network. Agents originally possess amounts of energy, possibly different for all agents. The agents travel in the network spending energy proportional to the distance traversed. Some nodes of the network may keep information which is acquired by the agents visiting them. The meeting agents may exchange currently possessed information, as well as any amount of energy. We consider communication problems when the information initially held by some network nodes have to be communicated to some other nodes and/or agents. The paper deals with two communication problems: data delivery and convergecast. These problems are posed for a centralized scheduler which has full knowledge of the instance. It is already known that, without energy exchange, both problems are NP-complete even if the network is a line. In this paper we show that, if the agents are allowed to exchange energy, both problems have linear-time solutions on trees. On the other hand for general undirected and directed graphs we show that these problems are NP-complete.

Abstract: In broadcasting, one node of a network has a message that must be learned by all other nodes. We study deterministic algorithms for this fundamental communication task in a very weak model of wireless communication. The only signals sent by nodes are beeps. Moreover, they are delivered to neighbors of the beeping node in an asynchronous way: the time between sending and reception is finite but unpredictable. We first observe that under this scenario, no communication is possible, if beeps are all of the same strength. Hence we study broadcasting in the bivalent beeping model, where every beep can be either soft or loud. At the receiving end, if exactly one soft beep is received by a node in a round, it is heard as soft. Any other combination of beeps received in a round is heard as a loud beep. The cost of a broadcasting algorithm is the total number of beeps sent by all nodes. We consider four levels of knowledge that nodes may have about the network: anonymity (no knowledge whatsoever), ad-hoc (all nodes have distinct labels and every node knows only its own label), neighborhood awareness (every node knows its label and labels of all neighbors), and full knowledge (every node knows the entire labeled map of the network and the identity of the source). We first show that in the anonymous case, broadcasting is impossible even for very simple networks. For each of the other three knowledge levels we provide upper and lower bounds on the minimum cost of a broadcasting algorithm. Our results show separations between all these scenarios. Perhaps surprisingly, the jump in broadcasting cost between the ad-hoc and neighborhood awareness levels is much larger than between the neighborhood awareness and full knowledge levels, although in the two former levels knowledge of nodes is local, and in the latter it is global.

Abstract: The core-periphery network architecture proposed by Avin et al. [ICALP 2014] was shown to support fast computation for many distributed algorithms, while being much sparser than the congested clique. For being efficient, the core-periphery architecture is however bounded to satisfy three axioms, among which is the capability of the core to implement the all-to-all communication pattern in $O(1)$ rounds in the CONGEST model. In this paper, we show that implementing all-to-all communication in k rounds can be done in n-node networks with roughly $n^2/k$ edges, and this bound is tight. Hence, sparsifying the core beyond just saving a fraction of the edges requires to relax the constraint on the time to simulate the congested clique. We show that, for $p \gg \sqrt{\log n/n}$, a random graph in $G_{n,p}$ can, w.h.p., perform the all-to-all communication pattern in $O(\min\{1/p^2, np\})$ rounds. Finally, we show that if the core can emulate the congested clique in $t$ rounds, then there exists a distributed MST construction algorithm performing in $O(t \log n)$ rounds. Hence, for $t=O(1)$, our (deterministic) algorithm improves the best known (randomized) algorithm for constructing MST in core-periphery networks by a factor $\Theta(\log n)$.

Abstract: We consider a variant of the well-studied gossip-based model of communication for disseminating information in a network, usually represented by a graph. Classically, in each time unit, every node $u$ is allowed to contact a single random neighbor $v$. If $u$ knows the data (rumor) to be disseminated, node $v$ learns it (known as push) and if node $v$ knows the rumor, $u$ learns it (known as pull. While in the classic gossip model, each node is only allowed to contact a single neighbor in each time unit, each node can possibly be contacted by many neighboring nodes. If, for example, several nodes pull from the same common neighbor $v$, $v$ manages to inform all these nodes in a single time unit. In the present paper, we consider a restricted model where at each node only one incoming request can be served in one time unit. As long as only a single piece of information needs to be disseminated, this does not make a difference for push requests. It however has a significant effect on pull requests. If several nodes try to pull the information from the same common neighbor, only one of the requests can be served. In the paper, we therefore concentrate on this weaker pull version, which we call restricted pull. We distinguish two versions of the restricted pull protocol depending on whether the request to be served among a set of pull requests at a given node is chosen adversarially or uniformly at random. As a first result, we prove an exponential separation between the two variants. We show that there are instances where if an adversary picks the request to be served, the restricted pull protocol requires a polynomial number of rounds whereas if the winning request is chosen uniformly at random, the restricted pull protocol only requires a polylogarithmic number of rounds to inform the whole network. Further, as the main technical contribution, we show that if the request to be served is chosen randomly, the slowdown of using restricted pull versus using the classic pull protocol can w.h.p. be upper bounded by $O(\Delta / \delta \cdot\log n)$, where $\Delta$ and $\delta$ are the largest and smallest degree of the network.

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 activate the entire social network, whom should she befriend? We study the problem of finding the minimum number of links that Alice should form to people in the network, in order to activate the entire social network. This Minimum 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 Target Set Selection problem. We prove that the Minimum Links problem is NP-complete, in fact it is hard to approximate to within an $\epsilon \ln n$ factor for some constant $\epsilon$, even for graphs with degree 3 and with threshold at most 2. In contrast, we give linear time algorithms to solve the problem for trees, cycles, and cliques, and give precise bounds on the number of links needed.

Abstract: In a single-hop radio network, nodes can communicate with each other by broadcasting to a shared wireless channel. In each time slot, all nodes receive feedback from the channel depending on the number of transmitters. In the Beeping Model, each node learns whether zero or at least one node have transmitted. In such a model, a procedure estimating the size of the network can be used for efficiently solving the problems of leader election or conflict resolution. We introduce a time-efficient uniform algorithm for size estimation of single-hop networks. With probability at least $1-1/f$ our solution returns $(1+\epsilon)$-approximation of the network size $n$ within $O(\log \log n+\log f/\epsilon^2)$ time slots. We prove that the algorithm is asymptotically time-optimal for any constant $\epsilon>0$.

Abstract: We consider the task of computing (combined) function mapping and routing for requests in Software-Defined Networks (SDNs). Function mapping refers to the assignment of nodes in the substrate network to various processing stages that requests must undergo. Routing refers to the assignment of a path in the substrate network that begins in a source node of the request, traverses the nodes that are assigned functions for this request, and ends in a destination of the request. The algorithm either rejects a request or completely serves a request, and its goal is to maximize the sum of the benefits of the served requests. The solution must abide edge and vertex capacities. We follow the framework suggested by Even et al. [EMPS15] for the specification of the processing requirements and routing of requests via processing-and-routing graphs (PR-graphs). In this framework, each request has a demand, a benefit, and PR-graph. Our main result is a randomized approximation algorithm for path computation and function placement with the following guarantee. Let $m$ denote the number of links in the substrate network, $\epsilon$ denote a parameter such that $0< \epsilon <1$, and $\mathrm{opt}$ denote the maximum benefit that can be attained by a fractional solution (one in which requests may be partly served and flow may be split along multiple paths). Let $c_\min$ denote the minimum edge capacity, let $d_\max$ denote the maximum demand, and let $b_\max$ denote the maximum benefit of a request. Let $\Delta_\max$ denote an upper bound on the number of processing stages a request undergoes. If $c_\min/(\Delta_\max\cdot d_\max)=\Omega((\log m)/\epsilon^2)$, then with probability at least $1-\frac{1}{m}-\textit{exp}(-\Omega(\epsilon^2\cdot \mathrm{opt} /(b_\max \cdot d_\max)))$, the algorithm computes a $(1-\epsilon)$-approximate solution.

Abstract: The software-defined networking paradigm introduces interesting opportunities to operate networks in a more flexible yet formally verifiable manner. Despite the logically centralized control, however, a Software-Defined Network (SDN) is still a distributed system, with inherent delays between the switches and the controller. Especially the problem of changing network configurations in a consistent manner, also known as the consistent network update problem, has received much attention over the last years. This paper revisits the problem of how to update an SDN in a transiently consistent, loop-free manner. First, we rigorously prove that computing a maximum (“greedy”) loop-free network update is generally NP-hard; this result has implications for the classic maximum acyclic subgraph problem (the dual feedback arc set problem) as well. Second, we show that for special problem instances, fast and good approximation algorithms exist.