Search

We give the first non-trivial decremental dynamic embedding of a weighted, undirected graph $G$ into $\ell_p$ space. Given a weighted graph $G$ undergoing a sequence of edge weight increases, the goal of this problem is to maintain a (randomized) mapping $\phi: (G,d) \to (X,\ell_p)$ from the set of vertices of the graph to the $\ell_p$ space such that for every pair of vertices $u$ and $v$, the expected distance between $\phi(u)$ and $\phi(v)$ in the $\ell_p$ metric is within a small multiplicative factor, referred to as the \emph{distortion}, of their distance in $G$. Our main result is a dynamic algorithm with expected distortion $O(\log^3 n)$ and total update time $O\left((m^{1+o(1)} \log^2 W + Q \log n)\log(nW) \right)$, where $W$ is the maximum weight of the edges, $Q$ is the total number of updates and $n, m$ denote the number of vertices and edges in $G$ respectively. This is the first result of its kind, extending the seminal result of Bourgain to the growing field of dynamic algorithms. Moreover, we demonstrate that in the fully dynamic regime, where we tolerate edge insertions as well as deletions, no algorithm can explicitly maintain an embedding into $\ell_p$ space that has a low distortion with high probability., Comment: Accepted to ICML 2024 (15 pages, 3 figures)

We study the problem of reaching agreement in a synchronous distributed system by $n$ autonomous parties, when the communication links from/to faulty parties can omit messages. The faulty parties are selected and controlled by an adaptive, full-information, computationally unbounded adversary. We design a randomized algorithm that works in $O(\sqrt{n}\log^2 n)$ rounds and sends $O(n^2\log^3 n)$ communication bits, where the number of faulty parties is $\Theta(n)$. Our result is simultaneously tight for both these measures within polylogarithmic factors: due to the $\Omega(n^2)$ lower bound on communication by Abraham et al. (PODC'19) and $\Omega(\sqrt{n/\log n})$ lower bound on the number of rounds by Bar-Joseph and Ben-Or (PODC'98). We also quantify how much randomness is necessary and sufficient to reduce time complexity to a certain value, while keeping the communication complexity (nearly) optimal. We prove that no MC algorithm can work in less than $\Omega(\frac{n^2}{\max\{R,n\}\log n})$ rounds if it uses less than $O(R)$ calls to a random source, assuming a constant fraction of faulty parties. This can be contrasted with a long line of work on consensus against an {\em adversary limited to polynomial computation time}, thus unable to break cryptographic primitives, culminating in a work by Ghinea et al. (EUROCRYPT'22), where an optimal $O(r)$-round solution with probability $1-(cr)^{-r}$ is given. Our lower bound strictly separates these two regimes, by excluding such results if the adversary is computationally unbounded. On the upper bound side, we show that for $R\in\tilde{O}(n^{3/2})$ there exists an algorithm solving consensus in $\tilde{O}(\frac{n^2}{R})$ rounds with high probability, where tilde notation hides a polylogarithmic factor. The communication complexity of the algorithm does not depend on the amount of randomness $R$ and stays optimal within polylogarithmic factor.

Sharding is used to improve the scalability and performance of blockchain systems. We investigate the stability of blockchain sharding, where transactions are continuously generated by an adversarial model. The system consists of $n$ processing nodes that are divided into $s$ shards. Following the paradigm of classical adversarial queuing theory, transactions are continuously received at injection rate $\rho \leq 1$ and burstiness $b > 0$. We give an absolute upper bound $\max\{ \frac{2}{k+1}, \frac{2}{ \left\lfloor\sqrt{2s}\right\rfloor}\}$ on the maximum injection rate for which any scheduler could guarantee bounded queues and latency of transactions, where $k$ is the number of shards that each transaction accesses. We next give a basic distributed scheduling algorithm for uniform systems where shards are equally close to each other. To guarantee stability, the injection rate is limited to $\rho \leq \max\{ \frac{1}{18k}, \frac{1}{\lceil 18 \sqrt{s} \rceil} \}$. We then provide a fully distributed scheduling algorithm for non-uniform systems where shards are arbitrarily far from each other. By using a hierarchical clustering of the shards, stability is guaranteed with injection rate $\rho \leq \frac{1}{c_1d \log^2 s} \cdot \max\{ \frac{1}{k}, \frac{1}{\sqrt{s}} \}$, where $d$ is the worst distance of any transaction to the shards it will access, and $c_1$ is some positive constant. We also conduct simulations to evaluate the algorithms and measure the average queue sizes and latency throughout the system. To our knowledge, this is the first adversarial stability analysis of sharded blockchain systems., Comment: 11 pages, 3 figures

We develop deterministic algorithms for the problems of consensus, gossiping and checkpointing with nodes prone to failing. Distributed systems are modeled as synchronous complete networks. Failures are represented either as crashes or authenticated Byzantine faults. The algorithmic goal is to have both linear running time and linear amount of communication for as large an upper bound $t$ on the number of faults as possible, with respect to the number of nodes~$n$. For crash failures, these bounds of optimality are $t=\mathcal{O}(\frac{n}{\log n})$ for consensus and $t=\mathcal{O}(\frac{n}{\log^2 n})$ for gossiping and checkpointing, while the running time for each algorithm is $\Theta(t+\log n)$. For the authenticated Byzantine model of failures, we show how to accomplish both linear running time and communication for $t=\mathcal{O}(\sqrt{n})$. We show how to implement the algorithms in the single-port model, in which a node may choose only one other node to send/receive a message to/from in a round, such as to preserve the range of running time and communication optimality. We prove lower bounds to show the optimality of some performance bounds.

Fault-tolerant consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or (PODC'98) were the first who proved an absolute lower bound $\Omega(\sqrt{n/\log n})$ on expected time complexity of consensus in any classic (i.e., randomized or deterministic) message-passing network with $n$ processes succeeding with probability $1$ against such a strong adaptive adversary crashing processes. Seminal work of Ben-Or and Hassidim (STOC'05) broke the $\Omega(\sqrt{n/\log n})$ barrier for consensus in classic (deterministic and randomized) networks by employing quantum computing. They showed an (expected) constant-time quantum algorithm for a linear number of crashes $t

A number of stations, independently activated over time, is able to communicate by transmitting and listening to a shared channel in discrete time slots, and a message is successfully delivered to all stations if and only if its source station is the only transmitter at a time. Despite a vast amount of work in the last decades, many fundamental questions remain open in the realistic situation where stations do not start synchronously but are awaken in arbitrary times. In this work we present a broad picture of results for the fundamental problem of Contention resolution, in which each of the contending stations needs to broadcast successfully its message. We show that adaptive algorithms or algorithms with the knowledge of the contention size $k$ achieve a linear $O(k)$ message latency even if the channel feedback is restricted to simple acknowledgements in case of successful transmissions and in the absence of synchronization. This asymptotically optimal performance cannot be extended to other settings: we prove that there is no non-adaptive algorithm without the knowledge of contention size $k$ admitting latency $o(k\log k/(\log\log k)^2)$. This means, in particular, that coding (even random) with acknowledgements is not very efficient on a shared channel without synchronization or an estimate of the contention size. We also present a non-adaptive algorithm with no knowledge of contention size that almost matches the lower bound on latency. Finally, despite the absence of a collision detection mechanism, we show that our algorithms are also efficient in terms of energy, understood as the total number of transmissions performed by the stations during the execution.

In a multiple access channel, autonomous stations are able to transmit and listen to a shared device. A fundamental problem, called \textit{contention resolution}, is to allow any station to successfully deliver its message by resolving the conflicts that arise when several stations transmit simultaneously. Despite a long history on such a problem, most of the results deal with the static setting when all stations start simultaneously, while many fundamental questions remain open in the realistic scenario when stations can join the channel at arbitrary times. In this paper, we explore the impact that three major channel features (asynchrony among stations, knowledge of the number of contenders and possibility of switching off stations after a successful transmission) can have on the time complexity of non-adaptive deterministic algorithms. We establish upper and lower bounds allowing to understand which parameters permit time-efficient contention resolution and which do not.

We study computer systems with transactions executed on a set of shared objects. Transactions arrive continually subjects to constrains that are framed as an adversarial model and impose limits on the average rate of transaction generation and the number of objects that transactions use. We show that no deterministic distributed scheduler in the queue-free model of transaction autonomy can provide stability for any positive rate of transaction generation. Let a system consist of $m$ shared objects and an adversary be constrained such that each transaction may access at most $k$ shared objects. We prove that no scheduler can be stable if a generation rate is greater than $\max\bigl\{\frac{2}{k+1},\frac{2}{\lfloor \sqrt{2m} \rfloor}\bigr\}$. We develop a centralized scheduler that is stable if a transaction generation rate is at most $\max\bigl\{\frac{1}{4k}, \frac{1}{4\lceil\sqrt{m}\rceil} \bigr\}$. We design a distributed scheduler in the queue-based model of transaction autonomy, in which a transaction is assigned to an individual processor, that guarantees stability if the rate of transaction generation is less than $\max\bigl\{ \frac{1}{6k},\frac{1}{6\lceil\sqrt{m}\rceil}\bigr\}$. For each of the schedulers we give upper bounds on the queue size and transaction latency in the range of rates of transaction generation for which the scheduler is stable.

Suppose we are given integer $k \leq n$ and $n$ boxes labeled $1,\ldots, n$ by an adversary, each containing a number chosen from an unknown distribution. We have to choose an order to sequentially open these boxes, and each time we open the next box in this order, we learn its number. If we reject a number in a box, the box cannot be recalled. Our goal is to accept the $k$ largest of these numbers, without necessarily opening all boxes. This is the free order multiple-choice secretary problem. Free order variants were studied extensively for the secretary and prophet problems. Kesselheim, Kleinberg, and Niazadeh KKN (STOC'15) initiated a study of randomness-efficient algorithms (with the cheapest order in terms of used random bits) for the free order secretary problems. We present an algorithm for free order multiple-choice secretary, which is simultaneously optimal for the competitive ratio and used amount of randomness. I.e., we construct a distribution on orders with optimal entropy $\Theta(\log\log n)$ such that a deterministic multiple-threshold algorithm is $1-O(\sqrt{\log k/k})$-competitive. This improves in three ways the previous best construction by KKN, whose competitive ratio is $1 - O(1/k^{1/3}) - o(1)$. Our competitive ratio is (near)optimal for the multiple-choice secretary problem; it works for exponentially larger parameter $k$; and our algorithm is a simple deterministic multiple-threshold algorithm, while that in KKN is randomized. We also prove a corresponding lower bound on the entropy of optimal solutions for the multiple-choice secretary problem, matching entropy of our algorithm, where no such previous lower bound was known. We obtain our algorithmic results with a host of new techniques, and with these techniques we also improve significantly the previous results of KKN about constructing entropy-optimal distributions for the classic free order secretary., Comment: arXiv admin note: substantial text overlap with arXiv:2111.13203

When facing a very large stream of data, it is often desirable to extract most important statistics online in a short time and using small memory. For example, one may want to quickly find the most influential users generating posts online or check if the stream contains many identical elements. In this paper, we study streams containing insertions and deletions of elements from a possibly large set $N$ of size $|N| = n$, that are being processed by online deterministic algorithms. At any point in the stream the algorithm may be queried to output elements of certain frequency in the already processed stream. More precisely, the most frequent elements in the stream so far. The output is considered correct if the returned elements it contains all elements with frequency greater than a given parameter $\varphi$ and no element with frequency smaller than $\varphi-\epsilon$. We present an efficient online deterministic algorithm for solving this problem using $O(\min(n, \frac{polylog(n)}{\epsilon}))$ memory and $O(polylog(n))$ time per processing and outputting an element. It is the first such algorithm as the previous algorithms were either randomized, or processed elements in substantially larger time $\Omega(\min(n, \frac{\log n}{\epsilon}))$, or handled only insertions and required two passes over the stream (i.e., were not truly online). Our solution is almost-optimally scalable (with only a polylogarithmic overhead) and does not require randomness or scanning twice through the stream. We complement the algorithm analysis with a lower bound $\Omega(\min(n, \frac{1}{\epsilon}))$ on required memory.

Consensus is one of the most thoroughly studied problems in distributed computing, yet there are still complexity gaps that have not been bridged for decades. In particular, in the classical message-passing setting with processes' crashes, since the seminal works of Bar-Joseph and Ben-Or [1998] \cite{Bar-JosephB98} and Aspnes and Waarts [1996, 1998] \cite{AspnesW-SICOMP-96,Aspnes-JACM-98} in the previous century, there is still a fundamental unresolved question about communication complexity of fast randomized Consensus against a (strong) adaptive adversary crashing processes arbitrarily online. The best known upper bound on the number of communication bits is $\Theta(\frac{n^{3/2}}{\sqrt{\log{n}}})$ per process, while the best lower bound is $\Omega(1)$. This is in contrast to randomized Consensus against a (weak) oblivious adversary, for which time-almost-optimal algorithms guarantee amortized $O(1)$ communication bits per process \cite{GK-SODA-10}. We design an algorithm against adaptive adversary that reduces the communication gap by nearly linear factor to $O(\sqrt{n}\cdot\text{polylog } n)$ bits per process, while keeping almost-optimal (up to factor $O(\log^3 n)$) time complexity $O(\sqrt{n}\cdot\log^{5/2} n)$. More surprisingly, we show this complexity indeed can be lowered further, but at the expense of increasing time complexity, i.e., there is a {\em trade-off} between communication complexity and time complexity. More specifically, our main Consensus algorithm allows to reduce communication complexity per process to any value from $\text{polylog } n$ to $O(\sqrt{n}\cdot\text{polylog } n)$, as long as Time $\times$ Communication $= O(n\cdot \text{polylog } n)$. Similarly, reducing time complexity requires more random bits per process, i.e., Time $\times$ Randomness $=O(n\cdot \text{polylog } n)$.

In this work we address the question of efficiency of distributed computing in anonymous, congested and highly dynamic and not-always-connected networks/systems. More precisely, the system consists of an unknown number of anonymous nodes with congestion on links and local computation. Links can change arbitrarily from round to round, with only limitation that the union of any T consecutive networks must form a temporarily connected (multi-)graph on all nodes (knowledge of T is the only information the nodes require, otherwise the communication would not be feasible). Nodes do not have any IDs, only some number l of them have a bit distinguishing them from nodes without such a bit. In each round a node can send and receive messages from its current neighbors. Links and nodes are congested, in the sense that the length of messages and local cache memory for local computation is (asymptotically) logarithmic. All-to-all communication is a fundamental principle in distributed computing - it assumes that each node has an input message to be delivered to all other nodes. Without loss of generality, the size of each input message is logarithmic to fit in the link and node congestion assumption; otherwise, they could be split in logarithmic batches and considered one-by-one. Because of anonymity, each node needs to receive only a set of all input messages, each accompanied by a number of initiating nodes (message multiplicity). We prove that this task can be done in time polynomial in the (initially unknown) number of nodes n and in the lower bound on the isoperimetric numbers of dynamically evolving graphs. This allows to efficiently emulate a popular Congested Clique model on top of Anonymous Dynamic Congested Systems (ADCS) with Opportunistic Connectivity, even if the number of nodes may arbitrarily change in the beginning of emulation., Comment: 28 pages

We study deterministic distributed algorithms for broadcasting on multiple-access channels. Packet injection is modeled by leaky-bucket adversaries. There is a fixed set of stations attached to a channel. Additional features of the model of communication include an upper bound on the number of stations activated in a round, an individual injection rate, and randomness in generating and injecting packets. We demonstrate that some broadcast algorithms designed for ad-hoc channels have bounded latency for increased ranges of injection rates than in ad-hoc channels when executed on channels with a fixed number of stations against adversaries that can activate at most one station per round. Individual injection rates are shown to impact latency, as compared to the model of general leaky bucket adversaries. Outcomes of experiments are given that compare the performance of broadcast algorithms against randomized adversaries. The experiments include deterministic algorithms and randomized backoff algorithms.

We study the problem of online tree exploration by a deterministic mobile agent. Our main objective is to establish what features of the model of the mobile agent and the environment allow linear exploration time. We study agents that, upon entering to a node, do not receive as input the edge via which they entered. In such a model, deterministic memoryless exploration is infeasible, hence the agent needs to be allowed to use some memory. The memory can be located at the agent or at each node. The existing lower bounds show that if the memory is either only at the agent or only at the nodes, then the exploration needs superlinear time. We show that tree exploration in dual-memory model, with constant memory at the agent and logarithmic at each node is possible in linear time when one of two additional features is present: fixed initial state of the memory at each node (so called clean memory) or a single movable token. We present two algorithms working in linear time for arbitrary trees in these two models. On the other hand, in our lower bound we show that if the agent has a single bit of memory and one bit is present at each node, then exploration may require quadratic time on paths, if the initial memory at nodes could be set arbitrarily (so called dirty memory). This shows that having clean node memory or a token allows linear exploration of trees in the model with two types of memory, but having neither of those features may lead to quadratic exploration time even on a simple path.

The Quantitative Group Testing (QGT) is about learning a (hidden) subset $K$ of some large domain $N$ using a sequence of queries, where a result of a query provides information about the size of the intersection of the query with the unknown subset $K$. Almost all previous work focused on randomized algorithms minimizing the number of queries; however, in case of large domains $N$, randomization may result in a significant deviation from the expected precision. Others assumed unlimited computational power (existential results) or adaptiveness of queries. In this work we propose efficient non-adaptive deterministic QGT algorithms for constructing queries and deconstructing a hidden set $K$ from the results of the queries, without using randomization, adaptiveness or unlimited computational power. The efficiency is three-fold. First, in terms of almost-optimal number of queries - we improve it by factor nearly $|K|$ comparing to previous constructive results. Second, our algorithms construct the queries and reconstruct set $K$ in polynomial time. Third, they work for any hidden set $K$, as well as multi-sets, and even if the results of the queries are capped at $\sqrt{|K|}$. We also analyze how often elements occur in queries and its impact to parallelization and fault-tolerance of the query system.

In the Group Testing problem, the objective is to learn a subset K of some much larger domain N, using the shortest-possible sequence of queries Q. A feedback to a query provides some information about the intersection between the query and subset K. Several specific feedbacks have been studied in the literature, often proving different formulas for the estimate of the query complexity of the problem, defined as the shortest length of queries' sequence solving Group Testing problem with specific feedback. In this paper we study what are the properties of the feedback that influence the query complexity of Group Testing and what is their measurable impact. We propose a generic framework that covers a vast majority of relevant settings considered in the literature, which depends on two fundamental parameters of the feedback: input capacity $\alpha$ and output expressiveness $\beta$. They upper bound the logarithm of the size of the feedback function domain and image, respectively. To justify the value of the framework, we prove upper bounds on query complexity of non adaptive, deterministic Group Testing under some "efficient" feedbacks, for minimum, maximum and general expressiveness, and complement them with a lower bound on all feedbacks with given parameters $\alpha,\beta$. Our upper bounds also hold if the feedback function could get an input twisted by a malicious adversary, in case the intersection of a query and the hidden set is bigger than the feedback capacity $\alpha$. We also show that slight change in the feedback function may result in substantial worsening of the query complexity. Additionally, we analyze explicitly constructed randomized counterparts of the deterministic results. Our results provide some insights to what are the most useful bits of information an output-restricted feedback could provide, and open a number of challenging research directions.

Consider the problem: we are given $n$ boxes, labeled $\{1,2,\ldots, n\}$ by an adversary, each containing a single number chosen from an unknown distribution; these $n$ distributions are not necessarily identical. We are also given an integer $k \leq n$. We have to choose an order in which we will sequentially open these boxes, and each time we open the next box in this order, we learn the number in the box. Once we reject a number in a box, the box cannot be recalled. Our goal is to accept $k$ of these numbers, without necessarily opening all boxes, such that the accepted numbers are the $k$ largest numbers in the boxes (thus their sum is maximized). A natural approach to solve such problems is to use randomness to sample randomly ordered elements, however, as indicated in several sources, e.g., Turan et al. NIST'15, Bierhorst et al. Nature'18, pure randomness is hard to get in reality. We present an algorithm for this problem, which is provably and simultaneously near-optimal with respect to the achieved competitive ratio and the used amount of randomness. In particular, we construct a distribution on the orders with entropy $\Theta(\log\log n)$ such that a deterministic multiple-threshold algorithm gives a competitive ratio $1-O(\sqrt{\log k/k})$, for $k < \log n/\log \log n$. Our competitive ratio is simultaneously optimal and uses optimal entropy $\Theta(\log\log n)$, improving in three ways the previous best known algorithm, whose competitive ratio is $1 - O(1/k^{1/3}) - o(1)$., Comment: arXiv admin note: text overlap with arXiv:1502.02155 by other authors

Population protocols model information spreading and computation in network systems where pairwise node exchanges are determined by an external random scheduler and nodes have small memory. Most of the population protocols in the literature assume that the participating $n$ nodes are honest. Such an assumption may not be, however, accurate for large-scale systems of small devices. Hence, in this work, we study population protocols in a setting where up to $f$ nodes can be Byzantine. We examine the majority (binary) consensus problem against different levels of adversary strengths, ranging from the Full Byzantine adversary that has complete knowledge of all the node states to the Weak Content-Oblivious Byzantine adversary that has only knowledge about which exchanges take place. We also take into account Dynamic vs Static node corruption by the adversary. We give lower bounds that require any algorithm solving the majority consensus to have initial difference $d = \Omega(f + 1)$ for the tally between the two proposed values, which holds for both the Full Static and Weak Dynamic adversaries. We then present an algorithm that solves the majority consensus problem and tolerates $f \leq n / c$ Byzantine nodes, for some constant $c>0$, with $d = \Omega(f + \sqrt{n \log n})$ and $O(\log^3 n)$ parallel time steps, using $O(\log^3 n)$ states per node. We also give an alternative algorithm, with the same asymptotic performance, for $d = \Omega(\min\{f \log^2 n + 1,n\})$. Finally, we combine both algorithms into one using a new robust distributed common coin. The only other known previous work on Byzantine-resilient population protocols tolerates up to $f = o(\sqrt n)$ faulty nodes and was analyzed against a Static adversary; hence, our protocols significantly improve fault-tolerance by an $\omega(\sqrt n)$ factor and all of them work correctly against a stronger Dynamic adversary.

Counting the number of nodes in Anonymous Dynamic Networks is enticing from an algorithmic perspective: an important computation in a restricted platform with promising applications. Starting with Michail, Chatzigiannakis, and Spirakis [19], a flurry of papers sped up the running time guarantees from doubly-exponential to polynomial [16]. There is a common theme across all those works: a distinguished node is assumed to be present, because Counting cannot be solved deterministically without at least one. In the present work we study challenging questions that naturally follow: how to efficiently count with more than one distinguished node, or how to count without any distinguished node. More importantly, what is the minimal information needed about these distinguished nodes and what is the best we can aim for (count precision, stochastic guarantees, etc.) without any. We present negative and positive results to answer these questions. To the best of our knowledge, this is the first work that addresses them., Comment: arXiv admin note: text overlap with arXiv:1707.04282

We consider deterministic distributed algorithms for reaching agreement in synchronous networks of arbitrary topologies. Links are bi-directional and prone to failures while nodes stay non-faulty at all times. A faulty link may omit messages. Agreement among nodes is understood as holding in each connected component of a network obtained by removing faulty links. We call ``disconnected agreement'' the algorithmic problem of reaching such agreement. We introduce the concept of stretch, which is the number of connected components of a network, obtained by removing faulty links, minus~$1$ plus the sum of diameters of connected components. We define the concepts of ``fast'' and ``early-stopping'' algorithms for disconnected agreement by referring to stretch. A network has $n$ nodes and $m$ links. Nodes are normally assumed to know their own names and ability to associate communication with local ports. If we additionally assume that a bound~$\Lambda$ on stretch is known to all nodes, then there is an algorithm for disconnected agreement working in time $O(\Lambda)$ using messages of $O(\log n)$ bits. We give a general disconnected agreement algorithm operating in~$n+1$ rounds that uses messages of $O(\log n)$ bits. Let~$\lambda$ be an unknown stretch occurring in an execution; we give an algorithm working in time~$(\lambda+2)^3$ and using messages of $O(n\log n)$ bits. We show that disconnected agreement can be solved in the optimal $O(\lambda)$ time, but at the cost of increasing message size to~$O(m\log n)$. We also design an algorithm that uses only~$O(n)$ non-faulty links and works in time~$O(n m)$, while nodes start with their ports mapped to neighbors and messages carry $O(m\log n)$ bits. We prove lower bounds on the performance of disconnected-agreement solutions that refer to the parameters of evolving network topologies and the knowledge available to nodes.

We study the problem of randomized Leader Election in synchronous distributed networks with indistinguishable nodes. We consider algorithms that work on networks of arbitrary topology in two settings, depending on whether the size of the network, i.e., the number of nodes, is known or not. In the former setting, we present a new Leader Election protocol that improves over previous work by lowering message complexity and making it close to a lower bound by a factor of $\tilde{O}(\sqrt{t_{mix}\sqrt{\Phi}})$, where $\Phi$ is the conductance and $t_{mix}$ is the mixing time of the network graph. We then show that lacking the network size no Leader Election algorithm can guarantee that the election is final with constant probability, even with unbounded communication. Hence, we further classify the problem as Irrevocable Leader Election (the classic one, requiring knowledge of n - as is our first protocol) or Revocable Leader Election, and present a new polynomial time and message complexity Revocable Leader Election algorithm in the setting without knowledge of network size. We analyze time and message complexity of our protocols in the Congest model of communication.

Stability is an important issue in order to characterize the performance of a network, and it has become a major topic of study in the last decade. Roughly speaking, a communication network system is said to be stable if the number of packets waiting to be delivered (backlog) is finitely bounded at any one time. In this paper, we introduce a new family of combinatorial structures, which we call universally strong selectors, that are used to provide a set of transmission schedules. Making use of these structures, combined with some known queuing policies, we propose a packet-oblivious routing algorithm which is working without using any global topological information, and guarantees stability for certain injection rates. We show that this protocol is asymptotically optimal regarding the injection rate for which stability is guaranteed. Furthermore, we also introduce a packet-oblivious routing algorithm that guarantees stability for higher traffic. This algorithm is optimal regarding the injection rate for which stability is guaranteed. However, it needs to use some global information of the system topology.

We study the problem of bi-chromatic coloring of hypergraphs in the LOCAL distributed model of computation. This problem can easily be solved by a randomized local algorithm with no communication. However, it is not known how to solve it deterministically with only a polylogarithmic number of communication rounds. In this paper we indeed design such a deterministic algorithm that solves this problem with polylogarithmic number of communication rounds. This is an almost exponential improvement on the previously known deterministic local algorithms for this problem. Because the bi-chromatic coloring of hypergraphs problem is known to be complete in the class of all locally checkable graph problems, our result implies deterministic local algorithms with polylogarithmic number of communication rounds for all such problems for which an efficient randomized algorithm exists. This solves one of the fundamental open problems in the area of local distributed graph algorithms. By reductions due to Ghaffari, Kuhn and Maus [STOC 2017] this implies such polylogarithmically efficient deterministic local algorithms for many graph problems., Comment: Version date: 10 July 2019; some typos corrected; added explanation p. 5; paper submitted to ACM-SIAM SODA 2020; 13 pages

The paper studies the problem of reaching agreement in a distributed message-passing system prone to crash failures. Crashes are generated by \constrained\ adversaries - a \wadapt\ adversary, who has to fix in advance the set of $f$ crash-prone processes, or a \chainadapt\ adversary, who orders all the processes into $k$ disjoint chains and has to follow this pattern when crashing them. Apart from these constraints, both of them may crash processes in an adaptive way at any time. While commonly used \sadapt\ adversaries model attacks and \noadapt\ ones -- pre-defined faults, the constrained adversaries model more realistic scenarios when there are fault-prone dependent processes, e.g., in hierarchical or dependable software/hardware systems. We propose time-efficient consensus algorithms against such adversaries and also show how to improve the message complexity of proposed solutions. Finally, we show how to reach consensus against a \kthick\ adversary, limited by an arbitrary partial order \dk{with a maximal anti-chain of length $k$}. We complement our algorithmic results with (almost) tight lower bounds, and extend the one for \wadapt\ adversaries to hold also for (syntactically) weaker \noadapt\ adversaries. Together with the consensus algorithm against \wadapt\ adversaries (which automatically translates to \noadapt\ adversaries), these results extend the state-of-the-art of the popular class of \noadapt\ adversaries, in particular the result of Chor, Meritt and Shmoys~\cite{CMS}, and prove general separation between \sadapt\ and the constrained adversaries (including \noadapt) analyzed by Bar-Joseph and Ben-Or~\cite{BB} and others.

The randomized rumor spreading problem generates a big interest in the area of distributed algorithms due to its simplicity, robustness and wide range of applications. The two most popular communication paradigms used for spreading the rumor are Push and Pull algorithms. The former protocol allows nodes to send the rumor to a randomly selected neighbor at each step, while the latter is based on sending a request and downloading the rumor from a randomly selected neighbor, provided the neighbor has it. Previous analysis of these protocols assumed that every node could process all such push/pull operations within a single step, which could be unrealistic in practical situations. Therefore we propose a new framework for analysis rumor spreading accommodating buffers, in which a node can process only one push/pull message or push request at a time. We develop upper and lower bounds for randomized rumor spreading time in the new framework, and compare the results with analogous in the old framework without buffers., Comment: Manuscript submitted to DISC 2013

We consider the impact of scheduling disciplines on performance of routing in the framework of adversarial queuing. We propose an adversarial model which reflects stalling of packets due to transient failures and explicitly incorporates feedback produced by a network when packets are stalled. This adversarial model provides a methodology to study stability of routing protocols when flow-control and congestion-control mechanisms affect the volume of traffic. We show that any scheduling policy that is universally stable, in the regular model of routing that additionally allows packets to have two priorities, remains stable in the proposed adversarial model.

We investigate routing on networks modeled as multiple access channels, when packets are injected continually. There is an energy cap understood as a bound on the number of stations that can be switched on simultaneously. Each packet is injected into some station and needs to be delivered to its destination station via the channel. A station has to be switched on in order to receive a packet when it is heard on the channel. Each station manages when it is switched on and off by way of a programmable wakeup mechanism, which is scheduled by a routing algorithm. Packet injection is governed by adversarial models that determine upper bounds on injection rates and burstiness. We develop deterministic distributed routing algorithms and assess their performance in the worst-case sense. One of the algorithms maintains bounded queues for the maximum injection rate 1 subject only to the energy cap 3. This energy cap is provably optimal, in that obtaining the same throughput with the energy cap 2 is impossible. We give algorithms subject to the minimum energy cap 2 that have latency polynomial in the total number of stations n for each fixed adversary of injection rate less than 1. An algorithm is k-energy-oblivious if at most k stations are switched on in a round and for each station the rounds when it will be switched on are determined in advance. We give a k-energy-oblivious algorithm that has packet delay O(n) for adversaries of injection rates less than (k-1)/(n-1), and show that there is no k-energy-oblivious stable algorithm against adversaries with injection rates greater than k/n. We give a k-energy-oblivious algorithm routing directly that has latency O(n^2/k) for adversaries of sufficiently small injection rates that are O(k^2/n^2). We show that no k-energy-oblivious algorithm routing directly can be stable against adversaries with injection rates greater than k(k-1)/n(n-1).

We examine deterministic broadcasting on multiple-access channels for a scenario when packets are injected continuously by an adversary to the buffers of the devices at rate $\rho$ packages per round. The aim is to maintain system stability, that is, bounded queues. In contrast to previous work we assume that there is a strict limit of available power, defined as the total number of stations allowed to transmit or listen to the channel at a given time, that can never be exceeded. We study how this constraint influences the quality of services with particular focus on stability. We show that in the regime of deterministic algorithms, the significance of energy restriction depends strongly on communication capabilities of broadcasting protocols. For the adaptive and full-sensing protocols, wherein stations may substantially adopt their behavior to the injection pattern, one can construct efficient algorithms using very small amounts of power without sacrificing throughput or stability of the system. In particular, we construct constant-energy adaptive and full sensing protocols stable for $\rho=1$ and any $\rho<1$, respectively, even for worst case (adversarial) injection patterns. Surprisingly, for the case of acknowledgment based algorithms that cannot adopt to the situation on the channel (i.e., their transmitting pattern is fixed in advance), limiting power leads to reducing the throughput. That is, for this class of protocols in order to preserve stability we need to reduce injection rate significantly. We support our theoretical analysis by simulation results of algorithms constructed in the paper. We depict how they work for systems of moderate, realistic sizes. We also provide a comprehensive simulation to compare our algorithms with backoff algorithms, which are common in real-world implementations, in terms of queue sizes and energy consumption., Comment: 9 figures

We consider dynamic routing in multi-hop wireless networks with adversarial traffic. The model of wireless communication incorporates interferences caused by packets' arrivals into the same node that overlap in time. We consider two classes of adversaries: balanced and unbalanced. We demonstrate that, for each routing algorithm and an unbalanced adversary, the algorithm is unstable against this adversary in some networks. We develop a routing algorithm that has bounded packet latency against each balanced adversary.