An official website of the United States government
Since the mid-1980s it has been known that Byzantine Agreement can be solved with probability 1 asynchronously, even against an omniscient, computationally unbounded adversary that can adaptivelycorruptup tof < n/3parties. Moreover, the problem is insoluble withf ≥ n/3corruptions. However, Bracha’s [13] 1984 protocol (see also Ben-Or [8]) achievedf < n/3resilience at the cost ofexponentialexpected latency2Θ (n), a bound that hasneverbeen improved in this model withf = ⌊ (n-1)/3 ⌋corruptions. In this article, we prove that Byzantine Agreement in the asynchronous, full information model can be solved with probability 1 against an adaptive adversary that can corruptf < n/3parties, while incurring onlypolynomial latency with high probability. Our protocol follows an earlier polynomial latency protocol of King and Saia [33,34], which hadsuboptimalresilience, namelyf ≈ n/109 [33,34]. Resiliencef = (n-1)/3is uniquely difficult, as this is the point at which the influence of the Byzantine and honest players are of roughly equal strength. The core technical problem we solve is to design a collective coin-flipping protocol thateventuallylets us flip a coin with an unambiguous outcome. In the beginning, the influence of the Byzantine players is too powerful to overcome, and they can essentially fix the coin’s behavior at will. We guarantee that after just a polynomial number of executions of the coin-flipping protocol, either (a) the Byzantine players fail to fix the behavior of the coin (thereby ending the game) or (b) we can “blacklist” players such that the blacklisting rate for Byzantine players is at least as large as the blacklisting rate for good players. The blacklisting criterion is based on a simple statistical test offraud detection.
more »
« less
Irrigable measures for weighted irrigation plans
A model of irrigation network, where lower branches must be thicker in order to support the weight of the higher ones, was recently introduced in [7]. This leads to a countable family of ODEs, describing the thickness of every branch, solved by backward induction. The present paper determines what kind of measures can be irrigated with a finite weighted cost. Indeed, the boundedness of the cost depends on the dimension of the support of the irrigated measure, and also on the asymptotic properties of the ODE which determines the thickness of branches.
more »
« less
- Award ID(s):
- 1714237
- PAR ID:
- 10297275
- Date Published:
- Journal Name:
- Networks & Heterogeneous Media
- Volume:
- 16
- Issue:
- 3
- ISSN:
- 1556-181X
- Page Range / eLocation ID:
- 493
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Algorithms often have tunable parameters that impact performance metrics such as runtime and solution quality. For many algorithms used in practice, no parameter settings admit meaningful worst-case bounds, so the parameters are made available for the user to tune. Alternatively, parameters may be tuned implicitly within the proof of a worst-case approximation ratio or runtime bound. Worst-case instances, however, may be rare or nonexistent in practice. A growing body of research has demonstrated that a data-driven approach to parameter tuning can lead to significant improvements in performance. This approach uses atraining setof problem instances sampled from an unknown, application-specific distribution and returns a parameter setting with strong average performance on the training set. We provide techniques for derivinggeneralization guaranteesthat bound the difference between the algorithm’s average performance over the training set and its expected performance on the unknown distribution. Our results apply no matter how the parameters are tuned, be it via an automated or manual approach. The challenge is that for many types of algorithms, performance is a volatile function of the parameters: slightly perturbing the parameters can cause a large change in behavior. Prior research [e.g.,12,16,20,62] has proved generalization bounds by employing case-by-case analyses of greedy algorithms, clustering algorithms, integer programming algorithms, and selling mechanisms. We streamline these analyses with a general theorem that applies whenever an algorithm’s performance is a piecewise-constant, piecewise-linear, or—more generally—piecewise-structuredfunction of its parameters. Our results, which are tight up to logarithmic factors in the worst case, also imply novel bounds for configuring dynamic programming algorithms from computational biology.more » « less
-
Abstract ObjectivesDespite qualitative observations of wild primates pumping branches before leaping across gaps in the canopy, most studies have suggested that support compliance increases the energetic cost of arboreal leaping, thus limiting leaping performance. In this study, we quantified branch pumping behavior and tree swaying in wild primates to test the hypothesis that these behaviors improve leaping performance. Materials and MethodsWe recorded wild colobine monkeys crossing gaps in the canopy and quantitatively tracked the kinematics of both the monkey and the compliant support during behavioral sequences. We also empirically measured the compliance of a sample of locomotor supports in the monkeys' natural habitat, allowing us to quantify the resonant properties of substrates used during leaping. ResultsAnalyses of three recordings show that adult red colobus monkeys (Piliocolobus tephrosceles) use branch compliance to their advantage by actively pumping branches before leaping, augmenting their vertical velocity at take‐off. Quantitative modeling of branch resonance periods, based on empirical measurements of support compliance, suggests that monkeys specifically employed branch pumping on relatively thin branches with protracted periods of oscillation. Finally, an additional four recordings show that both red colobus and black and white colobus monkeys (Colobus guereza) utilize tree swaying to cross large gaps, augmenting horizontal velocity at take‐off. DiscussionThis deliberate branch manipulation to produce a mechanical effect for stronger propulsion is consistent with the framework of instrumental problem‐solving. To our knowledge, this is the first study of wild primates which quantitatively shows how compliant branches can be used advantageously to augment locomotor performance.more » « less
-
Human activities in urban areas disturb the natural landscape upon which they develop, disrupting pedogenic processes and ultimately limiting the ecosystem services urban soils provide. To better understand the impacts on and resiliency of soils in response to urban development, it is essential to understand the processes by which and degree to which soil physical and chemical properties are altered in urban systems. Here, we apply the source-tracing capabilities of Sr isotopes (87Sr/86Sr) to understand the impacts of urban processes on the composition of soils in eight watersheds in Austin, Texas. We evaluate natural and anthropogenic Sr sources in watersheds spanning a wide range of urbanization, comparing soils by variations in their natural (including mineralogy, thickness, soil type, and watershed) and anthropogenic (including irrigation, soil amendments, and fertilization) characteristics. A strong positive correlation between soil thickness and 87Sr/86Sr is observed among unirrigated soils (R2 = 0.83). In contrast, this relationship is not observed among irrigated soils (R2 = 0.004). 95 % of 42 irrigated soil samples have 87Sr/86Sr values approaching or within the range for municipal supply water. These results indicate soil interaction with municipal water through irrigation and/or water infrastructure leakage. Soils irrigated with municipal water have elevated 87Sr/86Sr values relative to unirrigated soils in seven of eight watersheds. We propose that original soil 87Sr/86Sr values are partially to completely reset by irrigation with municipal water via ion exchange processes. Our results demonstrate that in urban systems, Sr isotopes can serve as an environmental tracer to assess the overprint of urbanization on natural soil characteristics. In the Austin region, resetting of natural soil compositions via urban development is extensive, and the continued expansion of urban areas and irrigation systems may affect the ability of soils to retain nutrients, filter contaminants, and provide other ecosystem services that support environmental resilience.more » « less
-
One approach to understanding complex data is to study its shape through the lens of algebraic topology. While the early development of topological data analysis focused primarily on static data, in recent years, theoretical and applied studies have turned to data that varies in time. A time-varying collection of metric spaces as formed, for example, by a moving school of fish or flock of birds, can contain a vast amount of information. There is often a need to simplify or summarize the dynamic behavior. We provide an introduction to topological summaries of time-varying metric spaces including vineyards [19], crocker plots [55], and multiparameter rank functions [37]. We then introduce a new tool to summarize time-varying metric spaces: a crocker stack. Crocker stacks are convenient for visualization, amenable to machine learning, and satisfy a desirable continuity property which we prove. We demonstrate the utility of crocker stacks for a parameter identification task involving an influential model of biological aggregations [57]. Altogether, we aim to bring the broader applied mathematics community up-to-date on topological summaries of time-varying metric spaces.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.3934/nhm.2021014
