Sergio Rajsbaum

TCS Journal 2023 Journal Article

A distributed computing perspective of unconditionally secure information transmission in Russian cards problems

• Sergio Rajsbaum

In the generalized Russian cards problem, we have a deck of n cards and three participants, A, B, and C, which receive a, b, and c cards respectively. The signature ( a, b, c ), where n = a + b + c + r, is known to all three participants. The goal is for A to privately communicate her hand to B via a public announcement, without using a shared secret nor cryptography. Using a deterministic protocol, A decides its announcement based on her hand. Using techniques from coding theory, Johnson graphs, and additive number theory, a novel perspective inspired by distributed computing theory is provided, to analyze the amount of information that A needs to send, while preventing C from learning a single card of her hand. In one extreme, B wants to learn all of A's cards; the novel notion of minimal information protocol is considered, so that, in the other extreme, B wishes to learn something about A's hand.

I&C Journal 2023 Journal Article

Synchronous t-resilient consensus in arbitrary graphs

• Armando Castañeda
• Pierre Fraigniaud
• Ami Paz
• Sergio Rajsbaum
• Matthieu Roy
• Corentin Travers

We study the number of rounds needed to solve consensus in a synchronous network G where at most t nodes may fail by crashing. This problem has been thoroughly studied when G is a complete graph, but very little is known when G is arbitrary. We define a notion of radius ( G, t ), that extends the standard graph theoretical notion of radius, for considering all the ways in which t nodes may crash, and we present an algorithm that solves consensus in radius ( G, t ) rounds. Then we derive a lower bound showing that, among oblivious algorithms, our algorithm is optimal for a large family of graphs including all vertex-transitive graphs.

I&C Journal 2022 Journal Article

Distributed computability: Relating k-immediate snapshot and x-set agreement

• Carole Delporte
• Hugues Fauconnier
• Sergio Rajsbaum
• Michel Raynal

This paper introduces a generalization of the immediate snapshot object denoted k-immediate snapshot, requiring that the snapshot returned contains at least ( n − k ) pairs. The case k = n − 1 corresponds to the original immediate snapshot object, which requires that the snapshot returned contains at least one pair 〈process id, value〉 pair, that corresponds to the process id that invoked the operation). The paper first shows that k-immediate snapshot is impossible to implement in an asynchronous read/write system, even if k = n − 2 and t = 1. Then, the paper considers x-set agreement, another object stronger than the classical read/write t-crash read/write model (when x ≤ t ), and studies the relation with the k-immediate snapshot object, establishing strong relations linking these two fundamental distributed computing abstractions. The paper shows conditions under which x-set agreement can be solved in read/write systems enriched with k-immediate snapshot objects. It also shwos when k-immediate snapshot and consensus are equivalent.

I&C Journal 2021 Journal Article

A simplicial complex model for dynamic epistemic logic to study distributed task computability

• Éric Goubault
• Jérémy Ledent
• Sergio Rajsbaum

The usual S 5 n epistemic model for a multi-agent system is based on a Kripke frame, which is a graph whose edges are labeled with agents that do not distinguish between two states. We propose to uncover the higher dimensional information implicit in this structure, by considering a dual, simplicial complex model. We use dynamic epistemic logic (DEL) to study how an epistemic simplicial complex model changes after a set of agents communicate with each other. We concentrate on an action model that represents the so-called immediate snapshot communication patterns of asynchronous agents, because it is central to distributed computability (but our setting works for other communication patterns). There are topological invariants preserved from the initial epistemic complex to the one after the action model is applied, which determine the knowledge that the agents gain after communication. Finally, we describe how a distributed task specification can be modeled as a DEL action model, and show that the topological invariants determine whether the task is solvable. We thus provide a bridge between DEL and the topological theory of distributed computability, which studies task solvability in a shared memory or message passing architecture.

TCS Journal 2021 Journal Article

A topological perspective on distributed network algorithms

• Armando Castañeda
• Pierre Fraigniaud
• Ami Paz
• Sergio Rajsbaum
• Matthieu Roy
• Corentin Travers

More than two decades ago, combinatorial topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that combinatorial topology can also be useful for analyzing distributed algorithms in failure-free networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the local model and dynamic networks.

I&C Journal 2020 Journal Article

Perfect failure detection with very few bits

• Pierre Fraigniaud
• Sergio Rajsbaum
• Corentin Travers
• Petr Kuznetsov
• Thibault Rieutord

A failure detector is a distributed oracle that provides each process with a module that continuously outputs an estimate of which processes in the system have failed. The perfect failure detector provides accurate and eventually complete information about process failures. We show that, in asynchronous failure-prone message-passing systems, perfect failure detection can be achieved using an oracle that outputs at most ⌈ log ⁡ α ( n ) ⌉ + 1 bits per process in n-process systems, where α denotes the inverse-Ackermann function. This result is essentially optimal, as we also show that, in the same environment, no failure detector outputting a constant number of bits per process can achieve perfect failure detection.

GandALF Workshop 2018 Workshop Paper

A Simplicial Complex Model for Dynamic Epistemic Logic to study Distributed Task Computability

• Éric Goubault
• Jérémy Ledent
• Sergio Rajsbaum

The usual epistemic model S5n for a multi-agent system is based on a Kripke frame, which is a graph whose edges are labeled with agents that do not distinguish between two states. We propose to uncover the higher dimensional information implicit in this structure, by considering a dual, simplicial complex model. We use dynamic epistemic logic (DEL) to study how an epistemic simplicial complex model changes after a set of agents communicate with each other. We concentrate on an action model that represents the so called immediate snapshot communication patterns of asynchronous agents, because it is central to distributed computability (but our setting works for other communication patterns). There are topological invariants preserved from the initial epistemic complex to the one after the action model is applied, which determine the knowledge that the agents gain after communication. Finally, we describe how a distributed task specification can be modeled as a DEL action model, and show that the topological invariants determine whether the task is solvable. We thus provide a bridge between DEL and the topological theory of distributed computability, which studies task solvability in a shared memory or message passing architecture.

TCS Journal 2017 Journal Article

From wait-free to arbitrary concurrent solo executions in colorless distributed computing

• Maurice Herlihy
• Sergio Rajsbaum
• Michel Raynal
• Julien Stainer

In an asynchronous distributed system where any number of processes may crash, a process may have to run solo, computing its local output without receiving any information from other processes. In the basic shared memory system where the processes communicate through atomic read/write registers, at most one process may run solo. This paper introduces the family of d-solo models, where d-processes may concurrently run solo, 1 ≤ d ≤ n (the 1-solo model is the basic read/write model). The paper then studies distributed colorless computations in the d-solo models, where process ids are not used, either in task specifications or during computation. It presents a characterization of the colorless tasks that can be solved in each d-solo model. Colorless tasks include consensus, set agreement and many other previously studied tasks. It shows that colorless algorithms have limited computational power for solving tasks, only when d > 1. When d = 1, colorless algorithms can solve the same tasks as algorithms that may use ids. It is well-known that, while consensus is not wait-free solvable in a model where at most one process may run solo, ϵ-approximate agreement is solvable. In a d-solo model, the fundamental solvable task is ( d, ϵ ) -solo approximate agreement, a generalization of ϵ-approximate agreement. Indeed, ( d, ϵ ) -solo approximate agreement can be solved in the d-solo model, but not in the ( d + 1 ) -solo model. Finally, the paper studies a link between the solvability of d-set agreement and ( d, ϵ ) -solo approximate agreement in asynchronous wait-free message-passing systems, which provides an insight on the “maximal partitioning” allowed to solve an approximate agreement task.

TCS Journal 2017 Journal Article

Preface

• Kishore Kothapalli
• Sergio Rajsbaum

TCS Journal 2015 Journal Article

Linear space bootstrap communication schemes

• Carole Delporte-Gallet
• Hugues Fauconnier
• Eli Gafni
• Sergio Rajsbaum

Consider a system of n processes with ids that are drawn from a large space. How can these n processes communicate to solve a problem? It is shown that linear number of Multi-Writer Multi-Reader (MWMR) registers are sufficient to solve any read-write wait-free solvable problem and needed to solve some read-write wait-free solvable problem. This contrasts with the existing possible solution borrowed from adaptive algorithms that require Θ ( n 3 / 2 ) MWMR registers. To obtain the sufficiency result, the paper shows how the processes can non-blocking emulate a system of n Single-Writer Multi-Reader (SWMR) registers on top of n Multi-Writer Multi-Reader (MWMR) registers. For the necessity result, it shows it is impossible to do such an emulation with n − 1 MWMR registers. The paper also presents a wait-free emulation, using 2 n − 1 rather than just n registers. The emulation can be used to solve an infinite sequence of tasks that are sequentially dependent (processes need the previous task's outputs in order to proceed to the next task). A non-blocking emulation cannot be used in this case, because it might starve a process forever.

TCS Journal 2013 Journal Article

Power and limits of distributed computing shared memory models

• Maurice Herlihy
• Sergio Rajsbaum
• Michel Raynal

What can and cannot be computed in a distributed system is a complex function of the system’s communication model, timing model, and failure model. Considering a canonical distributed system model, where processes execute asynchronously, communicate by reading and writing shared memory, and fail by crashing, this paper surveys important results about computability, and explains the fundamental role that topology plays in the distributed computability theory. The paper also considers different types of additional assumptions that allow impossibility results to be circumvented. These assumptions are known under the names failure detectors and adversaries. Finally, it presents a powerful simulation technique (known under the name BG simulation), which allows to show that, from a computability point of view, t -resilience is not different from wait-freedom. When pieced together, the aim of all the concepts, notions, models, and algorithms presented in the paper, is to provide the reader with a synthetic view of important results on the distributed asynchronous read/write shared-memory model, its power and its limits.

TCS Journal 2011 Journal Article

Some problems in distributed computational geometry

• Sergio Rajsbaum
• Jorge Urrutia

In a planar geometric network vertices are located in the plane, and edges are straight line segments connecting pairs of vertices, such that no two of them intersect. In this paper we study distributed computing in asynchronous, failure-free planar geometric networks, where each vertex is associated to a processor, and each edge to a bidirectional message communication link. Processors are aware of their locations in the plane. We consider fundamental computational geometry problems from the distributed computing point of view, such as finding the convex hull of a geometric network and identification of the external face. We also study the classic distributed computing problem of leader election, to understand the impact that geometric information has on the message complexity of solving it. We obtain an O ( n log 2 n ) message complexity algorithm to find the convex hull, and an O ( n log n ) message complexity algorithm to identify the external face of a geometric network of n processors. We present a matching lower bound for the external face problem. We prove that the message complexity of leader election in a geometric ring is Ω ( n log n ), hence geometric information does not help in reducing the message complexity of this problem.

I&C Journal 2011 Journal Article

The impossibility of boosting distributed service resilience

• Paul Attie
• Rachid Guerraoui
• Petr Kuznetsov
• Nancy Lynch
• Sergio Rajsbaum

We study f-resilient services, which are guaranteed to operate as long as no more than f of the associated processes fail. We prove three theorems asserting the impossibility of boosting the resilience of such services. Our first theorem allows any connection pattern between processes and services but assumes these services to be atomic (linearizable) objects. This theorem says that no distributed system in which processes coordinate using f-resilient atomic objects and reliable registers can solve the consensus problem in the presence of f + 1 undetectable process stopping failures. In contrast, we show that it is possible to boost the resilience of some systems solving problems easier than consensus: for example, the 2-set-consensus problem is solvable for 2 n processes and 2 n - 1 failures (i. e. , wait-free) using n-process consensus services resilient to n - 1 failures (wait-free). Our proof is short and self-contained. We then introduce the larger class of failure-oblivious services. These are services that cannot use information about failures, although they may behave more flexibly than atomic objects. An example of such a service is totally ordered broadcast. Our second theorem generalizes the first theorem and its proof to failure-oblivious services. Our third theorem allows the system to contain failure-aware services, such as failure detectors, in addition to failure-oblivious services. This theorem requires that each failure-aware service be connected to all processes; thus, f + 1 process failures overall can disable all the failure-aware services. In contrast, it is possible to boost the resilience of a system solving consensus using failure-aware services if arbitrary connection patterns between processes and services are allowed: consensus is solvable for any number of failures using only 1-resilient 2-process perfect failure detectors. As far as we know, this is the first time a unified framework has been used to describe both atomic and non-atomic objects, and the first time boosting analysis has been performed for services more general than atomic objects.

TCS Journal 2010 Journal Article

Average long-lived binary consensus: Quantifying the stabilizing role played by memory

• Florent Becker
• Sergio Rajsbaum
• Ivan Rapaport
• Eric Rémila

Consider a system composed of n sensors operating in synchronous rounds. In each round an input vector of sensor readings x is produced, where the i -th entry of x is a binary value produced by the i -th sensor. The sequence of input vectors is assumed to be smooth: exactly one entry of the vector changes from one round to the next one. The system implements a fault-tolerant averaging consensus function f. This function returns, in each round, a representative output value v of the sensor readings x. Assuming that at most t entries of the vector can be erroneous, f is required to return a value that appears at least t + 1 times in x. We introduce the definition of instability of the system, which consists in the number of output changes over a random sequence of input vectors. We first design optimal (with respect to the instability measure) consensus systems: D 0 without memory, and D 1 with memory. Then we quantify the gain factor due to memory by computing c n ( t ), the number of decision changes performed by D 0 per decision change performed by D 1.

TCS Journal 2004 Journal Article

Preface

• Juan A. Garay
• Sergio Rajsbaum

TCS Journal 2003 Journal Article

A classification of wait-free loop agreement tasks

• Maurice Herlihy
• Sergio Rajsbaum

Loop agreement is a family of wait-free tasks that includes instances of set agreement and approximate agreement tasks. A task G implements task F if one can construct a solution to F from a solution to G, possibly followed by access to a read/write memory. Loop agreement tasks form a lattice under this notion of implementation. This paper presents a classification of loop agreement tasks. Each loop agreement task can be assigned an algebraic signature consisting of a finitely presented group G and a distinguished element g in G. This signature characterizes the task's power to implement other tasks. If F and G are loop agreement tasks with respective signatures 〈F, f〉 and 〈G, g〉, then F implements G if and only if there exists a group homomorphism h: F→G carrying f to g.

STOC Conference 2001 Conference Paper

Conditions on input vectors for consensus solvability in asynchronous distributed systems

• Achour Mostéfaoui
• Sergio Rajsbaum
• Michel Raynal

This paper introduces and explores a new condition based approach to solve the consensus problem in asynchronous systems. The approach consists of identifying sets of input vectors, called conditions , for which it is possible to design a protocol solving consensus despite the occurrence of up to f process crashes.

STOC Conference 1999 Conference Paper

Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract)

• Yefim Dinitz
• Shlomo Moran
• Sergio Rajsbaum

MFCS Conference 1999 Conference Paper

New Perspectives in Distributed Computing

• Maurice Herlihy
• Sergio Rajsbaum

Abstract This is an informal introduction to recent developments in the theory of distributed computing, showing how notions from combinatorial and algebraic topology can be used to capture essential aspects of distributed computing.

TCS Journal 1998 Journal Article

On mixed connectivity certificates

• Shimon Even
• Gene Itkis
• Sergio Rajsbaum

Vertex and edge connectivity are special cases of mixed connectivity, in which all edges and a specified set of vertices play a similar role. Certificates of k-connectivity for a graph are obtained by removing a subset of its edges, while preserving its connectivity up to k. We unify the previous work on connectivity certificates and extend it to handle mixed connectivity and multigraphs. Our treatment contributes a new insight of the pertinent structures, yielding more general results and simpler proofs. Also, we present the first communicationoptimal distributed algorithm for finding mixed connectivity certificates.

STOC Conference 1997 Conference Paper

The Decidability of Distributed Decision Tasks (Extended Abstract)

• Maurice Herlihy
• Sergio Rajsbaum

STOC Conference 1994 Conference Paper

A theory of clock synchronization (extended abstract)

• Boaz Patt-Shamir
• Sergio Rajsbaum

STOC Conference 1990 Conference Paper

The Use of a Synchronizer Yields Maximum Computation Rate in Distributed Networks (Extended Abstract)

• Shimon Even
• Sergio Rajsbaum