More Like this

1. On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols

   https://doi.org/10.1007/978-3-031-74580-5_8  

   Kuschner, Jordan; Shashwat, Yugarshi; Yadav, Sarthak; Chrobak, Marek (December 2024, Springer Nature Switzerland)

   Bramas, Quentin; Casteigts, Arnaud; Meeks, Kitty (Ed.)

   Selective families of sets, or selectors, are combinatorial tools used to “isolate” individual members of sets from some set family. Given a set X and an element x ∈ X, to isolate x from X, at least one of the sets in the selector must intersect X on exactly x. We study (k,N)-permutation selectors which have the property that they can isolate each element of each k-element subset of {0, 1, ..., N − 1} in each possible order. These selectors can be used in protocols for ad-hoc radio networks to more efficiently disseminate informa- tion along multiple hops. In 2004, Gasieniec, Radzik and Xin gave a construc- tion of a (k, N )-permutation selector of size O(k2 log3 N ). This paper improves this by providing a probabilistic construction of a (k, N )-permutation selector of size O(k2 log N ). Remarkably, this matches the asymptotic bound for standard strong (k,N)-selectors, that isolate each element of each set of size k, but with no restriction on the order. We then show that the use of our (k, N )-permutation selector improves the best running time for gossiping in ad-hoc radio networks by a poly-logarithmic factor. 

   more » « less
2. A Gossiping Protocol for Sparse Ad-Hoc Radio Networks

   Wu, Chao; Chrobak, Marek (September 2026, ISAAC: International Symposium on Algorithms and Computation, 2026)

   We study the problem of gossiping (all-to-all information exchange) in ad-hoc radio networks. Such a network is represented by a strongly-connected directed graph with n vertices, whose topology is initially unknown to the protocol. In 2004, Gasieniec, Radzik, and Xin [19] gave an ˜O(n4/3)-time deterministic protocol for this problem, and closing the gap between their upper bound and the ˜Ω(n) lower bound on the time complexity of gossiping remains a central open problem. We develop a deterministic protocol for gossiping in ad-hoc radio networks that achieves running time ˜O((mn)3/5) for directed graphs with at most m edges. Our protocol improves on the ˜O(n4/3) bound when m = O(nc), for c < 11 9 . We also present an ˜O(∆1/2n)-time gossiping protocol for ∆-regular graphs 

   more » « less
3. Engineering Tunneling Selector to Achieve High Non-linearity for 1S1R Integration

   https://doi.org/10.3389/fnano.2021.656026  

   Upadhyay, Navnidhi K.; Blum, Thomas; Maksymovych, Petro; Lavrik, Nickolay V.; Davila, Noraica; Katine, Jordan A.; Ievlev, A. V.; Chi, Miaofang; Xia, Qiangfei; Yang, J. Joshua (April 2021, Frontiers in Nanotechnology)

   Memristor devices have been extensively studied as one of the most promising technologies for next-generation non-volatile memory. However, for the memristor devices to have a real technological impact, they must be densely packed in a large crossbar array (CBA) exceeding Gigabytes in size. Devising a selector device that is CMOS compatible, 3D stackable, and has a high non-linearity (NL) and great endurance is a crucial enabling ingredient to reach this goal. Tunneling based selectors are very promising in these aspects, but the mediocre NL value limits their applications in large passive crossbar arrays. In this work, we demonstrated a trilayer tunneling selector based on the Ge/Pt/TaN 1+x /Ta 2 O 5 /TaN 1+x /Pd layers that could achieve a NL of 3 × 10 5 , which is the highest NL achieved using a tunnel selector so far. The record-high tunneling NL is partially attributed to the bottom electrode's ultra-smoothness (BE) induced by a Ge/Pt layer. We further demonstrated the feasibility of 1S1R (1-selector 1-resistor) integration by vertically integrating a Pd/Ta 2 O 5 /Ru based memristor on top of the proposed selector. 

   more » « less
4. Energy-Efficient Maximal Independent Sets in Radio Networks

   https://doi.org/10.4230/lipics.disc.2025.14  

   Banasik, Dominick; Dani, Varsha; Dufoulon, Fabien; Gupta, Aayush; Hayes, Thomas P; Pandurangan, Gopal (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Kowalski, Dariusz R (Ed.)

   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. 

   more » « less
5. One Hop Greedy Permutations

   Sheehy, Donald R. (January 2020, Proceedings of the 32nd Canadian Conference on Computational Geometry)

   Keil, Mark; Mondal, Debajyoti (Ed.)

   We adapt and generalize a heuristic for k-center clustering to the permutation case, where every pre x of the ordering is a guaranteed approximate solution. The one-hop greedy permutations work by choosing at each step the farthest unchosen point and then looking in its local neighborhood for a point that covers the most points at a certain scale. This balances the competing demands of reducing the coverage radius and also covering as many points as possible. This idea first appeared in the work of Garcia-Diaz et al. and their algorithm required O(n2 log n) time for a fi xed k (i.e. not the whole permutation). We show how to use geometric data structures to approximate the entire permutation in O(n log D
   ) time for metrics sets with spread D. Notably, this running time is asymptotically the same as the running time for computing the ordinary greedy permutation. 

   more » « less