Pierre Fraigniaud

Pierre Fraigniaud

Auto-generated profile, based on publicly available information

Pierre Fraigniaud

Univ Paris Cite, Inst Rech Informat Fondamentale, Paris, France

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
7 October 2020 in Distributed Computing
Verified
Journal Article
Open access
PDF file
LFLaurent Feuilloley
Laurent Feuilloley
PFPierre Fraigniaud
Pierre Fraigniaud
JHJuho Hirvonen
Juho Hirvonen
APAmi Paz
Ami Paz
MPMor Perry
Mor Perry
Distributed proofs are mechanisms that enable the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g., having a specific diameter), or on objects distributed over the nodes (e.g., a spanning tree). We consider well known mechanisms consisting of two components: aproverthat assigns acertificateto each node, and a distributed algorithm called averifierthat is in charge of verifying the distributed proof formed by the collection of all certificates. We show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs to establish perfect tradeoffs between thesize of the certificatestored at every node, and thenumber of roundsof the verification protocol.

6 June 2018 in Distributed Computing
Verified
Journal Article
Open access
PDF file
PFPierre Fraigniaud
Pierre Fraigniaud
ENEmanuele Natale
Emanuele Natale
Error-correcting codes are efficient methods for handling noisy communication channels in the context of technological networks. However, such elaborate methods differ a lot from the unsophisticated way biological entities are supposed to communicate. Yet, it has been recently shown by Feinerman et al. (PODC 2014 ) that complex coordination tasks such as rumor spreading and majority consensus can plausibly be achieved in biological systems subject to noisy communication channels, where every message transferred through a channel remains intact with small probability \(\frac{1}{2}+\epsilon \), without using coding techniques. This result is a considerable step towards a better understanding of the way biological entities may cooperate. It has nevertheless been established only in the case of 2-valued opinions: rumor spreading aims at broadcasting a single-bit opinion to all nodes, and majority consensus aims at leading all nodes to adopt the single-bit opinion that was initially present in the system with (relative) majority. In this paper, we extend this previous work to k-valued opinions, for any constant \(k\ge 2\). Our extension requires to address a series of important issues, some conceptual, others technical. We had to entirely revisit the notion of noise, for handling channels carrying k-valued messages. In fact, we precisely characterize the type of noise patterns for which plurality consensus is solvable. Also, a key result employed in the bivalued case by Feinerman et al. is an estimate of the probability of observing the most frequent opinion from observing the mode of a small sample. We generalize this result to the multivalued case by providing a new analytical proof for the bivalued case that is amenable to be extended, by induction, and that is of independent interest.

12 April 2023 in Information and Computation
Verified
Journal Article
Closed access
ACArmando Castañeda
Armando Castañeda
PFPierre Fraigniaud
Pierre Fraigniaud
APAmi Paz
Ami Paz
Sergio RajsbaumSergio Rajsbaum
Sergio Rajsbaum
MRMatthieu Roy
Matthieu Roy
CTCorentin Travers
Corentin Travers

5 November 2024 in Theoretical Computer Science
Verified
Journal Article
Closed access
CDCarole Delporte-Gallet
Carole Delporte-Gallet
HFHugues Fauconnier
Hugues Fauconnier
PFPierre Fraigniaud
Pierre Fraigniaud
MRMikaël Rabie
Mikaël Rabie

21 September 2020 in arXiv
Verified
Preprint
Open access
PDF file
LFLaurent Feuilloley
Laurent Feuilloley
PFPierre Fraigniaud
Pierre Fraigniaud
JHJuho Hirvonen
Juho Hirvonen
APAmi Paz
Ami Paz
MPMor Perry
Mor Perry
Distributed proofs are mechanisms enabling the nodes of a network to collectivity and efficiently check the correctness of Boolean predicates on the structure of the network, or on data-structures distributed over the nodes (e.g., spanning trees or routing tables). We consider mechanisms consisting of two components: a \emph{prover} assigning a \emph{certificate} to each node, and a distributed algorithm called \emph{verifier} that is in charge of verifying the distributed proof formed by the collection of all certificates. In this paper, we show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs for establishing perfect tradeoffs between the \emph{size of the certificate} stored at every node, and the \emph{number of rounds} of the verification protocol. If we allow every node to communicate to distance at most $t$, one might expect that the certificate sizes can be reduced by a multiplicative factor of at least~$t$. In trees, cycles and grids, we show that such tradeoffs can be established for \emph{all} network predicates, i.e., it is always possible to linearly decrease the certificate size. In arbitrary graphs, we show that any part of the certificates common to all nodes can be evenly redistributed among these nodes, achieving even a better tradeoff: this common part of the certificate can be reduced by the size of a smallest ball of radius $t$ in the network. In addition to these general results, we establish several upper and lower bounds on the certificate sizes used for distributed proofs for spanning trees, minimum-weight spanning trees, diameter, additive and multiplicative spanners, and more, improving and generalizing previous results from the literature.