Concept

Nondeterministic algorithm

Publications associées (54)

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

Robust Distributed Coverage using a Swarm of Miniature Robots

Alcherio Martinoli, Nicolaus Correll

For the multi-robot coverage problem deterministic deliberative as well as probabilistic approaches have been proposed. Whereas deterministic approaches usually provide provable completeness and promise good performance under perfect conditions, probabilis ...

2007

Adaptive and robust media streaming over multiple channels with bursty losses

Pascal Frossard, Jean-Paul Wagner

This paper addresses the problem of efficiently delivering a layered media stream from multiple senders to a single receiver, over channels that present correlated packet loss patterns. Using a digital fountain approach, the performance of a distributed st ...

2007

On the Impossibility of Boosting Distributed Service Resilience

Rachid Guerraoui

We show that no deterministic algorithm can solve consensus in the presence of t+1 process crash failures, in a system of n processes that communicate in a reliable way and synchronize their activities using any number of t-resilient services. These base s ...

2005

Media-Specific Rate Allocation in Multipath Networks

Pascal Frossard, Dan Jurca

We address the problem of joint path selection and rate allocation in multipath streaming in order to optimize a media specific quality of service. An optimization problem is proposed, which aims at minimizing a video distortion metric based on sequence-de ...

2005

From Nondeterministic Buchi and Streett Automata to Deterministic Parity Automata

Determinisation and complementation are foundational notions in computer science. When considering finite automata on finite words nondeterminisation and complementation are one and the same. Given a nondeterministic finite automaton there exists an expone ...

2005

Democratrizing the Parliament

Rachid Guerraoui

This paper presents a replication algorithm that implements a highly-available, non-deterministic state machine. Our algorithm generalizes the Paxos parliament algorithm of Lamport to cope with non-deterministic computations, while preserving its nice resi ...

2001

Advances in Internet Quality of Service

Jean-Yves Le Boudec

We describe recent advances in theories and architecture that support performance guarantees needed for quality of service networks. We start with deterministic computations and give applications to integrated services, differentiated services, and playbac ...

2001

Improved data structures for fully dynamic biconnectivity

Monika Henzinger

We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs. A fully dynamic algorithm maintains a graph during a sequence of insertions and deletions of edges or isolated vertices. Let m be the number of edge ...

2000

Replication of non-deterministic objects

This thesis discusses replication of non-deterministic objects in distributed systems to achieve fault tolerance against crash failures. The objects replicated are the virtual nodes of a distributed application. Replication is viewed as an issue that is to ...

EPFL1998

Computing vertex connectivity: New bounds from old techniques

Monika Henzinger

The vertex connectivity K of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time ...

IEEE1996