Darek, with collaborators, started the subfield of adversarial shared channels. In a simplified setting, a multiple of autonomous processes, also called stations, are connected to a shared communication channel, in which a packet can be successfully transmitted if exactly one station attempts to transmit it at a time. Packets occur in stations according to some adversarial (worst-case) pattern, unknown to the distributed algorithm run by the stations, and are stored in local queues until successfully transmitted on the channel. The goal is to design algorithms that keep the queues bounded and achieve high throughput (of successfully transmitted packets) and low packet latency in arbitrarily long computations.
Darek produced a very large body of work that addresses and resolves several fundamental issues for the adversarial distribution of the input in time (even in an unbounded time period). The input could be packets, but also other resources or faults (e.g., jamming, crashes). In his papers, a first model for analyzing arbitrarily long executions of communication on a shared channel was introduced, and later developed, together with latency analysis, and later of fairness, queue sizes, etc. Darek also introduced a classification of protocols and proved separation bounds between them. The results included, for example, an adversarial version of the renowned Little's Law from the stochastic queuing theory, and the development of a new theory that combines queue sizes with latency and throughput.
Darek's contributions include further aspects of shared channels, such as asynchronous communication on the channel, consensus and mutual exclusion, adversarial models for analyzing stability and latency of transactional memory and sharding, classic scheduling with adversarial jamming, and many others. Several novel and technically involved results and techniques have been developed while pursuing his research on dynamic channels: a connection of adversarial dynamicity with online and stochastic models of shared channels, a construction of ultra-resilient superimposed codes which exploit close links with information theory and improve not only communication on dynamic shared channels but also in multi-hop beeping networks, contributions to the theory of selective families for radio networks, and more.
For his pioneering advancements on distributed computing over shared channels, we are proud to present the 2026 Prize for Innovation in Distributed Computing to Dariusz Kowalski. The prize will be awarded at SIROCCO 2026, to be held on June 9-11, 2026, in Durham, UK.
The 2026 Award committee:
Keren Censor-Hillel (Technion, Israel)
Yuval Emek (Technion, Israel)
Magnus Halldorsson (Reykjavik University, Iceland)
Sergio Rajsbaum (UNAM, Mexico)
Ulrich Schmid (TU Wien, Austria)
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
