Abstract

Abstract

Abstract
The notion of a difunction was introduced by Jacques Riguet in 1948. Since then it has played a prominent role in database theory, type theory, program specification and process theory. The theory of difunctions is, however, less known in computing than it perhaps should be. The main purpose of the current paper is to give an account of difunction theory in relation algebra, with the aim of making the topic more mainstream.As is common with many important concepts, there are several different but equivalent characterisations of difunctionality, each with its own strength and practical significance. This paper compares different proofs of the equivalence of the characterisations. A well-known property is that a difunction is a set of completely disjoint rectangles. This property suggests the introduction of the (general) notion of the core of a relation; we use this notion to give a novel and, we believe, illuminating characterisation of difunctionality as a bijection between the classes of certain partial equivalence relations.& COPY; 2023 The Authors. Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

Abstract
For the average programmer, adjunctions are (if at all known) more respected than loved. At best, they are regarded as an algebraic device of theoretical interest only, not useful in common practice. This paper is aimed at showing the opposite: that adjunctions underlie most of the work we do as programmers, in particular those using the functional paradigm. However, functions alone are not sufficient to express the whole spectrum of programming, with its dichotomy between specifications—what is (often vaguely) required—and implementations—how what is required is (hopefully well) implemented. For this, one needs to extend functions to relations. Inspired by the pioneering work of Ralf Hinze on “adjoint (un)folds”, the core of the so-called (relational) Algebra of Programming is shown in this paper to arise from adjunctions. Moreover, the paper also shows how to calculate recursive programs from specifications expressed by Galois connections—a special kind of adjunction. Because Galois connections are easier to understand than adjunctions in general, the paper adopts a tutorial style, starting from the former and leading to the latter (a path usually not followed in the literature). The main aim is to reconcile the functional programming community with a concept that is central to software design as a whole, but rarely accepted as such. © 2023, Springer Nature Switzerland AG.

Abstract
Performance of transactional systems is degraded by update hotspots as conflicts lead to waiting and wasted work. This is particularly challenging in emerging large-scale database systems, as latency increases the probability of conflicts, state-of-the-art lock-based mitigations are not available, and most alternatives provide only weak consistency and cannot enforce lower bound invariants. We address this challenge with Multi-Record Values (MRVs), a technique that can be layered on existing database systems and that uses randomization to split and access numeric values in multiple records such that the probability of conflict can be made arbitrarily small. The only coordination needed is the underlying transactional system, meaning it retains existing isolation guarantees. The proposal is tested on five different systems ranging from DBx1000 (scale-up) to MySQL GR and a cloud-native NewSQL system (scale-out). The experiments explore design and configuration trade-offs and, with the TPC-C and STAMP Vacation benchmarks, demonstrate improved throughput and reduced abort rates when compared to alternatives.

Abstract
Automatic grading based on unit tests is a key feature of massive open online courses (MOOC) on programming, as it allows instant feedback to students and enables courses to scale up. This technique works well for sequential programs, by checking outputs against a sample of inputs, but unfortunately it is not adequate for detecting races and deadlocks, which precludes its use for concurrent programming, a key subject in parallel and distributed computing courses. In this paper we provide a hands-on evaluation of verification and testing tools for concurrent programs, collecting a precise set of requirements, and describing to what extent they can or can not be used for this purpose. Our conclusion is that automatic grading of concurrent programming exercises remains an open challenge.