Lecture

Impossibility Result: Atomic SRSW Register

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.

Description

This lecture discusses the impossibility of implementing an atomic SRSW register using a finite number of bounded regular registers without readers writing to the base registers. The slides cover concepts such as SRSW regular registers, atomic operations, and the limitations of constructing such a register. The lecture also explores the properties of digests for finite sequences of values and the challenges in achieving an atomic SRSW register. Various transformations and operations on registers are presented, highlighting the complexities involved in this implementation.

Official source

Related concepts (17)

Regular 4-polytope

In mathematics, a regular 4-polytope is a regular four-dimensional polytope. They are the four-dimensional analogues of the regular polyhedra in three dimensions and the regular polygons in two dimensions. There are six convex and ten star regular 4-polytopes, giving a total of sixteen. The convex regular 4-polytopes were first described by the Swiss mathematician Ludwig Schläfli in the mid-19th century. He discovered that there are precisely six such figures.

Regular polygon

In Euclidean geometry, a regular polygon is a polygon that is direct equiangular (all angles are equal in measure) and equilateral (all sides have the same length). Regular polygons may be either convex, star or skew. In the limit, a sequence of regular polygons with an increasing number of sides approximates a circle, if the perimeter or area is fixed, or a regular apeirogon (effectively a straight line), if the edge length is fixed. These properties apply to all regular polygons, whether convex or star.

Regular polytope

In mathematics, a regular polytope is a polytope whose symmetry group acts transitively on its flags, thus giving it the highest degree of symmetry. All its elements or j-faces (for all 0 ≤ j ≤ n, where n is the dimension of the polytope) — cells, faces and so on — are also transitive on the symmetries of the polytope, and are regular polytopes of dimension ≤ n. Regular polytopes are the generalized analog in any number of dimensions of regular polygons (for example, the square or the regular pentagon) and regular polyhedra (for example, the cube).

Regular expression

A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" or "find and replace" operations on strings, or for input validation. Regular expression techniques are developed in theoretical computer science and formal language theory. The concept of regular expressions began in the 1950s, when the American mathematician Stephen Cole Kleene formalized the concept of a regular language.

Regular language

In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expression engines, which are augmented with features that allow the recognition of non-regular languages). Alternatively, a regular language can be defined as a language recognized by a finite automaton.

Related lectures (23)

Regularity of Weak Solutions

Explores elliptic PDEs, weak solutions, regularity, and strong solutions, with a focus on classical solutions and proof techniques.

Construction of Solutions by Dirichlet-Laplace

Explores the construction of solutions by Dirichlet-Laplace in general domains.

Geodesic Curves: Minimizing Distance and Constant Speed

Covers geodesic curves parameterized at constant speed to minimize distances between points.

MATH-213 Géométrie Différentielle | Jeudi | Automne 24