Publication

On verifying causal consistency

Publications associées (49)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Fast Access to Distributed Atomic Memory

Rachid Guerraoui, Marko Vukolic, Ron Levy, Partha Dutta

We study eﬃcient and robust implementations of an atomic read-write data structure over an asynchronous distributed message-passing system made of reader and writer processes, as well as a number of servers implementing the data structure. We determine the ...

Society for Industrial and Applied Mathematics2010

A note on the data-driven capacity of P2P networks

Pascal Frossard

We consider two capacity problems in P2P networks. In the first one, the nodes have an infinite amount of data to send and the goal is to optimally allocate their uplink bandwidths such that the demands of every peer in terms of receiving data rate are met ...

2009

Generalized Hypertree Decompositions: NP-hardness and Tractable Variants

Zoltán Miklós

The generalized hypertree width GHW(H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded GHW are known to be solvable in polynomial time. However, i ...

2009

Finitary Winning in omega-Regular Games

Games on graphs with omega-regular objectives provide a model for the control and synthesis of reactive systems. Every omega-regular objective can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens " ...

2009

On the Complexity of the Asymmetric VPN Problem

Thomas Rothvoss, Laura Sanità

We give the first constant factor approximation algorithm for the asymmetric Virtual Private Network (VPN) problem with arbitrary concave costs. We even show the stronger result, that there is always a tree solution of cost at most 2 OPT and that a tree so ...

Springer2009

Efficient Data Structures For Decision Diagrams

Stéphane Rabie

Dynamic Programming Optimization (DPOP) is an algorithm proposed to solve distributed constraint optimization problems. In order to represent the multi-values functions manipulated in this algorithm, a data structure called Hypercube was implemented. A mor ...

2009

New Results on Optimizing Rooted Triplets Consistency

A set of phylogenetic trees with overlapping leaf sets is consistent if it can be merged without conflicts into a supertree. In this paper, we study the polynomial-time approximability of two related optimization problems called the maximum rooted triplets ...

Springer2008

Efficient Data Structures for Decision Diagrams

Nacereddine Ouaret

Dynamic Programming OPtimization (DPOP) is an algorithm proposed for solving distributed constraint optimization problems. In this algorithm, Hypercubes are used as the format of the messages exchanged between the agents. Then, Hybrid-DPOP (H-DPOP), a hybr ...

2008

Reduction of stochastic parity to stochastic mean-payoff games

A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with w-regular winning conditions specified as parity objectives, and mean-payoff (or limit-average) objectives. These games ...

2008

World-set Decompositions: Expressiveness and Efficient Algorithms

Christoph Koch

Uncertain information is commonplace in real-world data management scenarios. The ability to represent large sets of possible instances (worlds) while supporting efficient storage and processing is an important challenge in this context. The recent formali ...

2007