More Like this

1. Dynamic Race Detection with O(1) Samples

   https://doi.org/10.1145/3571238  

   Thokair, Mosaad Al ; Zhang, Minjian ; Mathur, Umang ; Viswanathan, Mahesh ( January 2023 , Proceedings of the ACM on Programming Languages)

   Happens before-based dynamic analysis is the go-to technique for detecting data races in large scale software projects due to the absence of false positive reports. However, such analyses are expensive since they employ expensive vector clock updates at each event, rendering them usable only for in-house testing. In this paper, we present a sampling-based, randomized race detector that processes onlyconstantly manyevents of the input trace even in the worst case. This is the firstsub-lineartime (i.e., running ino(n) time wherenis the length of the trace) dynamic race detection algorithm; previous sampling based approaches like run in linear time (i.e.,O(n)). Our algorithm is a property tester for -race detection — it is sound in that it never reports any false positive, and on traces that are far, with respect to hamming distance, from any race-free trace, the algorithm detects an -race with high probability. Our experimental evaluation of the algorithm and its comparison with state-of-the-art deterministic and sampling based race detectors shows that the algorithm does indeed have significantly low running time, and detects races quite often.

    

   more » « less
2. Optimal prediction of synchronization-preserving races

   https://doi.org/10.1145/3434317  

   Mathur, Umang ; Pavlogiannis, Andreas ; Viswanathan, Mahesh ( January 2021 , Proceedings of the ACM on Programming Languages)

   null (Ed.)

   Concurrent programs are notoriously hard to write correctly, as scheduling nondeterminism introduces subtle errors that are both hard to detect and to reproduce. The most common concurrency errors are (data) races, which occur when memory-conflicting actions are executed concurrently. Consequently, considerable effort has been made towards developing efficient techniques for race detection. The most common approach is dynamic race prediction: given an observed, race-free trace σ of a concurrent program, the task is to decide whether events of σ can be correctly reordered to a trace σ * that witnesses a race hidden in σ. In this work we introduce the notion of sync(hronization)-preserving races. A sync-preserving race occurs in σ when there is a witness σ * in which synchronization operations (e.g., acquisition and release of locks) appear in the same order as in σ. This is a broad definition that strictly subsumes the famous notion of happens-before races. Our main results are as follows. First, we develop a sound and complete algorithm for predicting sync-preserving races. For moderate values of parameters like the number of threads, the algorithm runs in Õ( N ) time and space, where N is the length of the trace σ. Second, we show that the problem has a Ω( N /log 2 N ) space lower bound, and thus our algorithm is essentially time and space optimal. Third, we show that predicting races with even just a single reversal of two sync operations is NP-complete and even W1-hard when parameterized by the number of threads. Thus, sync-preservation characterizes exactly the tractability boundary of race prediction, and our algorithm is nearly optimal for the tractable side. Our experiments show that our algorithm is fast in practice, while sync-preservation characterizes races often missed by state-of-the-art methods. 

   more » « less
3. Multiple solutions at the genomic level in response to selective breeding for high locomotor activity

   https://doi.org/10.1093/genetics/iyac165  

   Hillis, David A. ; Garland, Jr, Theodore ; Gleason, ed., J. ( October 2022 , Genetics)

   Replicate lines under uniform selection often evolve in different ways. Previously, analyses using whole-genome sequence data for individual mice (Mus musculus) from 4 replicate High Runner lines and 4 nonselected control lines demonstrated genomic regions that have responded consistently to selection for voluntary wheel-running behavior. Here, we ask whether the High Runner lines have evolved differently from each other, even though they reached selection limits at similar levels. We focus on 1 High Runner line (HR3) that became fixed for a mutation at a gene of major effect (Myh4Minimsc) that, in the homozygous condition, causes a 50% reduction in hindlimb muscle mass and many pleiotropic effects. We excluded HR3 from SNP analyses and identified 19 regions not consistently identified in analyses with all 4 lines. Repeating analyses while dropping each of the other High Runner lines identified 12, 8, and 6 such regions. (Of these 45 regions, 37 were unique.) These results suggest that each High Runner line indeed responded to selection somewhat uniquely, but also that HR3 is the most distinct. We then applied 2 additional analytical approaches when dropping HR3 only (based on haplotypes and nonstatistical tests involving fixation patterns). All 3 approaches identified 7 new regions (as compared with analyses using all 4 High Runner lines) that include genes associated with activity levels, dopamine signaling, hippocampus morphology, heart size, and body size, all of which differ between High Runner and control lines. Our results illustrate how multiple solutions and “private” alleles can obscure general signatures of selection involving “public” alleles.

    

   more » « less
4. Planning Coordinated Event Observation for Structured Narratives

   https://doi.org/10.1109/ICRA.2019.8794450  

   Shell, Dylan A. ; Huang, Li ; Becker, Aaron T. ; O'Kane, Jason M. ( May 2019 , Planning Coordinated Event Observation for Structured Narratives)

   This paper addresses the problem of using autonomous robots to record events that obey narrative structure. The work is motivated by a vision of robot teams that can, for example, produce individualized highlight videos for each runner in a large-scale road race such as a marathon. We introduce a method for specifying the desired structure as a function that describes how well the captured events can be used to produce an output that meets the specification. This function is specified in a compact, legible form similar to a weighted finite automaton. Then we describe a planner that uses simple predictions of future events to coordinate the robots' efforts to capture the most important events, as determined by the specification. We describe an implementation of this approach, and demonstrate its effectiveness in a simulated race scenario both in simulation and in a hardware testbed. 

   more » « less
5. Conditioned place preference for cocaine and methylphenidate in female mice from lines selectively bred for high voluntary wheel‐running behavior

   https://doi.org/10.1111/gbb.12700  

   Schmill, Margaret P. ; Cadney, Marcell D. ; Thompson, Zoe ; Hiramatsu, Layla ; Albuquerque, Ralph L. ; McNamara, Monica P. ; Castro, Alberto A. ; Kay, Jarren C. ; Buenaventura, Darrius G. ; Ramirez, Jocelyn L. ; et al ( September 2020 , Genes, Brain and Behavior)

   Behavioral addictions can come in many forms, including overeating, gambling and overexercising. All addictions share a common mechanism involving activation of the natural reward circuit and reinforcement learning, but the extent to which motivation for natural and drug rewards share similar neurogenetic mechanisms remains unknown. A unique mouse genetic model in which four replicate lines of female mice were selectively bred (>76 generations) for high voluntary wheel running (High Runner or HR lines) alongside four non‐selected control (C) lines were used to test the hypothesis that high motivation for exercise is associated with greater reward for cocaine (20 mg/kg) and methylphenidate (10 mg/kg) using the conditioned place preference (CPP) test. HR mice run ~three times as many revolutions/day as C mice, but the extent to which they have increased motivation for other rewards is unknown. Both HR and C mice displayed significant CPP for cocaine and methylphenidate, but with no statistical difference between linetypes for either drug. Taken together, results suggest that selective breeding for increased voluntary running has modified the reward circuit in the brain in a way that increases motivation for running without affecting cocaine or methylphenidate reward.

    

   more » « less