Science Research & Publications

Permanent URI for this collection


Recent Submissions

Now showing 1 - 5 of 1832
  • Item
    Open Access
    Strongly Linearizable LL/SC from CAS
    (ACM, 2024) Naderi-Semiromi, Fatemeh; Woelfel, Philipp
    We present an efficient strongly linearizable implementation of the load-linked/store-conditional (LL/SC) primitive from compare-and-swap (CAS) objects. Our algorithm has constant step complexity, and uses a bounded number of CAS objects and registers that can each store O (log n) bits, where n is the number of processes. All previously known wait-free LL/SC algorithms are either not strongly linearizable, or use objects of unbounded size.
  • Item
    Open Access
    Faster Randomized Repeated Choice and DCAS
    (ACM, 2024) Bencivenga, Dante; Giakkoupis, George; Woelfel, Philipp
    At STOC 2021, Giakkoupis, Giv, and Woelfel, presented an efficient randomized implementation of Double Compare-And-Swap (DCAS) from Compare-And-Swap (CAS) objects. DCAS is a useful and fundamental synchronization primitive for shared memory systems, which, contrary to CAS, is not available in hardware. The DCAS algorithm has O(logn) expected amortized step complexity against an oblivious adversary, where nn is the number of processes in the system. The bottleneck of this algorithm is a building block, introduced in the same paper: A repeated choice (RC) object, which allows processes to propose values, and later agree on (and “lock in”) one of the proposed values, which is roughly uniformly distributed among the “recently” proposed ones. The object can then be unlocked, and the process be repeated. The RC implementation introduced by Giakkoupis et al. has step complexity O(logn). In this paper, we present a more efficient RC algorithm, with similar probabilistic guarantees, but expected step complexity O(loglogn). We then show how this improved RC object can be used to achieve an exponential improvement in the expected amortized step complexity of DCAS.
  • Item
    Flameless operating mode for improved multiple flame photometric detection in gas chromatography
    (Springer Nature, 2024-04-25) Thurbide, Kevin; Nguyen, Bao
    A novel fameless operating mode is introduced, which improves the response of a multiple fame photometric detector (mFPD). The mFPD normally has analyte travel through 4 ‘worker’ fames in series before entering a fnal ‘analytical’ fame where its emission is monitored. Here, it is found that when the analytical fame is not ignited, background luminescence is reduced over 30 times and the strong analyte chemiluminescence of the worker fames can be made to extend a large distance (~10 fame widths) into the analytical fame region where it is detected. This occurs for phosphorous (HPO*), quadratic sulfur (S2*), and linear sulfur (HSO*) emission. Conversely, carbon emission resides inside the worker fames and yields a small negative signal. As a result, very good selectivity over carbon is observed, and improved minimum detectable limits (MDL) of 4 pg S/s (S2*) and 0.3 pg P/s (HPO*) are obtained, which are up to 20 times lower than previous values reported for the mFPD. Further, linear sulfur (HSO*) yields an MDL of 6 pg S/s, which is over 3 times lower than values reported for other FPDs. Due to the worker fames present in this mode, other benefts of regular mFPD operation are maintained, like uniform analyte response and large quenching resistance. In application, a trace benzothiophene analyte is readily detected within a concentrated diesel fuel matrix in the fameless mFPD mode, while no response is observed in the conventional FPD mode. Results indicate that this fameless operating mode is advantageous for sulfur and phosphorous analysis.
  • Item
    Open Access
    Better Little People Pictures: Generative Creation of Demographically Diverse Anthropographics
    (ACM, 2024-05-11) Dhawka, Priya; Perera, Lauren; Willett, Wesley
    We explore the potential of generative AI text-to-image models to help designers efficiently craft unique, representative, and demographically diverse anthropographics that visualize data about people. Currently, creating data-driven iconic images to represent individuals in a dataset often requires considerable design effort. Generative text-to-image models can streamline the process of creating these images, but risk perpetuating designer biases in addition to stereotypes latent in the models. In response, we outline a conceptual workflow for crafting anthropographic assets for visualizations, highlighting possible sources of risk and bias as well as opportunities for reflection and refinement by a human designer. Using an implementation of this workflow with Stable Diffusion and Google Colab, we illustrate a variety of new anthropographic designs that showcase the visual expressiveness and scalability of these generative approaches. Based on our experiments, we also identify challenges and research opportunities for new AI-enabled anthropographic visualization tools.
  • Item
    Open Access
    Input Visualization: Collecting and Modifying Data with Visual Representations
    (ACM, 2024-05-11) Bressa, Nathalie; Louis, Jordan; Willett, Wesley; Huron, Samuel
    We examine input visualizations, visual representations that are designed to collect (and represent) new data rather than encode preexisting datasets. Information visualization is commonly used to reveal insights and stories within existing data. As a result, most contemporary visualization approaches assume existing datasets as the starting point for design, through which that data is mapped to visual encodings. Meanwhile, the implications of visualizations as inputs and as data sources have received little attention—despite the existence of visual and physical examples stretching back centuries. In this paper, we present a design space of 50 input visualizations analyzing their visual representation, data, artifact, context, and input. Based on this, we identify input modalities, purposes of input visualizations, and a set of design considerations. Finally, we discuss the relationship between input visualization and traditional visualization design and suggest opportunities for future research to better understand these visual representations and their potential.