Structural Information and Communication Complexity

The study of graphs and networks often involves studying various parameters of the graph vertices, capturing different aspects of the graph structure, such as the vertex degrees or the distances between the vertices. Given an n-vertex graph G and a parameter of interest f, one may associate with G a vector $$\mathcal{F}(G)=\langle f_1,\ldots ,f_n\rangle $$ giving the value of f for each vertex. This vector can be thought of as the f-profile of the graph. This paper concerns the dual problem, where given an n-entry f-specification vector $$F=\langle f_1,\ldots ,f_n\rangle $$ , we need to decide whether it is possible to find a graph G realizing this specification, namely, whose f-profile $$\mathcal{F}(G)$$ conforms to $$F$$ . The paper introduces the notion of graph realiziations and illustrates a number of example problems related to finding graph realiziations for given specifications.

This paper presents a new distributed self-stabilizing algorithm solving the maximal matching problem under the fair distributed daemon. This is the first maximal matching algorithm in the link-register model under read/write atomicity. This work is composed of two parts. As we cannot establish a move complexity analysis under the fair distributed daemon, we first design an algorithm $$\mathcal A_{1} $$ under the unfair distributed daemon dealing with some relaxed constraints on the communication model. Second, we adapt $$\mathcal A_{1} $$ so that it can handle the fair distributed daemon, leading to the $$\mathcal A_{2} $$ algorithm. We prove that algorithm $$\mathcal A_1$$ stabilizes in $$O(m\Delta )$$ moves and algorithm $$\mathcal A_2$$ in $$O(m\Delta )$$ rounds, with $$\Delta $$ the maximum degree and m the number of edges.

By presenting a message-efficient snap-stabilizing quiescence detection algorithm, we also facilitate a transformer that converts non self-stabilizing algorithms into self-stabilizing ones. We propose a message-efficient snap-stabilizing ongoing quiescence detection algorithm. (Notice that by definition it is also self-stabilizing and can detect termination.) This algorithm works for diffusing computations. We are not aware of any other self-stabilizing or snap-stabilizing ongoing quiescence or termination detection algorithm.

The token distribution problem was originally defined by Peleg and Upfal in their seminal paper [4]. Consider a network of n processes and n tokens. Initially, the tokens are arbitrarily distributed among processes but with up to a maximum of l tokens in any process. The problem is to uniformly distribute the tokens such that every process ends up with exactly one token.

Network devices need packet counters for a variety of applications. For a large number of concurrent flows, on-chip memories can be too small to support a separate counter per flow. While a single network element might struggle to implement flow accounting on its own, in this work we study alternatives leveraging underutilized resources elsewhere in the network and implement flow accounting on multiple network devices. This paper takes the first step towards understanding the design principles for robust network-wide accounting with lossy unidirectional channels without feedback.

We consider the problem of replacing several dependent routes in a Software-Defined Network (SDN). Delaet et al. focused on the replacement of a single pair of routes and proposed a verification idea for launching a new sub-route. Dinitz et al. suggested a dependence graph model for solving the problem with several routes pairs, and described the sub-route launching verification in the form of a high level network protocol. In both works, each sub-route is seamlessly updated using the Make&Activate-Before-Break (MABB) approach, eliminating flow stopping and delays in transmission. According to the MABB approach, a new sub-route is first fully prepared by possibly adding additional traffic in the sake of readiness signaling and seamless route change; after that the new sub-route is activated by redirecting the flow through it and the corresponding part of the current route is dismantled. In this brief announcement, we describe our extension for the case of replacing several dependent routes to also address network policies preservation. Additionally, we describe the existing verification gap of OpenFlow (the standard communication protocol tool for SDN) in signaling the readiness of route changes. We describe a verification protocol of route change readiness by means of OpenFlow, called Route Readiness Verifier (RRV). We show that RRV closes the verification gap in OpenFlow for route updates.

Population protocols [2] are networks that consist of very weak computational entities (also called nodes or agents), regarding their individual capabilities and it has been shown that are able to perform complex computational tasks when they work collectively. Leader Election is the process of designating a single agent as the coordinator of some task distributed among several nodes. The nodes communicate among themselves in order to decide which of them will get into the leader state, starting from the same initial state q. An algorithm A solves the leader election problem if eventually the states of agents are divided into leader and follower, a unique leader remains elected and a follower can never become a leader. A randomized algorithm R solves the leader election problem if eventually only one leader remains in the system w.h.p.. Counting is the problem where nodes must determine the size n of the population. We call Approximate Counting the problem in which nodes must determine an estimation $$\hat{n}$$ of the population size, where $$\frac{\hat{n}}{a}< n < \hat{n}$$ . We call a the estimation parameter. Consider the setting in which an agent is in an initial state a, the rest $$n-1$$ agents are in state b and the only existing transition is $$(a,b) \rightarrow (a,a)$$ . This is the one-way epidemic process and it can be shown that the expected time to convergence under the uniform random scheduler is $$\varTheta (n\log {n})$$ (e.g., [3]), thus parallel time $$\varTheta (\log {n})$$ .

In a number of our works we present and use the tree-like network models, so called one-max constant-probability models characterized by the following newly studied principles: (i) each new vertex may be connected to at most one existing vertex; (ii) any connection event is realized with the same probability p due to external factors; (iii) the probability $$\varPi $$ that a new vertex will be connected to vertex i depends not directly on its degree $$d_{i}$$ but on the place of $$d_{i}$$ in the sorted list of vertex degrees. In this announcement we describe features and applications of these models and discuss possible ways of their generalization.

We examine the relation between the size of the id space and the number of rational agents in a network under which equilibrium in distributed algorithms is possible. When the number of agents in the network is not a-priori known, but the id space is limited, a single agent may duplicate to gain an advantage but each duplication involves a risk of being caught. Given an id space of size L, we provide a method of calculating the threshold, the minimal value t such that agents know that $$n \ge t$$ , such that the algorithm is in equilibrium. We apply the method to Leader Election and Knowledge Sharing, and provide a constant-time approximation $$t \approx \frac{L}{5}$$ of the threshold for Leader Election.

Fault-tolerant distributed consensus is a fundamental problem in secure distributed computing. In this work, we consider the problem of distributed consensus in directed graphs tolerating crash failures. Tseng and Vaidya (PODC’15) presented necessary and sufficient condition for the existence of consensus protocols in directed graphs. We improve the round and communication complexity of their protocol. Moreover, we prove that our protocol requires the optimal number of communication rounds, required by any protocol belonging to a restricted class of crash-tolerant consensus protocols in directed graphs.

It is known for some time that a random graph G(n, p) contains w.h.p. a Hamiltonian cycle if p is larger than the critical value $$p_{crit}= (\log n + \log \log n + \omega _n)/n$$ . The determination of a concrete Hamiltonian cycle is even for values much larger than $$p_{crit}$$ a nontrivial task. In this paper we consider random graphs G(n, p) with p in $$\tilde{\varOmega }(1/\sqrt{n})$$ , where $$\tilde{\varOmega }$$ hides poly-logarithmic factors in n. For this range of p we present a distributed algorithm $$\mathcal{A}_\mathsf {HC}$$ that finds w.h.p. a Hamiltonian cycle in $$O(\log n)$$ rounds. The algorithm works in the synchronous model and uses messages of size $$O(\log n)$$ and $$O(\log n)$$ memory per node.

We bound the performance guarantees that follow from Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, a randomized approach of Boppana forms a simple 1-round distributed algorithm, as well as a streaming and preemptive online algorithm. We show it gives a tight $$(\varDelta +1)/2$$ -approximation in unweighted graphs of maximum degree $$\varDelta $$ , which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a $$(\varDelta +1)$$ -approximation, but a simple modification results in an asymptotic expected $$0.529 (\varDelta +1)$$ -approximation. This compares with a recent, more complex $$\varDelta $$ -approximation [6], which holds deterministically.

Inspired by the successful chase for the weakest failure detector in asynchronous message passing systems with crash failures and surprising relations to synchronous directed dynamic networks with message adversaries established by Raynal and Stainer [PODC’13], we introduce the concept of message adversary simulations and use it for defining a notion for strongest message adversary for solving distributed computing problems like consensus and k-set agreement. We prove that every message adversary that admits all graph sequences consisting of perpetual star graphs and is strong enough for solving multi-valued consensus is a strongest one. We elaborate on seemingly paradoxical consequences of our results, which also shed some light on the fundamental difference between crash-prone asynchronous systems with failure detectors and synchronous dynamic networks with message adversaries.

In the classic Symmetric Rendezvous problem on a Line (SRL), two robots at known distance 2 but unknown direction execute the same randomized algorithm trying to minimize the expected rendezvous time. A long standing conjecture is that the best possible rendezvous time is 4.25 with known upper and lower bounds being very close to that value. We introduce and study a geometric variation of SRL that we call Symmetric Rendezvous in a Disk (SRD) where two robots at distance 2 have a common reference point at distance $$\rho $$ . We show that even when $$\rho $$ is not too small, the two robots can meet in expected time that is less than 4.25. Part of our contribution is that we demonstrate how to adjust known, even simple and provably non-optimal, algorithms for SRL, effectively improving their performance in the presence of a reference point. Special to our algorithms for SRD is that, unlike in SRL, for every fixed $$\rho $$ the worst case distance traveled, i.e. energy that is used, in our algorithms is finite. In particular, we show that the energy of our algorithms is $$O\left( \rho ^2\right) $$ , while we also explore time-energy tradeoffs, concluding that one may be efficient both with respect to time and energy, with only a minor compromise on the optimal termination time.

In this paper we study the reconstruction problem in the congested clique model. In the reconstruction problem nodes are asked to recover all the edges of the input graph G. Formally, given a class of graphs $$\mathcal G$$ , the problem is defined as follows: if $$G \notin {\mathcal G}$$ , then every node must reject; on the other hand, if $$G \in {\mathcal G}$$ , then every node must end up knowing all the edges of G. It is not difficult to see that the cost Rb of any algorithm that solves this problem (even with public coins) is at least $$\varOmega (\log |{\mathcal {G}}_n|/n)$$ , where $${\mathcal {G}}_n$$ is the subclass of all n-node labeled graphs in $$\mathcal G$$ , R is the number of rounds and b is the bandwidth.We prove here that the lower bound above is in fact tight and that it is possible to achieve it with only $$R=2$$ rounds and private coins. More precisely, we exhibit (i) a one-round algorithm that achieves this bound for hereditary graph classes; and (ii) a two-round algorithm that achieves this bound for arbitrary graph classes. Later, we show that the bound $$\varOmega (\log |{\mathcal {G}}_n|/n)$$ cannot be achieved in one round for arbitrary graph classes, and we give tight algorithms for that case.From (i) we recover all known results concerning the reconstruction of graph classes in one round and bandwidth $$\mathcal {O}(\log n)$$ : forests, planar graphs, cographs, etc. But we also get new one-round algorithms for other hereditary graph classes such as unit-disc graphs, interval graphs, etc. From (ii), we can conclude that any problem restricted to a class of graphs of size $$2^{\mathcal {O}(n\log n)}$$ can be solved in the congested clique model in two rounds, with bandwidth $$\mathcal {O}(\log n)$$ . Moreover, our general two-round algorithm is valid for any set of labeled graphs, not only for graph classes.

In this paper, we consider the uniform deployment problem of mobile agents in asynchronous unidirectional ring networks. This problem requires agents to spread uniformly in the network. In this paper, we focus on the memory space per agent required to solve the problem. We consider two problem settings. The first setting assumes that agents have no multiplicity detection, that is, agents cannot detect whether another agent is staying at the same node or not. In this case, we show that each agent requires $$\varOmega (\log n)$$ memory space to solve the problem, where n is the number of nodes. In addition, we propose an algorithm to solve the problem with $$O(k + \log n)$$ memory space per agent, where k is the number of agents. The second setting assumes that each agent is equipped with the weak multiplicity detection, that is, agents can detect another agent staying at the same node, but cannot learn the exact number. Then, we show that the memory space per agent can be reduced to $$O(\log k + \log \log n)$$ . To the best of our knowledge, this is the first research considering the effect of the multiplicity detection on memory space required to solve problems.

Graph exploration is one of the fundamental tasks performed by a mobile agent in a graph. An n-node graph has unlabeled nodes, and all ports at any node of degree d are arbitrarily numbered $$0,\dots , d-1$$ . A mobile agent, initially situated at some starting node v, has to visit all nodes of the graph and stop. In the absence of any initial knowledge of the graph the task of deterministic exploration is often impossible. On the other hand, for some families of graphs it is possible to design deterministic exploration algorithms working for any graph of the family. We call such families of graphs explorable. Examples of explorable families are all finite families of graphs, as well as the family of all trees.In this paper we study the problem of which families of graphs are explorable. We characterize all such families, and then ask the question whether there exists a universal deterministic algorithm that, given an explorable family of graphs, explores any graph of this family, without knowing which graph of the family is being explored. The answer to this question turns out to depend on how the explorable family is given to the hypothetical universal algorithm. If the algorithm can get the answer to any yes/no question about the family, then such a universal algorithm can be constructed. If, on the other hand, the algorithm can be only given an algorithmic description of the input explorable family, then such a universal deterministic algorithm does not exist.

One of the central questions in distributed computability is characterizing the tasks that are solvable in a given system model. In the anonymous case, where processes have no identifiers and communicate through multi-writer/multi-reader registers, there is a recent topological characterization (Yanagisawa 2017) of the colorless tasks that are solvable when any number of asynchronous processes may crash. In this paper, we consider the case where at most t asynchronous processes may crash, where $$1\le t<n$$ . We prove that a colorless task is t-resilient solvable anonymously if and only if it is t-resilient solvable non-anonymously. We obtain our results through various reductions and simulations that explore how to extend techniques for non-anonymous computation to anonymous one.

An $$(\alpha ,\beta )$$ -ruling set of a graph $$G=(V,E)$$ is a set $$R\subseteq V$$ such that for any node $$v\in V$$ there is a node $$u\in R$$ in distance at most $$\beta $$ from v and such that any two nodes in R are at distance at least $$\alpha $$ from each other. The concept of ruling sets can naturally be extended to edges, i.e., a subset $$F\subseteq E$$ is an $$(\alpha ,\beta )$$ -ruling edge set of a graph $$G=(V,E)$$ if the corresponding nodes form an $$(\alpha ,\beta )$$ -ruling set in the line graph of G. This paper presents a simple deterministic, distributed algorithm, in the $$\mathsf {CONGEST}$$ model, for computing (2, 2)-ruling edge sets in $$O(\log ^{*}n)$$ rounds. Furthermore, we extend the algorithm to compute ruling sets of graphs with bounded diversity. Roughly speaking, the diversity of a graph is the maximum number of maximal cliques a vertex belongs to. We devise $$(2,O(\mathcal {D}))$$ -ruling sets on graphs with diversity $$\mathcal {D}$$ in $$O(\mathcal {D}+\log ^{*}n)$$ rounds. This also implies a fast, deterministic $$(2,O( \ell ))$$ -ruling edge set algorithm for hypergraphs with rank at most $$ \ell $$ .Furthermore, we provide a ruling set algorithm for general graphs that for any $$B\ge 2$$ computes an $$\big (\alpha , \alpha \lceil \log _B n\rceil \big )$$ -ruling set in $$O(\alpha \cdot B \cdot \log _B n)$$ rounds in the $$\mathsf {CONGEST}$$ model. The algorithm can be modified to compute a $$\big (2, \beta \big )$$ -ruling set in $$O(\beta \varDelta ^{2/\beta } + \log ^{*}n)$$ rounds in the $$\mathsf {CONGEST}$$ model, which matches the currently best known such algorithm in the more general $$\mathsf {LOCAL}$$ model.

Mobile agents are deployed at selected nodes of an edge-weighted tree network. Each agent originally possesses an amount of energy, possibly different for all agents. Initially, in a given source node of the network is placed a piece of information (data packet) that must be broadcast to all other nodes. Such transfer of the packet needs to be achieved with aid of collaborating mobile agents, which may transport copies of the packet to all nodes.Agents travel in the network spending energy proportionally to the distance traversed. They can stop only at network nodes. If two agents are present at a node at the same time, they can exchange any amount of currently possessed energy. Our goal is to verify if there exists a sequence of agents’ movements (a schedule) and energy exchanges between meeting agents, which results in the packet reaching all nodes of the tree network.Our algorithm produces an optimal centralized scheduler as we assume that the central authority knows everything about the network and controls the movement of the agents, which do not need to possess any knowledge. In this sense it is a semi-distributed algorithm.The important part of our algorithm uses dynamic programming in order to compute an optimal agents migration flow of every edge of the network, i.e. the number of agents traversing every edge in each direction. The approach is far from being straightforward, as its correctness is based on multiple complex interactions between the subtrees obtained by removal of any given edge.It is known that, if energy exchange is not allowed, the broadcasting problem for trees (even for lines) is NP-complete.

We present a deterministic distributed 2-approximation algorithm for the Minimum Weight Vertex Cover problem in the CONGEST model whose round complexity is $$O(\log n\log \varDelta / \log ^2\log \varDelta )$$ . This improves over the currently best known deterministic 2-approximation implied by [KVY94]. Our solution generalizes the $$(2+\epsilon )$$ -approximation algorithm of [BCS17], improving the dependency on $$\epsilon ^{-1}$$ from linear to logarithmic. In addition, for every $$\epsilon =(\log \varDelta )^{-c}$$ , where $$c\ge 1$$ is a constant, our algorithm computes a $$\left( 2+\epsilon \right) $$ -approximation in $$O(\log {\varDelta }/\log \log {\varDelta })$$ rounds (which is asymptotically optimal).

In the Online Service with Delay (OSD) problem, introduced recently by Azar et al. (STOC 2017), there are an n-point metric space and a server occupying some point. Points request service over time and these requests need to be eventually served by moving the server to these points. To exploit spatial locality of requests, a service may be delayed and requests may be served in batches. However, there are certain penalties associated with the delays, e.g., such penalty may be proportional to the waiting time of a given request. The goal is to minimize the sum of the total distance traveled by the server and all delay penalties. The OSD problem is closely related to widely studied optimization problems, such as the reordering buffer management and the multi-level aggregation. Azar et al. (STOC 2017) gave a randomized online $$O(\log ^4 n)$$ -competitive algorithm for general metric spaces. In this paper, we present a deterministic $$O(\log n)$$ -competitive algorithm for the case when the metric space is a line consisting of n equidistant points.

We study the mixed approach to fault tolerance in the general context of server assignment in networks. The approach is based on mixing two different existing strategies, namely, reinforcement and backup. The former strategy protects clients by reinforcing the servers assigned to them and making them fault-resistant (at a possibly high cost), while the latter protects clients by assigning to them alternate low price backup servers that can replace their primary servers in case those fail. Applying the mixed approach to fault tolerance gives rise to new fault-tolerant variations of known server assignment problems. We introduce several NP-hard problems of this type, including the mixed fault-tolerant dominating set problem, the mixed fault-tolerant centers problem, and the mixed fault-tolerant facility location problem, and present polynomial time approximation algorithms for them, demonstrating the viability of the mixed strategy for server assignment problems.

We study the multi-party communication model, where players correspond to the nodes of a graph and each player knows its neighbors in the input graph. The players can send messages on a whiteboard which are immediately available to each player. Eventually, the referee which knows only messages on the whiteboard is supposed to give a solution to the considered (graph) problem. We distinguish between oblivious and adaptive variant of the model. The former model is related to simultaneous multi-party communication complexity, while the latter is closely related to so-called broadcast congested clique.Communication complexity is the maximum over all nodes of the sizes of messages put on the whiteboard by a node. Our goal is to study the impact of adaptivity on communication complexity of graph problems. We show that there exists an infinite hierarchy of problems with respect to the number of rounds for constant size messages. Moreover, motivated by unsuccessful attempts to establish non-adaptive communication complexity of graph connectivity in recent years, we study the connectivity problem in the severely restricted class of two-regular graphs We determine an asymptotically tight bound on communication complexity in the oblivious model and provide $$\omega (1)$$ lower bound on the number of rounds in the adaptive model for some message size $$b(n)=\omega (1)$$ .

A widely studied model of influence diffusion in social networks represents the network as a graph $$G=(V,E)$$ with an influence threshold t(v) for each node. Initially the members of an initial set $$S\subseteq V$$ are influenced. During each subsequent round, the set of influenced nodes is augmented by including every node v that has at least t(v) previously influenced neighbours. The general problem is to find a small initial set that influences the whole network. In this paper we extend this model by using incentives to reduce the thresholds of some nodes. The goal is to minimize the total of the incentives required to ensure that the process completes within a given number of rounds. The problem is hard to approximate in general networks. We present polynomial-time algorithms for paths, trees, and complete networks.

The context of this paper is the two-choice paradigm which is deeply used in balanced online resource allocation, priority scheduling, load balancing and more recently in population protocols. The model governing the evolution of these systems consists in throwing balls one by one and independently of each others into n bins, which represent the number of agents in the system. At each discrete instant, a ball is placed in the least filled bin among two bins randomly chosen among the n ones. A natural question is the evaluation of the difference between the number of balls in the most loaded bin and the one in the least loaded. At time t, this difference is denoted by $$\text {Gap}(t)$$ . A lot of work has been devoted to the derivation of asymptotic approximations of this gap for large values of n. In this paper we go a step further by showing that for all $$t \ge 0$$ , $$n \ge 2$$ and $$\sigma > 0$$ , the variable $$\text {Gap}(t)$$ is less than $$a(1+\sigma )\ln (n) + b$$ with probability greater than $$1-1/n^\sigma $$ , where the constants a and b, which are independent of t, $$\sigma $$ and n, are optimized and given explicitly, which to the best of our knowledge has never been done before.

This paper contributes to exploring the connection between epistemic knowledge and communication complexity in distributed systems. We focus on Action Models, a well-known variant of dynamic epistemic logic, which allows to cleanly separate the state of knowledge of the processes and its update due to communication actions: Exactly like the set of possible global states, the possible actions are described by means of a Kripke model that specifies which communication actions are indistinguishable for which process. We first show that the number of connected components in the action model results in a lower bound for communication complexity. We then apply this result, in the restricted setting of a two processor system, for determining communication complexity lower bounds for solving a distributed computing problem $$\mathcal {P}$$ : We first determine some properties of the action model corresponding to any given protocol that solves $$\mathcal {P}$$ , and then use our action model communication complexity lower bounds. Finally, we demonstrate our approach by applying it to synchronous distributed function computation and to a simple instance of consensus in directed dynamic networks.

In this paper we present two graph algorithms in the Broadcast Congested Clique model. In this model, there are n players, which communicate in synchronous rounds. Each player represents a single node of the input graph; initially each player knows the set of edges incident to his node. In each round of communication each node can broadcast a single b–bit message to all other nodes; usually $$b \in {\mathcal {O}}(\log n)$$ . The goal is to compute some function of the input graph.The first result we present is the first sub-logarithmic deterministic algorithm finding a maximal spanning forest of an n node graph in the Broadcast Congested Clique, which requires only $${\mathcal {O}}(\log n / \log \log n)$$ rounds. The second result is a randomized $$1 + \epsilon $$ approximation algorithm finding the minimum cut of an n node graph, which requires only $${\mathcal {O}}(\log n)$$ maximal spanning forest computations. In the Broadcast Congested Clique this approach, combined with the new maximal spanning forest algorithm, yields an $${\mathcal {O}}(\log ^2 n / \log \log n)$$ round algorithm. Additionally, it may be applied to different models, i.e. in the multi-pass semi-streaming model it allows to reduce required memory by $$\varTheta (\log n)$$ factor, with only $${\mathcal {O}}(\log ^* n)$$ passes over the data stream.

In this paper, we present the notion of biased hybrid logical clocks ( $$BHLC$$ ). These clocks are intended to improve the ability of a distributed system to perform predicate detection with just O(1) sized clocks. In traditional logical clocks (or hybrid logical clocks, their extension), the only way to guarantee that two events are concurrent is by checking if their clock values are equal. By contrast, biased clocks provide a window where this guarantee is provided. We validate our intuition that these biased clocks substantially improve the ability to successfully detect a given predicate with just O(1) sized clock. In particular, for many scenarios, we show that biased clocks improve the ability to detect predicates by 100–200 times when compared to standard hybrid logical clocks.

A set of mobile robots (represented as points) is distributed in the Cartesian plane. The collection contains an unknown subset of byzantine robots which are indistinguishable from the reliable ones. The reliable robots need to gather, i.e., arrive to a configuration in which at the same time, all of them occupy the same point on the plane. The robots are equipped with GPS devices and at the beginning of the gathering process they communicate the Cartesian coordinates of their respective positions to the central authority. On the basis of this information, without the knowledge of which robots are faulty, the central authority designs a trajectory for every robot. The central authority aims to provide the trajectories which result in the shortest possible gathering time of the healthy robots. The efficiency of a gathering strategy is measured by its competitive ratio, i.e., the maximal ratio between the time required for gathering achieved by the given trajectories and the optimal time required for gathering in the offline case, i.e., when the faulty robots are known to the central authority in advance. The role of the byzantine robots, controlled by the adversary, is to act so that the gathering is delayed and the resulting competitive ratio is maximized.The objective of our paper is to propose efficient algorithms when the central authority is aware of an upper bound on the number of byzantine robots. We give optimal algorithms for collections of robots known to contain at most one faulty robot. When the proportion of byzantine robots is known to be less than one half or one third, we provide algorithms with small constant competitive ratios. We also propose algorithms with bounded competitive ratio in the case where the proportion of faulty robots is arbitrary.

Efficient representation of data aggregations is a fundamental problem in modern big data applications, where network topologies and deployed routing and transport mechanisms play a fundamental role to optimize desired objectives: cost, latency, and others. We study the design principles of routing and transport infrastructure and identify extra information that can be used to improve implementations of compute-aggregate tasks. We build a taxonomy of compute-aggregate services unifying aggregation design principles, propose algorithms for each class and analyze them.

We introduce and study a new search-type problem with ( $$n+1$$ )-robots on a disk. The searchers (robots) all start from the center of the disk, have unit speed, and can communicate wirelessly. The goal is for a distinguished robot (the queen) to reach and evacuate from an exit that is hidden on the perimeter of the disk in as little time as possible. The remaining n robots (servants) are there to facilitate the queen’s objective and are not required to reach the hidden exit. We provide upper and lower bounds for the time required to evacuate the queen. Namely, we propose an algorithm specifying the trajectories of the robots which guarantees evacuation of the queen in time always better than $$2 + 4(\sqrt{2}-1) \frac{\pi }{n}$$ for $$n \ge 4$$ servants. We also demonstrate that for $$n \ge 4$$ servants the queen cannot be evacuated in time less than $$2+\frac{\pi }{n}+\frac{2}{n^2}$$ .