An official website of the United States government
This paper proposes a feasibility-optimal decentralized algorithm for real-time wireless ad hoc networks, where a strict deadline is imposed for each packet. While centralized scheduling algorithms provide provably optimal theoretical guarantees, they may not be practical in many settings, such as industrial networked control systems. Therefore, it is of great importance to design an algorithm that achieves feasibility optimality in a decentralized manner. To design a decentralized algorithm, we leverage two widely-used functions of wireless devices: carrier sensing and backoff timers. Different from the conventional approach, the proposed algorithm utilizes a collision-free backoff scheme to enforce the transmission priority of different links. This design obviates the capacity loss due to collision with quantifiably small backoff overhead. The algorithm is fully decentralized in the sense that every link only needs to know its own priority, and links contend for priorities only through carrier sensing. We prove that the proposed algorithm is feasibility-optimal. NS-3 simulation results show that the proposed algorithm indeed performs as well as the feasibility-optimal centralized algorithm. Moreover, the results also show that the proposed algorithm converges to optimality very fast.
more »
« less
Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds
Backoff algorithms are used in many distributed systems where multiple devices contend for a shared resource. For the classic balls-into-bins problem, the number of singletons - those bins with a single ball - is important to the analysis of several backoff algorithms; however, existing analyses employ advanced probabilistic tools to obtain concentration bounds. Here, we show that standard Chernoff bounds can be used instead, and the simplicity of this approach is illustrated by re-analyzing some well-known backoff algorithms.
more »
« less
- Award ID(s):
- 1816076
- PAR ID:
- 10229838
- Editor(s):
- Farach-Colton, Martin; Prencipe, Giuseppe; Uehara, Ryuhei
- Date Published:
- Journal Name:
- 10th International Conference on Fun with Algorithms (FUN 2021)
- Volume:
- 157
- ISSN:
- 1868-8969
- Page Range / eLocation ID:
- 24:1-24:19
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper presents new achievability bounds on the maximal achievable rate of variable-length stop-feedback (VLSF) codes operating over a binary erasure channel (BEC) at a fixed message size M=2^k . We provide bounds for two cases: The first case considers VLSF codes with possibly infinite decoding times and zero error probability. The second case limits the maximum (finite) number of decoding times and specifies a maximum tolerable probability of error. Both new achievability bounds are proved by constructing a new VLSF code that employs systematic transmission of the first k message bits followed by random linear fountain parity bits decoded with a rank decoder. For VLSF codes with infinite decoding times, our new bound outperforms the state-of-the-art result for BEC by Devassy et al. in 2016. We show that the backoff from capacity reduces to zero as the erasure probability decreases, thus giving a negative answer to the open question Devassy et al. posed on whether the 23.4% backoff to capacity at k=3 is fundamental to all BECs. For VLSF codes with finite decoding times, numerical evaluations show that the systematic transmission followed by random linear fountain coding performs better than random linear coding in terms of achievable rates.more » « less
-
The use of an active load has been recently proposed for the realization of power-efficient broadband balanced amplifiers. The application of an active load to a dual-input Chireix amplifier is investigated in this paper for the purpose of increasing their bandwidth. An embedding device model is used to established the optimal non-Foster loads required for both the transistors to remain operating in class F as the operating frequency deviates from the center frequency. Given the transistors must operate with a constant voltage swing between backoff and peak, it is found necessary for the two transistors to operate with different load impedances as the frequency varies. The required load impedance and outphasing angles for the Chireix operation are obtained using a generalized eigenvalue problem using the Y-matrix of the Chireix combiner loaded with the active load. It is verified that using an active load, it is possible to maintain a high efficiency not only at peak power but also under various backoff power levels over a bandwidth of 1 GHz. Within a 200 MHz bandwidth, the PA is predicted to be able to maintain an efficiency larger than 79% for 6 dB backoff. Further work is required to experimentally validate the proposed technique.more » « less
-
We study the fundamental problems of identity testing (goodness of fit), and closeness testing (two sample test) of distributions over k elements, under differential privacy. While the problems have a long history in statistics, finite sample bounds for these problems have only been established recently. In this work, we derive upper and lower bounds on the sample complexity of both the problems under (epsilon, delta)-differential privacy. We provide sample optimal algorithms for identity testing problem for all parameter ranges, and the first results for closeness testing. Our closeness testing bounds are optimal in the sparse regime where the number of samples is at most k. Our upper bounds are obtained by privatizing non-private estimators for these problems. The non-private estimators are chosen to have small sensitivity. We propose a general framework to establish lower bounds on the sample complexity of statistical tasks under differential privacy. We show a bound on di erentially private algorithms in terms of a coupling between the two hypothesis classes we aim to test. By carefully constructing chosen priors over the hypothesis classes, and using Le Cam’s two point theorem we provide a general mechanism for proving lower bounds. We believe that the framework can be used to obtain strong lower bounds for other statistical tasks under privacy.more » « less
-
We propose a stochastic variational inference algorithm for training large-scale Bayesian networks, where noisy-OR conditional distributions are used to capture higher-order relationships. One application is to the learning of hierarchical topic models for text data. While previous work has focused on two-layer networks popular in applications like medical diagnosis, we develop scalable algorithms for deep networks that capture a multi-level hierarchy of interactions. Our key innovation is a family of constrained variational bounds that only explicitly optimize posterior probabilities for the sub-graph of topics most related to the sparse observations in a given document. These constrained bounds have comparable accuracy but dramatically reduced computational cost. Using stochastic gradient updates based on our variational bounds, we learn noisy-OR Bayesian networks orders of magnitude faster than was possible with prior Monte Carlo learning algorithms, and provide a new tool for understanding large-scale binary data.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.4230/LIPIcs.FUN.2021.24
