skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Communication cost of consensus for nodes with limited memory
Motivated by applications in wireless networks and the Internet of Things, we consider a model of n nodes trying to reach consensus with high probability on their majority bit. Each node i is assigned a bit at time 0 and is a finite automaton with m bits of memory (i.e., 2 m states) and a Poisson clock. When the clock of i rings, i can choose to communicate and is then matched to a uniformly chosen node j. The nodes j and i may update their states based on the state of the other node. Previous work has focused on minimizing the time to consensus and the probability of error, while our goal is minimizing the number of communications. We show that, when m > 3 log log log ( n ) , consensus can be reached with linear communication cost, but this is impossible if m < log log log ( n ) . A key step is to distinguish when nodes can become aware of knowing the majority bit and stop communicating. We show that this is impossible if their memory is too low.  more » « less
Award ID(s):
1705007
PAR ID:
10137950
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
Proceedings of the National Academy of Sciences
Date Published:
Journal Name:
Proceedings of the National Academy of Sciences
Volume:
117
Issue:
11
ISSN:
0027-8424
Page Range / eLocation ID:
p. 5624-5630
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract We analyze an optical atomic clock using two-photon 5 S 1 / 2 4 D J transitions in rubidium. Four one- and two-color excitation schemes to probe the 4 D 3 / 2 and 4 D 5 / 2 fine-structure states are considered in detail. We compare key characteristics of Rb 4 D J and 5 D 5 / 2 two-photon clocks. The 4 D J clock features a high signal-to-noise ratio due to two-photon decay at favorable wavelengths, low dc electric and magnetic susceptibilities, and minimal black-body shifts. Ac Stark shifts from the clock interrogation lasers are compensated by two-color Rabi-frequency matching. We identify a ‘magic’ wavelength near 1060 nm, which allows for in-trap, Doppler-free clock-transition interrogation with lattice-trapped cold atoms. From our analysis of clock statistics and systematics, we project a quantum-noise-limited relative clock stability at the 10 13 / τ ( s ) -level, with integration timeτin seconds, and a relative accuracy of 10 13 . We describe a potential architecture for implementing the proposed clock using a single telecom clock laser at 1550 nm, which is conducive to optical communication and long-distance clock comparisons. Our work could be of interest in efforts to realize small and portable Rb clocks and in high-precision measurements of atomic properties of Rb 4 D J -states. 
    more » « less
  2. Abstract This paper presents a newly established sample of 103 unique galaxies or galaxy groups at 0.4 ≲z≲ 0.7 from the Cosmic Ultraviolet Baryon Survey (CUBS) for studying the warm-hot circumgalactic medium (CGM) probed by both Oviand Neviiiabsorption. The galaxies and associated neighbors are identified at <1 physical Mpc from the sightlines toward 15 CUBS QSOs atzQSO≳ 0.8. A total of 30 galaxies or galaxy groups exhibit associated Oviλλ1031, 1037 doublet absorption within a line-of-sight velocity interval of ±250 km s−1, while the rest show no trace of Ovito a detection limit of log N OVI / cm 2 13.7 . Meanwhile, only five galaxies or galaxy groups exhibit the Neviiiλλ770, 780 doublet absorption, down to a limiting column density of log N NeVIII / cm 2 14.0 . These Ovi- and Neviii-bearing halos reside in different galaxy environments with stellar masses ranging from log M star / M 8 to ≈11.5. The warm-hot CGM around galaxies of different stellar masses and star formation rates exhibits different spatial profiles and kinematics. In particular, star-forming galaxies with log M star / M 9 11 show a significant concentration of metal-enriched warm-hot CGM within the virial radius, while massive quiescent galaxies exhibit flatter radial profiles of both column densities and covering fractions. In addition, the velocity dispersion of Oviabsorption is broad withσυ> 40 km s−1for galaxies of log M star / M > 9 within the virial radius, suggesting a more dynamic warm-hot halo around these galaxies. Finally, the warm-hot CGM probed by Oviand Neviiiis suggested to be the dominant phase in sub-L* galaxies with log M star / M 9 10 based on their high ionization fractions in the CGM. 
    more » « less
  3. Abstract We studyℓnorms ofℓ2-normalized eigenfunctions of quantum cat maps. For maps with short quantum periods (constructed by Bonechi and de Biévre in F Bonechi and S De Bièvre (2000,Communications in Mathematical Physics,211, 659–686)) we show that there exists a sequence of eigenfunctionsuwith u log N 1 / 2 . For general eigenfunctions we show the upper bound u log N 1 / 2 . Here the semiclassical parameter is h = 2 π N 1 . Our upper bound is analogous to the one proved by Bérard in P Bérard (1977,Mathematische Zeitschrift,155, 249-276) for compact Riemannian manifolds without conjugate points. 
    more » « less
  4. Abstract A test of lepton flavor universality in B ± K ± μ + μ and B ± K ± e + e decays, as well as a measurement of differential and integrated branching fractions of a nonresonant B ± K ± μ + μ decay are presented. The analysis is made possible by a dedicated data set of proton-proton collisions at s = 13 TeV recorded in 2018, by the CMS experiment at the LHC, using a special high-rate data stream designed for collecting about 10 billion unbiased b hadron decays. The ratio of the branching fractions B ( B ± K ± μ + μ ) to B ( B ± K ± e + e ) is determined from the measured double ratio R ( K ) of these decays to the respective branching fractions of the B ± J / ψ K ± with J / ψ μ + μ and e + e decays, which allow for significant cancellation of systematic uncertainties. The ratio R ( K ) is measured in the range 1.1 < q 2 < 6.0 GeV 2 , whereqis the invariant mass of the lepton pair, and is found to be R ( K ) = 0.78 0.23 + 0.47 , in agreement with the standard model expectation R ( K ) 1 . This measurement is limited by the statistical precision of the electron channel. The integrated branching fraction in the sameq2range, B ( B ± K ± μ + μ ) = ( 12.42 ± 0.68 ) × 10 8 , is consistent with the present world-average value and has a comparable precision. 
    more » « less
  5. We report results of large-scale ground-state density matrix renormalization group (DMRG) calculations on t- t -J cylinders with circumferences 6 and 8. We determine a rough phase diagram that appears to approximate the two-dimensional (2D) system. While for many properties, positive and negative t values ( t / t = ± 0.2 ) appear to correspond to electron- and hole-doped cuprate systems, respectively, the behavior of superconductivity itself shows an inconsistency between the model and the materials. The t < 0 (hole-doped) region shows antiferromagnetism limited to very low doping, stripes more generally, and the familiar Fermi surface of the hole-doped cuprates. However, we find t < 0 strongly suppresses superconductivity. The t > 0 (electron-doped) region shows the expected circular Fermi pocket of holes around the ( π , π ) point and a broad low-doped region of coexisting antiferromagnetism and d-wave pairing with a triplet p component at wavevector ( π , π ) induced by the antiferromagnetism and d-wave pairing. The pairing for the electron low-doped system with t > 0 is strong and unambiguous in the DMRG simulations. At larger doping another broad region with stripes in addition to weaker d-wave pairing and striped p-wave pairing appears. In a small doping region near x = 0.08 for t 0.2 , we find an unconventional type of stripe involving unpaired holes located predominantly on chains spaced three lattice spacings apart. The undoped two-leg ladder regions in between mimic the short-ranged spin correlations seen in two-leg Heisenberg ladders. 
    more » « less