Search Results

Documents authored by 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.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}
}
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