DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.150

Optimal k-Secretary with Logarithmic Memory

Authors: Mingda Qiao and Wei Zhang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We study memory-bounded algorithms for the k-secretary problem. The algorithm of Kleinberg (SODA 2005) achieves an optimal competitive ratio of 1 - O(1/√k), yet a straightforward implementation requires Ω(k) memory. Our main result is a k-secretary algorithm that matches the optimal competitive ratio using O(log k) words of memory. We prove this result by establishing a general reduction from k-secretary to (random-order) quantile estimation, the problem of finding the k-th largest element in a stream. We show that a quantile estimation algorithm with an O(k^{α}) expected error (in terms of the rank) gives a (1 - O(1/k^{1-α}))-competitive k-secretary algorithm with O(1) extra words. We then introduce a new quantile estimation algorithm that achieves an O(√k) expected error bound using O(log k) memory. Of independent interest, we give a different algorithm that uses O(√k) words and finds the k-th largest element exactly with high probability, generalizing a result of Munro and Paterson (1980).

Cite as

Mingda Qiao and Wei Zhang. Optimal k-Secretary with Logarithmic Memory. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 150:1-150:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{qiao_et_al:LIPIcs.ICALP.2026.150,
  author =	{Qiao, Mingda and Zhang, Wei},
  title =	{{Optimal k-Secretary with Logarithmic Memory}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{150:1--150:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.150},
  URN =		{urn:nbn:de:0030-drops-265394},
  doi =		{10.4230/LIPIcs.ICALP.2026.150},
  annote =	{Keywords: Streaming algorithms, online algorithms, secretary problem}
}

Document

DOI: 10.4230/OASIcs.NINeS.2026.13

In-Kernel Aggregation and Broadcast Acceleration for Distributed Communication

Authors: Jianchang Su, Yifan Zhang, and Wei Zhang

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract

Broadcasting and aggregation dominate the communication overhead in distributed systems, from machine learning training to data analytics. Current acceleration approaches require specialized hardware (RDMA) or dedicated resources (DPDK), limiting their deployment in commodity clouds. However, we present a counter-intuitive alternative: rather than bypassing the kernel, we move operations into it using eBPF. While this imposes severe constraints including no floating-point, limited memory, and stateless execution, we show these restrictions paradoxically drive innovative protocol designs that yield unexpected benefits. We introduce AggBox, which implements broadcast and aggregation operations entirely within eBPF’s constrained environment. Our key innovations include stateless group acknowledgments for reliability, edge quantization for floating-point aggregation using only integer arithmetic, and tail-call chains that create virtual memory beyond eBPF’s 512-byte stack limit. These designs emerge from and exploit the constraints rather than fighting them. AggBox achieves remarkable performance on commodity hardware: 84.5% reduction in broadcast latency, 43× speedup for MapReduce workloads, and 56.1% faster ML gradient aggregation, all without specialized NICs or dedicated cores. Beyond performance, our work demonstrates that constrained environments can drive fundamental innovation in protocol design, offering insights for future resource-limited and verified systems.

Cite as

Jianchang Su, Yifan Zhang, and Wei Zhang. In-Kernel Aggregation and Broadcast Acceleration for Distributed Communication. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{su_et_al:OASIcs.NINeS.2026.13,
  author =	{Su, Jianchang and Zhang, Yifan and Zhang, Wei},
  title =	{{In-Kernel Aggregation and Broadcast Acceleration for Distributed Communication}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{13:1--13:23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.13},
  URN =		{urn:nbn:de:0030-drops-255981},
  doi =		{10.4230/OASIcs.NINeS.2026.13},
  annote =	{Keywords: eBPF, distributed communication, broadcast, aggregation, in-kernel processing, XDP}
}

Search Results

Documents authored by Zhang, Wei

Optimal k-Secretary with Logarithmic Memory

Abstract

Cite as

In-Kernel Aggregation and Broadcast Acceleration for Distributed Communication

Abstract

Cite as

Thanks for your feedback!

Could not send message