Introduction to local certification

Autor: Laurent Feuilloley

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol vol. 23, no. 3, Iss Distributed Computing and... (2021)

A distributed graph algorithm is basically an algorithm where every node of a graph can look at its neighborhood at some distance in the graph and chose its output. As distributed environment are subject to faults, an important issue is to be able to

Externí odkaz: https://doaj.org/article/88779c42dfea497e84a9938a5bff881a

Lower Bound for Constant-Size Local Certification

Autor: Virgina Ardévol Martínez, Marco Caoduro, Laurent Feuilloley, Jonathan Narboni, Pegah Pournajafi, Jean-Florent Raymond

Publikováno v: Lecture Notes in Computer Science, Stabilization, Safety, and Security of Distributed Systems, 24th International Symposium, SSS 2022
Stabilization, Safety, and Security of Distributed Systems, 24th International Symposium, SSS 2022, Clermont-Ferrand, France
Stabilization, Safety, and Security of Distributed Systems, 24th International Symposium, SSS 2022, Clermont-Ferrand, France, Nov 2022, Clermont-Ferrand, France. pp.239-253, ⟨10.1007/978-3-031-21017-4_16⟩
Lecture Notes in Computer Science ISBN: 9783031210167

The full article is available on arxiv.; International audience

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::999a7bcfe472cabdb6db8dc4dc77f310
https://uca.hal.science/hal-03874784

Redundancy in distributed proofs

Autor: Ami Paz, Mor Perry, Laurent Feuilloley, Juho Hirvonen, Pierre Fraigniaud

Publikováno v: 32nd International Symposium on Distributed Computing
32nd International Symposium on Distributed Computing, 2018, New Orleans, United States. ⟨10.4230/LIPIcs.DISC.2018.24⟩
Distributed Computing

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 r

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0f33d88d5962a68f3484b8d06b770ce6
https://doi.org/10.1007/s00446-020-00386-z

Silent MST Approximation for Tiny Memory

Autor: Lélia Blin, Swan Dubois, Laurent Feuilloley

Publikováno v: Lecture Notes in Computer Science ISBN: 9783030643478
SSS
SSS 2020 : The 22th International Symposium on Stabilization, Safety, and Security of Distributed Systems
SSS 2020 : The 22th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Nov 2020, Austin, TX / Virtual, United States. pp.118-132, ⟨10.1007/978-3-030-64348-5_10⟩

In this paper we show that approximation can help reduce the space used for self-stabilization. In the classic \emph{state model}, where the nodes of a network communicate by reading the states of their neighbors, an important measure of efficiency i

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bd0c0ebc5c09221398bb1bd81b73bf1a
https://doi.org/10.1007/978-3-030-64348-5_10

Lower bounds for text indexing with mismatches and differences

Autor: Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya

Publikováno v: SODA 2019-Symposium on Discrete Algorithms
SODA 2019-Symposium on Discrete Algorithms, Jan 2019, San Diego, United States

In this paper we study lower bounds for the fundamental problem of text indexing with mismatches and differences. In this problem we are given a long string of length $n$, the "text", and the task is to preprocess it into a data structure such that g

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4d8336b8f13c8aec98096e5a33950c02
https://hal.archives-ouvertes.fr/hal-01960182/file/main-blast.pdf