Publication

Generating Fast Indulgent Algorithms

Related publications (114)

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.

Range queries in trie-structured overlays

Karl Aberer, Manfred Hauswirth, Anwitaman Datta, Roman Schmidt, Renault John Lecoultre

Among the open problems in P2P systems, support for non-trivial search predicates, standardized query languages, distributed query processing, query load balancing, and quality of query results have been identified as some of the most relevant issues. This ...

2005

Time-complexity bounds on agreement problems

Partha Dutta

In many distributed systems, designing an application that maintains consistency and availability despite failure of processes, involves solving some form of agreement. Not surprisingly, providing efficient agreement algorithms is critical for improving th ...

EPFL2005

New Attacks against Reduced-Round Versions of IDEA

Pascal Junod

In this paper, we describe a sequence of simple, yet e cient chosen-plaintext (or chosen-ciphertext) attacks against reduced-round versions of IDEA (with 2, 2.5, 3, 3.5, and 4 rounds) which compare favourably with the best known attacks: some of them decre ...

2005

Gracefully Degrading Fair Exchange with Security Modules

Rachid Guerraoui, Marko Vukolic, Gildas Avoine

The fair exchange problem is key to trading electronic items in systems of mutually untrusted parties. In modern variants of such systems, each party is equipped with a security module. The security modules trust each other but can only communicate by exch ...

2005

The Overhead of Consensus Failure Recovery

Rachid Guerraoui, Partha Dutta

Many reliable distributed systems are consensus-based and typically operate under two modes: a fast normal mode in failure-free periods, and a slower recovery mode following failures. A lot of work has been devoted to optimizing the normal mode, but little ...

2004

Lower Bounds on Generic Broadcast Algorithms

André Schiper, Fernando Pedone

This paper establishes tight lower bounds on the time complexity of algorithms solving the generic broadcast problem. Generic broadcast assumes a symmetric, non-reflexive conflict relation on the set of messages, and requires ordered delivery only for conf ...

2004

The Complexity of Asynchronous Byzantine Consensus

Rachid Guerraoui, Marko Vukolic, Partha Dutta

This paper establishes the first theorem relating resilience, round complexity and authentication in distributed computing. We give an exact measure of the time complexity of consensus algorithms that tolerate Byzantine failures and arbitrary long periods ...

2004

On the complexity of fixed parameter clique and dominating set

Friedrich Eisenbrand

We provide simple, faster algorithms for the detection of cliques and dominating sets of fixed order. Our algorithms are based on reductions to rectangular matrix multiplication. We also describe an improved algorithm for diamonds detection. © 2004 Elsevie ...

2004

Robust Emulations of Shared Memory in a Crash-Recovery Model

Rachid Guerraoui, Ron Levy

A shared memory abstraction can be robustly emulated over an asynchronous message passing system where any process can fail by crashing and possibly recover (crash-recovery model), by having (a) the processes exchange messages to synchronize their read and ...

2004

Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm

Thomas Liebling, Jean-Albert Ferrez

We address the weighted max-cut problem, or equivalently the problem of maximizing a quadratic form in n binary variables. If the underlying (symmetric) matrix is positive semidefinite of fixed rank d, then the problem can be reduced to searching the extre ...

2004