# Some results with MWMR registers by H. Fauconnier

## ,

**University Paris Diderot** –

## Abstract:

Abstract:

What is the number of registers required to solve a task? Many years ago, Ellen and al. have proved a lower bound of square root of n registers to (obstruction free) solve the consensus, but today there is no known consensus algorithm using less than n registers. In a system of n processes, if each process has its own SWMR register, it is possible to emulate any number of registers, but what of tasks can be solved with less than n registers?

Before considering this question, what’s happens when we only have MWMR registers? A trivial way may be to assign each process one MWMR: given an array C of MWMR registers, C[i] will be assigned to process i. But if the n processes have ids drawn from a very large set of N identifiers, the size of C depends on N not on n. Renaming algorithms may help but they use a non linear (on n) number of MWMR registers.

We give a solution without renaming that implements for each process a SWMR register using only n MWMR registers. This implementation is only non-blocking, but we get with 2(n-1) MWMR a wait-free implementation. Moreover we prove that n is a lower bound to such implementation. We also prove that n MWMR registers are sufficient to solve any wait-free task solvable with any number of (MWMR or SWMR) registers.

If the number of MWMR is less than n, we prove that some tasks may nevertheless been (obstruction-free) solved. For example, we prove that 2 registers are necessary and sufficient to (Obstruction-Free) solve the set-agreement problem.

This a joint work with C. Delporte, H. Fauconnier, E. Gafni and S. Rajbaum (ICDCN 2013). A recent extension to the adaptive case has been made jointly with L. Lamport ( DISC 2013)

Bio:

H. Fauconnier received his Ph.D. in 1982 and HDR degree in 2001 in Computer Science from the University Paris-Diderot, after Master degrees in Mathematics and Computer Science. He is a top level expert in Fault Tolerance Distributed Computing and he has published papers in many journals like JACM, Distributed Computing, TOPLAS and in top level conferences of this aera (PODC, DISC, DSN, ICDCS, …). He has been program committee members of established conferences in Distributed Computing such as PODC, DISC, IEEEE ICDCS, OPODIS…He is currently at LIAFA, University Paris Diderot.

Date: 2013-Dec-04 Time: 11:00:00 Room: 336

For more information:

### Upcoming Events

### Workshop “Metabolism and mathematical models: Two for a tango” – 2nd Edition

**Title: ** Workshop Metabolism and mathematical models: Two for a tango – 2nd Edition

**Dates:** October 25-26, 2022

**Location:** This workshop will be held in a virtual way

The topic of this workshop is metabolism in general, with a special focus, although not exclusive, on parasitology. Besides an exploration of the biological, biochemical and biomedical aspects, the workshop will also aim at presenting some of the mathematical modelling, algorithmic theory and software development that have become crucial to explore such aspects.

This workshop is being organised in the context of two projects, both with the Inria European Team Erable. One of the projects involves a partnership with the University of São Paulo (USP), in São Paulo, Brazil, more specifically the Institute of Mathematics and Statistics (IME) and the Institute of Biomedical Sciences – Inria Associated Team Capoeira – and the other involves the Inesc-ID/IST in Portugal, ETH in Zürich and EMBL in Heidelberg – H2020 Twinning Project Olissipo.

The workshop is open to all members of these two projects but also, importantly, to the community in general.

The program and more details are available here.