6 Search Results for "Travers, Corentin"

Document
DOI: 10.4230/LIPIcs.DISC.2025.8
Auditable Shared Objects: From Registers to Synchronization Primitives

Authors: Hagit Attiya, Antonio Fernández Anta, Alessia Milani, Alexandre Rapetti, and Corentin Travers

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Auditability allows to track operations performed on a shared object, recording who accessed which information. This gives data owners more control on their data. Initially studied in the context of single-writer registers, this work extends the notion of auditability to other shared objects, and studies their properties. We start by moving from single-writer to multi-writer registers, and provide an implementation of an auditable n-writer m-reader read / write register, with O(n+m) step complexity. This implementation uses (m+n)-sliding registers, which have consensus number m+n. We show that this consensus number is necessary. The implementation extends naturally to support an auditable load-linked / store-conditional (LL/SC) shared object. LL/SC is a primitive that supports efficient implementation of many shared objects. Finally, we relate auditable registers to other access control objects, by implementing an anti-flickering deny list from auditable registers.
Cite as

Hagit Attiya, Antonio Fernández Anta, Alessia Milani, Alexandre Rapetti, and Corentin Travers. Auditable Shared Objects: From Registers to Synchronization Primitives. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.DISC.2025.8,
  author =	{Attiya, Hagit and Anta, Antonio Fern\'{a}ndez and Milani, Alessia and Rapetti, Alexandre and Travers, Corentin},
  title =	{{Auditable Shared Objects: From Registers to Synchronization Primitives}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.8},
  URN =		{urn:nbn:de:0030-drops-248253},
  doi =		{10.4230/LIPIcs.DISC.2025.8},
  annote =	{Keywords: Auditability, Wait-free implementation, Synchronization power, Distributed objects, Shared memory, LL/SC, Deny List}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.34
Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure

Authors: Pierre Fraigniaud, Minh Hang Nguyen, and Ami Paz

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Consensus is arguably the most studied problem in distributed computing as a whole, and particularly in the distributed message-passing setting. In this latter framework, research on consensus has considered various hypotheses regarding the failure types, the memory constraints, the algorithmic performances (e.g., early stopping and obliviousness), etc. Surprisingly, almost all of this work assumes that messages are passed in a complete network, i.e., each process has a direct link to every other process. A noticeable exception is the recent work of Castañeda et al. (Inf. Comput. 2023) who designed a generic oblivious algorithm for consensus running in radius(G,t) rounds in every graph G, when up to t nodes can crash by irrevocably stopping, where t is smaller than the node-connectivity κ of G. Here, radius(G,t) denotes a graph parameter called the radius of G whenever up to t nodes can crash. For t = 0, this parameter coincides with radius(G), the standard radius of a graph, and, for G = K_n, the running time radius(K_n,t) = t+1 of the algorithm exactly matches the known round-complexity of consensus in the clique K_n. Our main result is a proof that radius(G,t) rounds are necessary for oblivious algorithms solving consensus in G when up to t nodes can crash, thus validating a conjecture of Castañeda et al., and demonstrating that their consensus algorithm is optimal for any graph G. We also extend the result of Castañeda et al. to two different settings: First, to the case where the number t of failures is not necessarily smaller than the connectivity κ of the considered graph; Second, to the k-set agreement problem for which agreement is not restricted to be on a single value as in consensus, but on up to k different values.
Cite as

Pierre Fraigniaud, Minh Hang Nguyen, and Ami Paz. Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.STACS.2025.34,
  author =	{Fraigniaud, Pierre and Nguyen, Minh Hang and Paz, Ami},
  title =	{{Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{34:1--34:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.34},
  URN =		{urn:nbn:de:0030-drops-228606},
  doi =		{10.4230/LIPIcs.STACS.2025.34},
  annote =	{Keywords: Consensus, set-agreement, fault tolerance, crash failures}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.21
No Symmetric Broadcast Abstraction Characterizes k-Set-Agreement in Message-Passing Systems

Authors: Sylvain Gay, Achour Mostéfaoui, and Matthieu Perrin

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
This paper explores the relationship between broadcast abstractions and the k-set agreement (k-SA) problem in crash-prone asynchronous distributed systems. It specifically investigates whether any broadcast abstraction is computationally equivalent to k-SA in message-passing systems. A key contribution of the paper is the delineation of the realm of "meaningful" broadcast abstractions, through the introduction of two new symmetry properties: compositionality and content-neutrality, inspired by the principle of network neutrality. Such preciseness in definition is essential for this paper’s scope, as our aim is not to characterize the computing power of a specific broadcast abstraction, but rather to explore the domain of broadcast abstractions as a whole, in search of a broadcast abstraction with certain characteristics. The paper’s main contribution is the proof that no broadcast abstraction, which is both content-neutral and compositional, is computationally equivalent to k-set agreement when 1 < k < n, in the crash-prone asynchronous message-passing model. To the best of our knowledge, this result represents the first instance of showing that a coordination problem cannot be expressed by an equivalent broadcast abstraction. It does not establish the absence of an implementation, but rather the absence of a specification that possesses certain properties.
Cite as

Sylvain Gay, Achour Mostéfaoui, and Matthieu Perrin. No Symmetric Broadcast Abstraction Characterizes k-Set-Agreement in Message-Passing Systems. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gay_et_al:LIPIcs.OPODIS.2024.21,
  author =	{Gay, Sylvain and Most\'{e}faoui, Achour and Perrin, Matthieu},
  title =	{{No Symmetric Broadcast Abstraction Characterizes k-Set-Agreement in Message-Passing Systems}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.21},
  URN =		{urn:nbn:de:0030-drops-225573},
  doi =		{10.4230/LIPIcs.OPODIS.2024.21},
  annote =	{Keywords: Agreement problem, Asynchronous system, Broadcast abstraction, Communication abstraction, Compositionality, Message-passing system, Network neutrality, Process crash, k-Set agreement, Wait-free model, Total order broadcast}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.32
Distributed Agreement in the Arrovian Framework

Authors: Kenan Wood, Hammurabi Mendes, and Jonad Pulaj

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Preference aggregation is a fundamental problem in voting theory, in which public input rankings of a set of alternatives (called preferences) must be aggregated into a single preference that satisfies certain soundness properties. The celebrated Arrow Impossibility Theorem is equivalent to a distributed task in a synchronous fault-free system that satisfies properties such as respecting unanimous preferences, maintaining independence of irrelevant alternatives (IIA), and non-dictatorship, along with consensus since only one preference can be decided. In this work, we study a weaker distributed task in which crash faults are introduced, IIA is not required, and the consensus property is relaxed to either k-set agreement or ε-approximate agreement using any metric on the set of preferences. In particular, we prove several novel impossibility results for both of these tasks in both synchronous and asynchronous distributed systems. We additionally show that the impossibility for our ε-approximate agreement task using the Kendall tau or Spearman footrule metrics holds under extremely weak assumptions.
Cite as

Kenan Wood, Hammurabi Mendes, and Jonad Pulaj. Distributed Agreement in the Arrovian Framework. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wood_et_al:LIPIcs.OPODIS.2024.32,
  author =	{Wood, Kenan and Mendes, Hammurabi and Pulaj, Jonad},
  title =	{{Distributed Agreement in the Arrovian Framework}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{32:1--32:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.32},
  URN =		{urn:nbn:de:0030-drops-225686},
  doi =		{10.4230/LIPIcs.OPODIS.2024.32},
  annote =	{Keywords: Approximate Agreement, Set Agreement, Preference Aggregation, Voting Theory, Impossibility}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.3
Long-Lived Counters with Polylogarithmic Amortized Step Complexity

Authors: Mirza Ahad Baig, Danny Hendler, Alessia Milani, and Corentin Travers

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
A shared-memory counter is a well-studied and widely-used concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. Jayanti, Tan and Toueg [Jayanti et al., 2000] proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read and write operations, of a large class of shared objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity. In this paper, we address this gap. We present the first wait-free n-process counter, implemented using only read and write operations, whose amortized operation step complexity is O(log^2 n) in all executions. This is the first non-blocking read/write counter algorithm that provides sub-linear amortized step complexity in executions of arbitrary length. Since a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations exists, our upper bound is optimal up to a logarithmic factor.
Cite as

Mirza Ahad Baig, Danny Hendler, Alessia Milani, and Corentin Travers. Long-Lived Counters with Polylogarithmic Amortized Step Complexity. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{baig_et_al:LIPIcs.DISC.2019.3,
  author =	{Baig, Mirza Ahad and Hendler, Danny and Milani, Alessia and Travers, Corentin},
  title =	{{Long-Lived Counters with Polylogarithmic Amortized Step Complexity}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.3},
  URN =		{urn:nbn:de:0030-drops-113108},
  doi =		{10.4230/LIPIcs.DISC.2019.3},
  annote =	{Keywords: Shared Memory, Wait-freedom, Counter, Amortized Complexity, Concurrent Objects}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2016.16
Decentralized Asynchronous Crash-Resilient Runtime Verification

Authors: Borzoo Bonakdarpour, Pierre Fraigniaud, Sergio Rajsbaum, David A. Rosenblueth, and Corentin Travers

Published in: LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016)

Abstract
Runtime Verification (RV) is a lightweight method for monitoring the formal specification of a system during its execution. It has recently been shown that a given state predicate can be monitored consistently by a set of crash-prone asynchronous distributed monitors, only if sufficiently many different verdicts can be emitted by each monitor. We revisit this impossibility result in the context of LTL semantics for RV. We show that employing the four-valued logic Rv-LTL will result in inconsistent distributed monitoring for some formulas. Our first main contribution is a family of logics, called Ltl2k+4, that refines Rv-Ltl incorporating 2k + 4 truth values, for each k >= 0. The truth values of Ltl2k+4 can be effectively used by each monitor to reach a consistent global set of verdicts for each given formula, provided k is sufficiently large. Our second main contribution is an algorithm for monitor construction enabling fault-tolerant distributed monitoring based on the aggregation of the individual verdicts by each monitor.
Cite as

Borzoo Bonakdarpour, Pierre Fraigniaud, Sergio Rajsbaum, David A. Rosenblueth, and Corentin Travers. Decentralized Asynchronous Crash-Resilient Runtime Verification. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bonakdarpour_et_al:LIPIcs.CONCUR.2016.16,
  author =	{Bonakdarpour, Borzoo and Fraigniaud, Pierre and Rajsbaum, Sergio and Rosenblueth, David A. and Travers, Corentin},
  title =	{{Decentralized Asynchronous Crash-Resilient Runtime Verification}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Desharnais, Jos\'{e}e and Jagadeesan, Radha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.16},
  URN =		{urn:nbn:de:0030-drops-61856},
  doi =		{10.4230/LIPIcs.CONCUR.2016.16},
  annote =	{Keywords: Runtime monitoring, Distributed algorithms, Fault-tolerance}
}
  • Refine by Type
  • 6 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2019
  • 1 2016

  • Refine by Author
  • 3 Travers, Corentin
  • 2 Fraigniaud, Pierre
  • 2 Milani, Alessia
  • 1 Anta, Antonio Fernández
  • 1 Attiya, Hagit
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Distributed algorithms
  • 1 Computer systems organization → Dependable and fault-tolerant systems and networks
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Networks → Network properties
  • 1 Theory of computation → Concurrent algorithms
  • Show More...

  • Refine by Keyword
  • 1 Agreement problem
  • 1 Amortized Complexity
  • 1 Approximate Agreement
  • 1 Asynchronous system
  • 1 Auditability
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact