Dariusz R. Kowalski
YOU?
Author Swipe
View article: Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries Open
Load balancing is among the basic primitives in distributed computing. In this paper, we consider this problem when executed locally on a network with nodes prone to failures. We show that there exist lightweight network topologies that ar…
View article: Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications
Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications Open
A superimposed code is a collection of binary vectors (codewords) with the property that no vector is contained in the Boolean sum of any $k$ others, enabling unique identification of codewords within any group of $k$. Superimposed codes a…
View article: Energy Efficient Adversarial Routing in Shared Channels
Energy Efficient Adversarial Routing in Shared Channels Open
We investigate routing in networks modeled as a set of stations sharing a channel. Packets are injected continually into stations. Each packet needs to be delivered to its destination station via the channel, possibly passing through relay…
View article: Searching for and Avoiding Hidden Sets Using Queries with Local Feedback
Searching for and Avoiding Hidden Sets Using Queries with Local Feedback Open
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…
View article: Beeping Deterministic CONGEST Algorithms in Graphs
Beeping Deterministic CONGEST Algorithms in Graphs Open
The Beeping Network (BN) model captures important properties of biological processes. Paradoxically, the extremely limited communication capabilities of such nodes has helped BN become one of the fundamental models for networks. Since in e…
View article: Beating Competitive Ratio 4 for Graphic Matroid Secretary
Beating Competitive Ratio 4 for Graphic Matroid Secretary Open
One of the classic problems in online decision-making is the secretary problem, where the goal is to hire the best secretary out of n rankable applicants or, in a natural extension, to maximize the probability of selecting the largest numb…
View article: Dynamic Metric Embedding into $\ell_p$ Space
Dynamic Metric Embedding into $\ell_p$ Space Open
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 (rand…
View article: Stable Blockchain Sharding under Adversarial Transaction Generation
Stable Blockchain Sharding under Adversarial Transaction Generation Open
View article: Sparse Spanners with Small Distance and Congestion Stretches
Sparse Spanners with Small Distance and Congestion Stretches Open
View article: Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed?
Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed? Open
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,…
View article: Stable Blockchain Sharding under Adversarial Transaction Generation
Stable Blockchain Sharding under Adversarial Transaction Generation Open
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$ proce…
View article: Distributed Fast Crash-Tolerant Consensus with Nearly-Linear Quantum Communication
Distributed Fast Crash-Tolerant Consensus with Nearly-Linear Quantum Communication Open
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 c…
View article: Correction to: Dynamic Multiple-Message Broadcast: Bounding Throughput in the Affectance Model
Correction to: Dynamic Multiple-Message Broadcast: Bounding Throughput in the Affectance Model Open
View article: Adversarial Contention Resolution Games
Adversarial Contention Resolution Games Open
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 …
View article: Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication
Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication Open
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 aut…
View article: Time and Energy Efficient Contention Resolution in Asynchronous Shared Channels
Time and Energy Efficient Contention Resolution in Asynchronous Shared Channels Open
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 sta…
View article: Deterministic non-adaptive contention resolution on a shared channel
Deterministic non-adaptive contention resolution on a shared channel Open
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 th…
View article: Stable Scheduling in Transactional Memory
Stable Scheduling in Transactional Memory Open
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…
View article: Optimal Algorithms for Free Order Multiple-Choice Secretary
Optimal Algorithms for Free Order Multiple-Choice Secretary Open
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 t…
View article: Light Agents Searching for Hot Information
Light Agents Searching for Hot Information Open
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 sing…
View article: Stable routing scheduling algorithms in multi-hop wireless networks
Stable routing scheduling algorithms in multi-hop wireless networks Open
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 stableif the number of packe…
View article: Efficient Algorithm for Deterministic Search of Hot Elements
Efficient Algorithm for Deterministic Search of Hot Elements Open
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…
View article: Improved Communication Complexity of Fault-Tolerant Consensus
Improved Communication Complexity of Fault-Tolerant Consensus Open
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,…
View article: Thoracic neoplasms
Thoracic neoplasms Open
View article: Efficient Distributed Computations in Anonymous Dynamic Congested Systems with Opportunistic Connectivity
Efficient Distributed Computations in Anonymous Dynamic Congested Systems with Opportunistic Connectivity Open
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 w…
View article: Broadcasting on Adversarial Multiple Access Channels
Broadcasting on Adversarial Multiple Access Channels Open
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 o…
View article: Tree exploration in dual-memory model
Tree exploration in dual-memory model Open
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, upo…
View article: Efficient Deterministic Quantitative Group Testing for Precise Information Retrieval
Efficient Deterministic Quantitative Group Testing for Precise Information Retrieval Open
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 unkn…
View article: Generalized Framework for Group Testing: Queries, Feedbacks and\n Adversaries
Generalized Framework for Group Testing: Queries, Feedbacks and\n Adversaries Open
In the Group Testing problem, the objective is to learn a subset K of some\nmuch larger domain N, using the shortest-possible sequence of queries Q. A\nfeedback to a query provides some information about the intersection between\nthe query…
View article: Generalized Framework for Group Testing: Queries, Feedbacks and Adversaries
Generalized Framework for Group Testing: Queries, Feedbacks and Adversaries Open
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 an…