4 papers
Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
Dariusz R. Kowalski, Jan Olkowski
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 s…
Beating Competitive Ratio 4 for Graphic Matroid Secretary
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski +3
One of the classic problems in online decision-making is the *secretary problem* where to goal is to maximize the probability of choosing the largest number from a randomly ordered…
Dynamic Metric Embedding into Space
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski +2
We give the first non-trivial decremental dynamic embedding of a weighted, undirected graph into space. Given a weighted graph undergoing a sequence of edge weight…
Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed?
Mohammad T. Hajiaghayi, Dariusz R. Kowalski, Jan Olkowski
We study the problem of reaching agreement in a synchronous distributed system by autonomous parties, when the communication links from/to faulty parties can omit messages. The…