Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Publication

On the Hardness of the Strongly Dependent Decision Problem

Martin Biely
2019
Conference Papers

Abstract

We present necessary and sufficient conditions for solving the strongly dependent decision (SDD) problem in various distributed systems. Our main contribution is a novel characterization of the SDD problem based on point-set topology. For partially synchronous systems, we show that any algorithm that solves the SDD problem induces a set of executions that is closed with respect to the point-set topology. We also show that the SDD problem is not solvable in the asynchronous system augmented with any arbitrarily strong failure detectors.

Official source

https://infoscience.epfl.ch/entities/publication/27cd48ff-8737-4469-98a7-f38dcfb8b537

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.

Martin Biely
2019
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/27cd48ff-8737-4469-98a7-f38dcfb8b537

About this result

Related concepts (17)

Set theory

Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concerned with those that are relevant to mathematics as a whole. The modern study of set theory was initiated by the German mathematicians Richard Dedekind and Georg Cantor in the 1870s. In particular, Georg Cantor is commonly considered the founder of set theory.

Empty set

In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other theories, its existence can be deduced. Many possible properties of sets are vacuously true for the empty set. Any set other than the empty set is called non-empty. In some textbooks and popularizations, the empty set is referred to as the "null set".

Set (mathematics)

A set is the mathematical model for a collection of different things; a set contains elements or members, which can be mathematical objects of any kind: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets. The set with no element is the empty set; a set with a single element is a singleton. A set may have a finite number of elements or be an infinite set. Two sets are equal if they have precisely the same elements. Sets are ubiquitous in modern mathematics.

Related publications (29)

On the Hardness of the Strongly Dependent Decision Problem

Graph Chatbot

Hitting with Probability One for Stochastic Heat Equations with Additive Noise

Dynamical system approach to navigation around obstacles

Reliable data-driven decision-making through optimal transport