Operating Systems

A cool and practical alternative to traditional hash tables

Algorithms for creating indexes for very large tables without quiescing updates

As relational DBMSs become more and more popular and as organizations grow, the sizes of individual tables are increasing dramatically. Unfortunately, current DBMSs do not allow updates to be performed on a table while an index (e.g., a B+-tree) is b...

A Read-Copy Update based parallel server for distributed crowd simulations

Control Chart Tests Based on Geometric Moving Averages

A geometrical moving average gives the most recent observation the greatest weight, and all previous observations weights decreasing in geometric progression from the most recent back to the first. A graphical procedure for generating geometric movin...

Cuckoo hashing.

DNS Cache Poisoning Attack Reloaded: Revolutions with Side Channels

In this paper, we report a series of flaws in the software stack that leads to a strong revival of DNS cache poisoning --- a classic attack which is mitigated in practice with simple and effective randomization-based defenses such as randomized sourc...

Efficient software implementations of modular exponentiation

Linear Hashing: A New Tool for File and Table Addressing.

AbstractPolyhydroxyethers were synthesized from monoalkali metal salts of diphenols and 1‐halo‐2,3‐epoxyalkanes in a one‐step reaction in dipolar, aprotic solvents as reaction media. They were also synthesized from alkali metal salts of diphenols, di...

Linear-time Temporal Logic guided Greybox Fuzzing

Software model checking as well as runtime verification are verification techniques which are widely used for checking temporal properties of software systems. Even though they are property verification techniques, their common usage in practice is i...

NetSpectre: Read Arbitrary Memory over Network

In this paper, we present NetSpectre, a generic remote Spectre variant 1 attack. For this purpose, we demonstrate the first access-driven remote Evict+Reload cache attack over network, leaking 15 bits per hour. Beyond retrofitting existing attacks to...

On a Real-Time Scheduling Problem

We study the problem of scheduling periodic-time-critical tasks on multiprocessor computing systems. A periodic-time-critical task consists of an infinite number of requests, each of which has a prescribed deadline. The scheduling problem is to speci...

Performance of memory reclamation for lockless synchronization

Rank-Balanced Trees

Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But th...

Rational Chebyshev approximations for the inverse of the error function

This report presents near-minimax rational approximations for the inverse of the error function inverf x, for 0 ⩽ x ⩽ 1 − 10 − 10000 0 \leqslant x \leqslant 1 - {10^{ - 10000}} , with relative errors ranging down to 10 − 23 {10^{ - 23}} . An asymptot...

Recommendation for Key Management - Part 1 General

3541 et seq., Public Law (P.L.) 113-283.NIST is responsible for developing information security standards and guidelines, including minimum requirements for federal information systems, but such standards and guidelines shall not apply to national se...

Scalable range locks for scalable address spaces and beyond

Range locks are a synchronization construct designed to provide concurrent access to multiple threads (or processes) to disjoint parts of a shared resource. Originally conceived in the file system context, range locks are gaining increasing interest ...

Simple on-the-fly automatic verification of linear temporal logic

Spectre Returns! Speculation Attacks using the Return Stack Buffer

The recent Spectre attacks exploit speculative execution, a pervasively used feature of modern microprocessors, to allow the exfiltration of sensitive data across protection boundaries. In this paper, we introduce a new Spectre-class attack that we c...

Syntax and semantics of the weak consistency model specification language cat

We provide the syntax and semantics of the cat language, a domain specific language to describe consistency properties of parallel/distributed programs. The language is implemented in the herd7 too (http://diy.inria.fr/doc/herd.html)l.

"We do not appreciate being experimented on": Developer and Researcher Views on the Ethics of Experiments on Open-Source Projects

A tenet of open source software development is to accept contributions from users-developers (typically after appropriate vetting). But should this also include interventions done as part of research on open source development? Following an incident ...