Dariusz R. Kowalski

TCS Journal 2026 Journal Article

Anonymous adversarial dynamic networks with logarithmic memory and communication

• Dariusz R. Kowalski
• Miguel A. Mosteiro

In seminal work on Adversarial Dynamic Networks, Kuhn, Lynch and Oshman (STOC 2010) [19] studied dynamic networks in which links are selected by an adversary and the number of network nodes is initially unknown. In such networks, they showed upper and lower bounds for computing the size of the network and any computable function of the nodes initial inputs. In this work, we address the same question in dynamic networks which additionally are: anonymous, possibly disconnected, and where internal memory and links’ bandwith are logarithmically limited. In the above framework, we study a fundamental communication principle – the All-to-all problem: each node has an input message to be delivered to all other nodes. (Once a node receives all inputs, any function can be computed locally.) Because of anonymity, each node needs to receive only a set of all input messages, each accompanied by a number of their initiating nodes (message multiplicity). We prove that this can be done deterministically in time proportional to the total number of messages’ bits multiplied by a small polynomial in networks’ parameters – namely, in the (initially unknown) number of nodes n and in the lower bound on the isoperimetric numbers of dynamically evolving graphs i min. Our results prove that a polynomial bit-throughput is possible in adversarial and anonymous dynamic networks with logarithmically limited bandwidth and internal memory.

AAAI Conference 2025 Conference Paper

Searching for and Avoiding Hidden Sets Using Queries with Local Feedback

• Tomasz Jurdzinski
• Dariusz R. Kowalski

Discovering elements of a hidden set, also known as Group Testing (GT), is a well-established area in which one party tries to discover elements hidden by the other party by asking queries and analyzing feedback. The feedback is a function of the intersection of the query with the hidden set - in our case, it is a classical double-threshold function, which returns i if the intersection is a singleton i and "null" otherwise (i.e., when the intersection is empty or of size at least 2). In this work, we enhance GT by two features. First, we introduce a local feedback framework to this problem: each hidden element is an "autonomous" element and can analyze feedback itself, but only for the queries to which it belongs. The goal is to design a deterministic non-adaptive sequence of queries that enables each non-hidden element to learn about all other hidden elements. We show that, surprisingly, this task requires substantially more queries than the classic group testing -- by proving a super-cubic (in terms of the number of hidden elements) lower bound and by constructing a specific query sequence of slightly longer length. Such a query system is also an extension of a well-known superimposed code, in a way that the decoding can be done only by the owners of the codewords. Second, we extend the results to the model where elements may belong to certain clusters and retrieving them could be done only via queries avoiding elements from "interfering" clusters. The main challenge is in not knowing which interfering clusters are non-empty (and thus, need to be avoided) and how to speed up the retrieval process by asking queries across many clusters. Our algorithms can be generalized to other feedback functions, to adversarial/stochastic fault-prone scenarios, implemented in a distributed setting and applied to the information theory and codes.

ICML Conference 2024 Conference Paper

Dynamic Metric Embedding into lp Space

• Kiarash Banihashem
• MohammadTaghi Hajiaghayi
• Dariusz R. Kowalski
• Jan Olkowski
• Max Springer

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 distortion, of their distance in $G$. Our main result is a dynamic algorithm with expected distortion $O(\log^2 n)$ and total update time $O\left((m^{1+o(1)} \log^2 W + Q)\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 ’85 to the expanding 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.

IJCAI Conference 2024 Conference Paper

Online Sampling and Decision Making with Low Entropy

• Mohammad Taghi Hajiaghayi
• Dariusz R. Kowalski
• Piotr Krysta
• Jan Olkowski

Suppose we are given an integer k and n boxes, labeled 1, 2, …, n by an adversary, each containing a single number chosen from an unknown distribution; the n distributions not necessarily identical. We have to choose an order to sequentially open the boxes, and each time we open the next box in this order, we learn the number inside. If 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). This problem, sometimes called a free order multiple-choice secretary problem, is one of the classic examples of online decision making problems. A natural approach to solve such problems is to sample elements in random order; however, as indicated in several sources, e. g. , Turan et al. NIST 2015 [35], Bierhorst et al. Nature 2018 [10], pure randomness is hard to get in reality. Thus, pseudorandomness has to be used, with a small entropy. We show that with a very small O(log log n) entropy an almost-optimal approximation of the value of k largest numbers can be selected, with only a polynomially small additive error, for k 1.

SODA Conference 2024 Conference Paper

Power of Posted-price Mechanisms for Prophet Inequalities

• Kiarash Banihashem
• MohammadTaghi Hajiaghayi
• Dariusz R. Kowalski
• Piotr Krysta
• Jan Olkowski

We study the power of posted pricing mechanisms for Bayesian online optimization problems subject to combinatorial feasibility constraints. When the objective is to maximize social welfare, the problem is widely studied in the literature on prophet inequalities. While most (though not all) existing algorithms for prophet inequalities are implemented using a pricing mechanism, whether or not this can be done in general is unknown, and was formally left as an open question by Dutting, Feldman, Kesselheim, and Lucier (FOCS 2017, SICOMP 2020). Understanding the power and limitations of posted prices is important from a mechanism design perspective because any posted price mechanism is truthful, and is also interesting in its own right as it can guide future research on prophet inequalities. We show that any prophet inequality has an implementation using a posted price mechanism, thereby resolving the open question of Dutting et al. Given an algorithm for Bayesian online optimization, we show that it can be transformed, in a black-box manner, to a posted price algorithm that has the same or higher expected social welfare and preserves the distribution over the assigned outcomes. We further show how to implement our reduction efficiently under standard assumptions using access to a sampling oracle. As an immediate consequence, we obtain improved pricing-based prophet inequalities for maximum weight matching, resolving an open problem of Ezra, Feldman, Gravin and Tang (EC 2020, MOR 2022). Correa and Cristi (STOC 2023) proved recently an existence of prophet inequality with constant approximation ratio for online social welfare maximizing combinatorial auctions with subadditive valuations. They left as an open problem to provide a posted pricing based implementation of their algorithm. Our technique resolves this question in affirmative as well.

IJCAI Conference 2023 Conference Paper

Adversarial Contention Resolution Games

• Giorgos Chionas
• Bogdan S. Chlebus
• Dariusz R. Kowalski
• Piotr Krysta

We study contention resolution (CR) on a shared channel modelled as a game with selfish players. There are n agents and the adversary chooses some k smaller than n of them as players. Each participating player in a CR game has a packet to transmit. A transmission is successful if it is performed as the only one at a round. Each player aims to minimize its packet latency. We introduce the notion of adversarial equilibrium (AE), which incorporates adversarial selection of players. We develop efficient deterministic communication algorithms that are also AE. We characterize the price of anarchy in the CR games with respect to AE.

TCS Journal 2022 Journal Article

Generalized framework for Group Testing: Queries, feedbacks and adversaries

• Marek Klonowski
• Dariusz R. Kowalski
• Dominik Pająk

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 α and output expressiveness β. 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 α, β. 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 α. 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.

STOC Conference 2022 Conference Paper

Improved communication complexity of fault-tolerant consensus

• MohammadTaghi Hajiaghayi
• Dariusz R. Kowalski
• Jan Olkowski

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 [PODC 1998] and Aspnes and Waarts [SICOMP 1996, JACM 1998] 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 Θ( n 3/2 /√log n ) per process, while the best lower bound is Ω(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. We design an algorithm against adaptive adversary that reduces the communication gap by nearly linear factor to O (√ n · n ) bits per process, while keeping almost-optimal (up to factor O (log 3 n )) time complexity O (√ n ·log 5/2 n ).

TCS Journal 2022 Journal Article

Information dissemination in wireless ad-hoc networks under the weighted-TIM framework

• Lu Dong
• Dariusz R. Kowalski
• Harshita Kudaravalli
• Miguel A. Mosteiro

We study communication from layer to layer of a network modeling it as a bipartite graph of transmitters and receivers. We seek to minimize the time needed for all receivers to get a message held by all transmitters. We study this Layer Dissemination problem under the Weighted Topological Interference Management (W-TIM) framework, which subsumes previous models of interference. We present randomized and deterministic protocols for Layer Dissemination, based on Selective-with-Interference Families, a combinatorial object related to group testing non-adaptive algorithms and superimposed codes. Our approach combines an engineering solution with theoretical guarantees. We characterize the network with a global measure of interference based on measurements in the specific deployment area. Then, our protocols distributedly produce an ad-hoc transmissions schedule for dissemination. We complement our theoretical study with simulations of a real network-deployment area to compare our protocols with previous work for models that ignore some physical constraints. The striking improvement in performance shown by our simulations with respect to using previous simplified models of interference shows the importance of using W-TIM to develop algorithms.

IJCAI Conference 2022 Conference Paper

Light Agents Searching for Hot Information

• Dariusz R. Kowalski
• Dominik Pajak

Agent-based crawlers are commonly used in network maintenance and information gathering. In order not to disturb the main functionality of the system, whether acting at nodes or being in transit, they need to operate online, perform a single operation fast and use small memory. They should also be preferably deterministic, as crawling agents have limited capabilities of generating a large number of truly random bits. We consider a system in which an agent receives an update, typically an insertion or deletion, of some information upon visiting a node. On request, the agent needs to output hot information, i. e. , with the net occurrence above certain frequency threshold. A desired time and memory complexity of such agent should be poly-logarithmic in the number of visited nodes and inversely proportional to the frequency threshold. Ours is the first such agent with rigorous analysis and a complementary almost-matching lower bound.

TCS Journal 2022 Journal Article

Stable routing scheduling algorithms in multi-hop wireless networks

• Vicent Cholvi
• P. Garncarek
• T. Jurdziński
• Dariusz R. Kowalski

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 number of routing scheduling algorithms which, making use of certain knowledge about the network's structure, guarantee stability for certain injection rates. First, we introduce two new families of combinatorial structures, which we call universally strong selectors and generalized universally strong selectors, that are used to provide a set of transmission schedules. Making use of these structures, we propose two local-knowledge packet-oblivious routing scheduling algorithms. The first proposed routing scheduling algorithm only needs to know some upper bounds on the number of links and on the network's degree, and is asymptotically optimal regarding the injection rate for which stability is guaranteed. The second proposed routing scheduling algorithm is close to be asymptotically optimal, but it only needs to know an upper bound on the number of links. For such algorithms, we also provide some results regarding both the maximum latencies and queue lengths. Furthermore, we also evaluate how the lack of global knowledge about the system topology affects the performance of the routing scheduling algorithms.

MFCS Conference 2022 Conference Paper

Tree Exploration in Dual-Memory Model

• Dominik Bojko
• Karol Gotfryd
• Dariusz R. Kowalski
• Dominik Pajak

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 a node, do not receive as input the edge via which they entered. In such 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 in the degree at each node is possible in linear time when one of the 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 the exploration may require quadratic time even 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 time exploration of trees in the dual-memory model, but having neither of those features may lead to quadratic exploration time even on a simple path.

TCS Journal 2020 Journal Article

Token traversal in ad hoc wireless networks via implicit carrier sensing

• Tomasz Jurdzinski
• Dariusz R. Kowalski
• Michal Rozanski
• Grzegorz Stachowiak

Communication problems in ad hoc wireless networks have been already widely studied under the SINR model, but a vast majority of results concern networks with constraints on connectivity, so called strongly-connected networks. In such networks, connectivity is defined based on highly reliable links, that is, where both ends are located far closer from their transmission boundaries. What happens if the network is not strongly-connected, e. g. , it contains some long but still viable “shortcut links” connecting transmission boundaries? It is known that even a single broadcast in such ad hoc weakly-connected networks with uniform transmission powers requires Ω ( n ) communication rounds, where n is the number of nodes in the network. The best up-to-date (randomized) distributed algorithm, designed by Daum et al. [1], accomplishes broadcast task in O ( n log 2 ⁡ n ) communication rounds with high probability. In this work, inspired by the work on broadcasting, we show a novel deterministic distributed implementation of token traversal — a fundamental tool in distributed systems — in the SINR model with uniform transmission powers and no restriction on connectivity. We show that it is efficient even in a very harsh model of weakly-connected networks without GPS, carrier sensing and other helping features. We apply this method to span a traversal tree and accomplish broadcast in O ( n log ⁡ N ) communication rounds, deterministically, provided nodes are equipped with unique IDs in the range [ 1, N ] for some integer N ≥ n. This result implies an O ( n log ⁡ n ) -round randomized solution that does not require IDs, which improves the result from [1]. The lower bound Ω ( n log ⁡ N ) for deterministic algorithms proved in our work shows that our result is tight without randomization. Our implementation of token traversal routine, efficient in terms of time and memory, is based on a novel implicit algorithmic carrier sensing method and a new type of selectors, which might be of independent interest and applicable to other communication tasks in distributed ad hoc setting.

TCS Journal 2019 Journal Article

Online packet scheduling under adversarial errors

• Paweł Garncarek
• Tomasz Jurdziński
• Dariusz R. Kowalski
• Krzysztof Loryś

We consider the problem of scheduling packets of different sizes via a directed communication link prone to errors, where dynamic packet arrivals and errors are modeled by an adversary. Packets arrive over time to be transmitted over a channel in which instantaneous errors occur at times not known to the algorithm in advance. We focus on estimating the competitive throughput of online scheduling algorithms defined as the ratio between the total size of packets successfully transmitted by an online algorithm and the largest total size of packets which can be transmitted for the same arrival and error patterns. First, we design two online algorithms with optimal competitive throughput in various scenarios. One algorithm works for any f ≥ 1 channels and attains the competitive throughput 1/2 provided that sizes of packets satisfy the divisibility property (i. e. , any larger size is divisible by any smaller). The other algorithm achieves the optimal competitive throughput in ( 1 / 3, 1 / 2 ] for arbitrary sizes of packets on one communication channel, where the exact value of the competitive throughput depends on the sizes of packets. Second, we focus on algorithms working with speedup s ≥ 1. In this setting, online algorithms transmit packets s times faster than the offline optimum solution they are compared against. We design an algorithm which attains the competitive throughput 1 if it works with speedup 2 in the case that sizes of packets satisfy the divisibility property and with speedup s ∈ [ 4, 6 ) for arbitrary sizes of packets. This demonstrates that throughput of the best online fault-tolerant scheduling algorithms scales well with resource augmentation.

I&C Journal 2018 Journal Article

Information gathering in ad-hoc radio networks with tree topology

• Marek Chrobak
• Kevin P. Costello
• Leszek Gasieniec
• Dariusz R. Kowalski

We study the problem of information gathering in ad-hoc radio networks, focusing on the case when the network forms a tree, with edges directed towards the root. Initially, each node has a rumor, and we aim to deliver all rumors to the root as quickly as possible without knowing the tree's topology in advance. In the deterministic case, where nodes are labeled with small integers, we give an O ( n ) -time protocol for the model with unbounded message size, and an O ( n log ⁡ n ) -time protocol for bounded message size. We also consider fire-and-forward protocols, in which nodes can transmit only their own rumor or the rumor received in the previous step. We give a deterministic fire-and-forward protocol with running time O ( n 1. 5 ), and show that it is asymptotically optimal. We also present a randomized O ( n log ⁡ n ) -time protocol in the model without node labels or aggregation, and show that it is asymptotically optimal.

TCS Journal 2017 Journal Article

Adaptive packet scheduling over a wireless channel under constrained jamming

• Antonio Fernández Anta
• Chryssis Georgiou
• Dariusz R. Kowalski
• Elli Zavou

In this work we consider the communication over a wireless link, between a sender and a receiver, being disrupted by a jammer. The objective of the sender is to transmit as much data as possible to the receiver in the most efficient way. The data is sent as the payload of packets, and becomes useless if the packet is jammed. We consider a jammer with constrained power, defined by parameters ρ and σ, which represent the rate at which the adversary may jam the channel, and the length of the largest burst of jams it can cause, respectively. This definition translates to the Adversarial Queuing Theory (AQT) constraints, typically used for packet arrivals. We propose deterministic algorithms that decide the length of the packets sent in order to maximize the goodput rate; i. e. , the amount of useful payload successfully transmitted over time. To do so, we first define and study a static version of the problem, which is used as a building block for the dynamic problem. We start by assuming packets of the same length and characterizing the corresponding quasi-optimal length. Then, we show that by adapting the length of the packets, the goodput rate can be improved. Hence, we develop optimal adaptive algorithms that choose the packet lengths depending on the jams that have occurred up to that point in time, in order to maximize the total payload transmitted successfully over a period T in the presence of up to f jams.

TCS Journal 2017 Journal Article

Contention resolution in a non-synchronized multiple access channel

• Gianluca De Marco
• Dariusz R. Kowalski

Multiple access channel is a well-known communication model that deploys properties of many network systems, such as Aloha multi-access systems, local area Ethernet networks, satellite communication systems, packet radio networks. The fundamental aspect of this model is to provide efficient communication and computation in the presence of restricted access to the communication resource: at most one station can successfully transmit at a time, and a wasted round occurs when more than one station attempts to transmit at the same time. In this work we consider the problem of contention resolution in a multiple access channel in a realistic scenario when up to k stations out of n join the channel at different times. The goal is to let at least one station to transmit alone, which results in successful delivery of the message through the channel. We present three algorithms: two of them working under some constrained scenarios, and achieving optimal time complexity Θ ( k log ⁡ ( n / k ) + 1 ), while the third general algorithm accomplishes the goal in time O ( k log ⁡ n log ⁡ log ⁡ n ).

I&C Journal 2017 Journal Article

Doing-it-All with bounded work and communication

• Bogdan S. Chlebus
• Leszek Gąsieniec
• Dariusz R. Kowalski
• Alexander A. Schwarzmann

We consider the Do-All problem, where p cooperating processors need to complete t similar and independent tasks in an adversarial setting. Here we deal with a synchronous message passing system with processors that are subject to crash failures. Efficiency of algorithms in this setting is measured in terms of workcomplexity and communication complexity. When work and communication are considered to be comparable resources, then the overall efficiency is meaningfully expressed in terms of effort defined as work + communication. We develop and analyze a constructive algorithm that has work O ( t + p log ⁡ p ( p log ⁡ p + t log ⁡ t ) ) and a nonconstructive algorithm that has work O ( t + p log 2 ⁡ p ). The latter result is close to the lower bound Ω ( t + p log ⁡ p / log ⁡ log ⁡ p ) on work. The effort of each of these algorithms is proportional to its work when the number of crashes is bounded above by c p, for some positive constant c < 1. We also present a nonconstructive algorithm that has effort O ( t + p 1. 77 ).

TCS Journal 2016 Journal Article

Scalable wake-up of multi-channel single-hop radio networks

• Bogdan S. Chlebus
• Gianluca De Marco
• Dariusz R. Kowalski

We consider single-hop radio networks with multiple channels as a model of wireless networks. There are n stations connected to b radio channels that do not provide collision detection. A station uses all the channels concurrently and independently. Some k stations may become active spontaneously at arbitrary times. The goal is to wake up the network, which occurs when all the stations hear a successful transmission on some channel. Duration of a waking-up execution is measured starting from the first spontaneous activation. We present a deterministic algorithm that wakes up a network in O ( k log 1 / b ⁡ k log ⁡ n ) time, where k is unknown. We give a deterministic scalable algorithm for the special case when b > d log ⁡ log ⁡ n, for some constant d > 1, which wakes up a network in O ( k b log ⁡ n log ⁡ ( b log ⁡ n ) ) time, with k unknown. This algorithm misses time optimality by at most a factor of O ( log ⁡ n ( log ⁡ b + log ⁡ log ⁡ n ) ), because any deterministic algorithm requires Ω ( k b log ⁡ n k ) time. We give a randomized algorithm that wakes up a network within O ( k 1 / b ln ⁡ 1 ϵ ) rounds with a probability that is at least 1 − ϵ, for any 0 < ϵ < 1, where k is known. We also consider a model of jamming, in which each channel in any round may be jammed to prevent a successful transmission, which happens with some known parameter probability p, independently across all channels and rounds. For this model, we give two deterministic algorithms for unknown k: one wakes up a network in time O ( log − 1 ⁡ ( 1 p ) k log ⁡ n log 1 / b ⁡ k ), and the other in time O ( log − 1 ⁡ ( 1 p ) k b log ⁡ n log ⁡ ( b log ⁡ n ) ) when the inequality b > log ⁡ ( 128 b log ⁡ n ) holds, both with probabilities that are at least 1 − 1 / poly ( n ).

TCS Journal 2015 Journal Article

Message and time efficient multi-broadcast schemes

• Liron Levin
• Dariusz R. Kowalski
• Michael Segal

We consider message and time efficient broadcasting and multi-broadcasting in wireless ad-hoc networks, where a subset of nodes, each with a unique rumor, wish to broadcast their rumors to all destinations while minimizing the total number of transmissions and total time until all rumors arrive to their destination. Under centralized settings, we introduce a novel approximation algorithm that provides almost optimal results with respect to the number of transmissions and total time, separately. Later on, we show how to efficiently implement this algorithm under distributed settings, where the nodes have only local information about their surroundings. In addition, we show multiple approximation techniques based on the network collision detection capabilities and explain how to calibrate the algorithms' parameters to produce optimal results for time and messages.

TCS Journal 2015 Journal Article

Online parallel scheduling of non-uniform tasks: Trading failures for energy

• Antonio Fernández Anta
• Chryssis Georgiou
• Dariusz R. Kowalski
• Elli Zavou

Consider a system in which tasks of different execution times arrive continuously and have to be executed by a set of machines that are prone to crashes and restarts. In this paper we model and study the impact of parallelism and failures on the competitiveness of such an online system. In a fault-free environment, a simple Longest-In-System scheduling policy, enhanced by a redundancy-avoidance mechanism, guarantees optimality in a long-term execution. In the presence of failures though, scheduling becomes a much more challenging task. In particular, no parallel deterministic algorithm can be competitive against an off-line optimal solution, even with one single machine and tasks of only two different execution times. We find that when additional energy is provided to the system in the form of processing speedup, the situation changes. Specifically, we identify thresholds on the speedup under which such competitiveness cannot be achieved by any deterministic algorithm, and above which competitive algorithms exist. Finally, we propose algorithms that achieve small bounded competitive ratios when the speedup is over the threshold.

SODA Conference 2010 Conference Paper

Distributed Agreement with Optimal Communication Complexity

• Seth Gilbert
• Dariusz R. Kowalski

TCS Journal 2010 Journal Article

Fast radio broadcasting with advice

• David Ilcinkas
• Dariusz R. Kowalski
• Andrzej Pelc

We study deterministic broadcasting in radio networks in the recently introduced framework of network algorithms with advice. We concentrate on the problem of trade-offs between the number of bits of information (size of advice) available to nodes and the time in which broadcasting can be accomplished. In particular, we ask what is the minimum number of bits of information that must be available to nodes of the network, in order to broadcast very fast. For networks in which constant time broadcast is possible under a complete knowledge of the network we give a tight answer to the above question: O ( n ) bits of advice are sufficient but o ( n ) bits are not, in order to achieve constant broadcasting time in all these networks. This is in sharp contrast with geometric radio networks of constant broadcasting time: we show that in these networks a constant number of bits suffices to broadcast in constant time. For arbitrary radio networks we present a broadcasting algorithm whose time is inverse-proportional to the size of the advice.

TCS Journal 2008 Journal Article

How to meet in anonymous network

• Dariusz R. Kowalski
• Adam Malinowski

A set of k mobile agents with distinct identifiers and located in nodes of an unknown anonymous connected network, have to meet at some node. We show that this gathering problem is no harder than its special case for k = 2, called the rendezvous problem, and design deterministic protocols solving the rendezvous problem with arbitrary startups in rings and in general networks. The measure of performance is the number of steps since the startup of the last agent until the rendezvous is achieved. For rings we design an oblivious protocol with cost O ( n log ℓ ), where n is the size of the network and ℓ is the minimum label of participating agents. This result is asymptotically optimal due to the lower bound showed by [A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc, Deterministic rendezvous in graphs, Algorithmica 46 (2006) 69–96]. For general networks we show a protocol with cost polynomial in n and log ℓ, independent of the maximum difference τ of startup times, which answers in the affirmative the open question by [A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc, Deterministic rendezvous in graphs, Algorithmica 46 (2006) 69–96].

STOC Conference 2005 Conference Paper

Cooperative asynchronous update of shared memory

• Bogdan S. Chlebus
• Dariusz R. Kowalski

The Write-All problem for an asynchronous shared-memory system has the objective for the processes to update the contents of a set of shared registers, while minimizing the total number of read and write operations. First abstracted by Kanellakis and Shvartsman [12], Write-All is among the standard problems in distributed computing. The model consists of $n$ asynchronous processes and n registers, where every process can read and write to any register. Processes may fail by crashing. The most efficient previously known deterministic algorithm performs O(n 1+ε ) reads and writes, for an arbitrary fixed constant ε>0, and is due to Anderson and Woll [4]. This paper presents a new deterministic algorithm that performs O(n polylog n) read/write operations, thus improving the best previously known upper bound from polynomial to polylogarithmic in the average number of read/write operations per process. Using an approach to store and retrieve information about progress made in auxiliary registers, the novelty of the new algorithm is in using a family of multi-partite graphs with expansion properties to structure a set of registers as a graph and then have each asynchronous process explore a part of the graph according to its pattern of traversals. An explicit instantiation of our Write-All algorithm, based on best-known polynomial-time constructions of lossless expanders and a-expanding graphs, performs n • 2 O(log 3 log n) reads and writes. In this explicit solution to Write-All, the processes perform asymptotically less read/write operations than the most efficient non-explicit solution known before.

TCS Journal 2005 Journal Article

Efficient gossip and robust distributed computation

• Chryssis Georgiou
• Dariusz R. Kowalski
• Alexander A. Shvartsman

This paper presents an efficient deterministic gossip algorithm for p synchronous, crash-prone, message-passing processors. The algorithm has time complexity T = O ( log 2 p ) and message complexity M = O ( p 1 + ε ), for any ε > 0. This substantially improves the message complexity of the previous best algorithm that has M = O ( p 1. 77 ), while maintaining the same time complexity. The strength and utility of the new result is demonstrated by constructing a deterministic algorithm for performing n tasks in this distributed setting. Previous solutions used coordinator or check-pointing approaches, immediately incurring a work penalty Ω ( n + f · p ) for f crashes, or relied on strong communication primitives, such as reliable broadcast, or had work too close to the trivial Θ ( p · n ) bound of oblivious algorithms. The new algorithm uses p crash-prone processors to perform n similar and idempotent tasks so long as one processor remains active. The work of the algorithm is W = O ( n + p · min { f + 1, log 3 p } ) and its message complexity is M = O ( fp ε + p min { f + 1, log p } ), for any ε > 0. This substantially improves the work complexity of previous solutions using simple point-to-point messaging, while “meeting or beating” the corresponding message complexity bounds. The new algorithms use communication graphs and permutations with certain combinatorial properties that are shown to exist. The algorithms are correct for any permutations, and in particular, the same expected bounds can be achieved using random permutations.

I&C Journal 2005 Journal Article

Performing work with asynchronous processors: Message-delay-sensitive bounds

• Dariusz R. Kowalski
• Alex A. Shvartsman

This paper considers the problem of performing tasks in asynchronous distributed settings. This problem, called Do-All, has been substantially studied in synchronous models, but there is a dearth of efficient algorithms for asynchronous message-passing processors. Do-All can be trivially solved without any communication by an algorithm where each processor performs all tasks. Assuming p processors and t tasks, this requires work Θ(p · t). Thus, it is important to develop subquadratic solutions (when p and t are comparable) by trading computation for communication. Following the observation that it is not possible to obtain subquadratic work when the message delay d is substantial, e. g. , d =Θ(t), this work pursues a message-delay-sensitive approach. Here, the upper bounds on work and communication are given as functions of p, t, and d, the upper bound on message delays, however, algorithms have no knowledge of d and they cannot rely on the existence of an upper bound on d. This paper presents two families of asynchronous algorithms achieving, for the first time, subquadratic work as long as d = o (t). The first family uses as its basis a shared-memory algorithm without having to emulate atomic registers assumed by that algorithm. These deterministic algorithms have work O(tp ε + pd⌈t/d⌉ ε ) for any ε >0. The second family uses specific permutations of tasks, with certain combinatorial properties, to sequence the work of the processors. These randomized (deterministic) algorithms have expected (worst-case) work O(t log p + pd log(2+ t/d)). Another important contribution in this work is the first delay-sensitive lower bound for this problem that helps explain the behavior of our algorithms: any randomized (deterministic) algorithm has expected (worst-case) work of Ω(t + pd log d+1 t).

TCS Journal 2005 Journal Article

Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism

• Dariusz R. Kowalski
• Andrzej Pelc

We consider the time of broadcasting in ad hoc radio networks modeled as undirected graphs. In such networks, every node knows only its own label and a linear bound on the number of nodes but is unaware of the topology of the network, or even of its own neighborhood. Our aim is to study to what extent the availability of two important characteristics of a broadcasting algorithm influences optimal broadcasting time. These characteristics are adaptiveness and randomization. Our contribution is establishing upper and lower bounds on optimal broadcasting time for three classes of algorithms: adaptive deterministic, oblivious randomized and oblivious deterministic. In two cases we present tight bounds, and in one case a small gap remains. We show that for deterministic adaptive algorithms time Ω ( n ) is required even for n-node networks of constant diameter. This lower bound is strongest possible, since linear time algorithms are known, and hence establishes optimal time Θ ( n ) for this class. For oblivious randomized algorithms we show an upper bound O ( n min { D, log n } ) and a lower bound Ω ( n ) on optimal expected broadcasting time in n-node networks of diameter D. Finally, for oblivious deterministic algorithms we show matching upper and lower bounds Θ ( n min { D, n } ) on optimal broadcasting time. Our results imply that enforcing obliviousness has at least as strong negative impact on broadcasting time as enforcing determinism, and that algorithms having both these features are strictly less efficient than those having only one of them.

STOC Conference 2004 Conference Paper

Collective asynchronous reading with polylogarithmic worst-case overhead

• Bogdan S. Chlebus
• Dariusz R. Kowalski
• Alexander A. Shvartsman

SODA Conference 2004 Conference Paper

The wake-up problem in multi-hop radio networks

• Marek Chrobak
• Leszek Gasieniec
• Dariusz R. Kowalski

FOCS Conference 2002 Conference Paper

Deterministic Broadcasting Time in Radio Networks of Unknown Topology

• Dariusz R. Kowalski
• Andrzej Pelc

In a seminal paper, Bar-Yehuda et al. (1992) considered broadcasting in radio networks whose nodes know only their own label and labels of their neighbors. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks, by constructing a class of graphs of diameter 3, with the property that every broadcasting algorithm requires linear time on one of these graphs. Due to a subtle error in the argument, this result is incorrect. We construct an algorithm that broadcasts in logarithmic time on all graphs from the work of Bar-Yehuda et al. Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter o(log log n). On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time /spl Omega/(4/spl radic/n) on one of these graphs. In view of the randomized algorithm, running in expected time O(D log n + log/sup 2/ n) on all n-node graphs of diameter D, our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting.