Publication

What Good are Probabilistic Specifications and What Probabilistic Specifications are Good?

2003
Reports

Abstract

The number of probabilistic approaches to ``classic'' distributed systems problems such as reliable broadcast, consensus, or leader election, has further increased recently. Probabilistic algorithms, possibly starting from probabilistic system models, have been motivated by the need for practicable solutions to such problems, circumventing bottlenecks and limitations inherent to distributed computing. While many approaches coming out of this revival of probabilistic approaches are indeed pathbreaking, it is legitimate to question the usefulness of certain efforts, which claim some form of probabilistic reliability, yet fail to provide clear specifications of the proposed algorithms. In this paper, we point out the inherent difficulties related to the specification of the behavior of probabilistic algorithms through various examples.

Official source

https://infoscience.epfl.ch/entities/publication/ce6243bc-0a41-49a7-80a3-d6378fe09d50

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

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.

2003
Reports

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/ce6243bc-0a41-49a7-80a3-d6378fe09d50

About this result

Related concepts (32)

Probabilistic logic

Probabilistic logic (also probability logic and probabilistic reasoning) involves the use of probability and logic to deal with uncertain situations. Probabilistic logic extends traditional logic truth tables with probabilistic expressions. A difficulty of probabilistic logics is their tendency to multiply the computational complexities of their probabilistic and logical components. Other difficulties include the possibility of counter-intuitive results, such as in case of belief fusion in Dempster–Shafer theory.

Behavior

Behavior (American English) or behaviour (British English) is the range of actions and mannerisms made by individuals, organisms, systems or artificial entities in some environment. These systems can include other systems or organisms as well as the inanimate physical environment. It is the computed response of the system or organism to various stimuli or inputs, whether internal or external, conscious or subconscious, overt or covert, and voluntary or involuntary.

Probabilistic Turing machine

In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution. As a consequence, a probabilistic Turing machine can—unlike a deterministic Turing Machine—have stochastic results; that is, on a given input and instruction state machine, it may have different run times, or it may not halt at all; furthermore, it may accept an input in one execution and reject the same input in another execution.

Related publications (32)

What Good are Probabilistic Specifications and What Probabilistic Specifications are Good?

Chat with Graph Search

The behavior biopsy: Interpreting animal behavior as embodied, situated, and hierarchical

Structured Prompts, Better Outcomes? Exploring the Effects of a Structured Interface with ChatGPT in a Graduate Robotics Course

Spectral Clustering with Side Information