Arrow Research search

Author name cluster

Sergio Rajsbaum

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers
2 author rows

Possible papers

18

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.

Details DOI

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.

Details DOI

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.

PDF Details DOI

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.

Details DOI

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.

Details DOI

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.

Details DOI

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.

Details DOI

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.

Details DOI

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.

Details DOI

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.

Details

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.

Details DOI