Search Results

Documents authored by Banasik, Dominick


Document
Brief Announcement
Brief Announcement: Initialization with Exponentially Fewer Bits

Authors: Dominick Banasik, Varsha Dani, and Thomas P. Hayes

Published in: LIPIcs, Volume 397, 40th International Symposium on Distributed Computing (DISC 2026)


Abstract
One of the most fundamental challenges in radio networks is avoiding collisions during communication. This is especially important in single-hop radio networks, where only a single processor is able to transmit at a time. To overcome this obstacle, the processors, which we assume are indistinguishable to begin with, solve initialization. That is, they each get assigned distinct numbers from 1 to n. Because collisions occur if two or more processors transmit simultaneously, solving initialization requires Ω(n) rounds, and O(n) round protocols have long been known. These networks are often made up of battery-powered devices, meaning energy is a crucial resource. We therefore consider a model in which nodes are allowed to sleep to save energy at the expense of communicating. Previous work by Nakano and Olariu [Nakano and Olariu, 2000] showed that initialization can be solved in O(log log n) energy using O(log n)-bit messages. We first show that their energy bound is optimal, giving a lower bound that Ω(log log n) sends are needed by any initialization protocol whose round complexity is nearly quasilinear in n. In the more restrictive setting without sender- or receiver-side collision detection (no-CD Model), we show that we can initialize all but a small fraction f of nodes with an energy complexity that depends only on f. As a corollary, we obtain the first constant-energy algorithm for initializing 0.999n nodes. We then consider the setting in which messages are limited to single bits. In this case, we present a series of improvements that result in an algorithm in which each node sends and receives up to O(log log n) bits - exponentially fewer than all previous work. Ultimately, we show that this can be done in O(n) single-bit rounds, with a worst-case bit complexity of O(log log n) and a node-averaged bit complexity of O(1).

Cite as

Dominick Banasik, Varsha Dani, and Thomas P. Hayes. Brief Announcement: Initialization with Exponentially Fewer Bits. In 40th International Symposium on Distributed Computing (DISC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 397, pp. 65:1-65:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)


Copy BibTex To Clipboard

@InProceedings{banasik_et_al:LIPIcs.DISC.2026.65,
  author =	{Banasik, Dominick and Dani, Varsha and Hayes, Thomas P.},
  title =	{{Brief Announcement: Initialization with Exponentially Fewer Bits}},
  booktitle =	{40th International Symposium on Distributed Computing (DISC 2026)},
  pages =	{65:1--65:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-454-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{397},
  editor =	{Moses Jr., William K. and Censor-Hillel, Keren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2026.65},
  URN =		{urn:nbn:de:0030-drops-281713},
  doi =		{10.4230/LIPIcs.DISC.2026.65},
  annote =	{Keywords: Distributed Computing, Energy Complexity, Radio Networks, Initialization}
}
Document
Energy-Efficient Maximal Independent Sets in Radio Networks

Authors: Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)


Abstract
The maximal independent set (MIS) is one of the most fundamental problems in distributed computing, and it has been studied intensively for over four decades. This paper focuses on the MIS problem in the radio network model, a standard model widely used to model wireless networks, particularly ad hoc wireless and sensor networks. Energy is a premium resource in these networks, which are typically battery-powered. Hence, designing distributed algorithms that use as little energy as possible is crucial. We use the well-established energy model where a node can be sleeping or awake in a round, and only the awake rounds (when it can send or listen) determine the energy complexity of the algorithm, which we want to minimize. We present new, more energy-efficient MIS algorithms in radio networks with arbitrary and unknown graph topology. We present algorithms for two popular variants of the radio model - with collision detection (CD) and without collision detection (no-CD). Specifically, we obtain the following results: 1) CD model: We present a randomized distributed MIS algorithm with energy complexity O(log n), round complexity O(log² n), and failure probability 1 / poly(n), where n is the network size. We show that our energy complexity is optimal by showing a matching Ω(log n) lower bound. 2) no-CD model: In the more challenging no-CD model, we present a randomized distributed MIS algorithm with energy complexity O(log²n log log n), round complexity O(log³ n log Δ), and failure probability 1 / poly(n). The energy complexity of our algorithm is significantly lower than the round (and energy) complexity of O(log³ n) of the best known distributed MIS algorithm of Davies [PODC 2023] for arbitrary graph topology.

Cite as

Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan. Energy-Efficient Maximal Independent Sets in Radio Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 14:1-14:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{banasik_et_al:LIPIcs.DISC.2025.14,
  author =	{Banasik, Dominick and Dani, Varsha and Dufoulon, Fabien and Gupta, Aayush and Hayes, Thomas P. and Pandurangan, Gopal},
  title =	{{Energy-Efficient Maximal Independent Sets in Radio Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{14:1--14:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.14},
  URN =		{urn:nbn:de:0030-drops-248311},
  doi =		{10.4230/LIPIcs.DISC.2025.14},
  annote =	{Keywords: Distributed Computing, Energy Complexity, Sleeping Model, Radio Networks, Maximal Independent Set}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail