Publication

A Thrifty Universal Construction

Related publications (106)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

The Semantics of Progress in Lock-Based Transactional Memory

Rachid Guerraoui, Michal Kapalka

Transactional memory (TM) is a promising paradigm for concurrent programming. Whereas the number of TM implementations is growing, however, little research has been conducted to precisely define TM semantics, especially their progress guarantees. This pape ...

ACM2009

An output-sensitive algorithm for multi-parametric LCPs with sufficient matrices

Colin Neil Jones

This paper considers the multi-parametric linear complementarity problem (pLCP) with sufficient matrices. The main result is an algorithm to find a polyhedral decomposition of the set of feasible parameters and to construct a piecewise affine function that ...

2009

The Complexity of Obstruction-Free Implementations

Rachid Guerraoui, Hagit Albo Attiya

Obstruction-free implementations of concurrent ob jects are optimized for the common case where there is no step contention, and were recently advocated as a solution to the costs associated with synchronization without locks. In this paper, we study this ...

2009

Graph-Based Approach for 3D Object Duplicate Detection

Touradj Ebrahimi, Frédéric Dufaux, Péter Vajda

In this paper, we consider the challenging problem of object duplicate detection and localization. Several applications require efficient object duplicate detection methods, such as automatic video and image tagging, video surveillance, and high level imag ...

2009

Lightweight Block Ciphers Revisited: Cryptanalysis of Reduced Round PRESENT and HIGHT

Onur Özen, Cihangir Tezcan, Kerem Varici

Design and analysis of lightweight block ciphers have become more popular due to the fact that the future use of block ciphers in ubiquitous devices is generally assumed to be extensive. In this respect, several lightweight block ciphers are designed, of w ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009

Reducing Memory Requirements for Combinatorial Attacks on NTRU via Multiple Birthdays

In this paper we view the possibilities to lance a multiple (iterative) birthday attack on NTRU. Recently Wagner's algorithm for the generalized birthday problem [9] allowed to speed-up several combinatorial attacks. However, in the case of NTRU we can not ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009

The Collective Memory of Amnesic Processes

Rachid Guerraoui, Bastian Pochon, James Pugh, Ron Levy

This paper considers the problem of robustly emulating a shared atomic memory over a distributed message passing system where processes can fail by crashing and possibly recover. We revisit the notion of atomicity in the crash-recovery context and introduc ...

2008

The complexity of reliable distributed storage

Ron Levy

Distributed storage systems based on commodity hardware have gained in popularity because they are cheaper, can be made more reliable and offer better scalability than centralized storage systems. However, implementing and managing such systems is more com ...

EPFL2008

The Semantics of Progress in Lock-Based Transactional Memory

Rachid Guerraoui, Michal Kapalka

2008

A scalable and oblivious atomicity assertion

Rachid Guerraoui, Marko Vukolic

This paper presents SOAR: the first oblivious atomicity assertion with polynomial complexity. SOAR enables to check atomicity of a single-writer multi-reader register implementation. The basic idea underlying the low overhead induced by SOAR lies in greedi ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2008