Search Results

Documents authored by Milani, Alessia

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.4
The Synchronization Power of Auditable Registers

Authors: Hagit Attiya, Antonella Del Pozzo, Alessia Milani, Ulysse Pavloff, and Alexandre Rapetti

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
Auditability allows to track all the read operations performed on a register. It abstracts the need of data owners to control access to their data, tracking who read which information. This work considers possible formalizations of auditing and their ramification for the possibility of providing it. The natural definition is to require a linearization of all write, read and audit operations together (atomic auditing). The paper shows that atomic auditing is a powerful tool, as it can be used to solve consensus. The number of processes that can solve consensus using atomic audit depends on the number of processes that can read or audit the register. If there is a single reader or a single auditor (the writer), then consensus can be solved among two processes. If multiple readers and auditors are possible, then consensus can be solved among the same number of processes. This means that strong synchronization primitives are needed to support atomic auditing. We give implementations of atomic audit when there are either multiple readers or multiple auditors (but not both) using primitives with consensus number 2 (swap and fetch&add). When there are multiple readers and multiple auditors, the implementation uses compare&swap. These findings motivate a weaker definition, in which audit operations are not linearized together with read and write operations (regular auditing). We prove that regular auditing can be implemented from ordinary reads and writes on atomic registers.
Cite as

Hagit Attiya, Antonella Del Pozzo, Alessia Milani, Ulysse Pavloff, and Alexandre Rapetti. The Synchronization Power of Auditable Registers. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{attiya_et_al:LIPIcs.OPODIS.2023.4,
  author =	{Attiya, Hagit and Del Pozzo, Antonella and Milani, Alessia and Pavloff, Ulysse and Rapetti, Alexandre},
  title =	{{The Synchronization Power of Auditable Registers}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.4},
  URN =		{urn:nbn:de:0030-drops-194940},
  doi =		{10.4230/LIPIcs.OPODIS.2023.4},
  annote =	{Keywords: Auditability, atomic register, fault tolerance, consensus number}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.4
Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers

Authors: Colette Johnen, Adnane Khattabi, and Alessia Milani

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Despite the widespread usage of FIFO queues in distributed applications, designing efficient wait-free implementations of queues remains a challenge. The majority of wait-free queue implementations restrict either the number of dequeuers or the number of enqueuers that can operate on the queue, even when they use strong synchronization primitives, like the Compare&Swap. If we do not limit the number of processes that can perform enqueue and dequeue operations, the best-known upper bound on the worst case step complexity for a wait-free queue is given by [Khanchandani and Wattenhofer, 2018]. In particular, they present an implementation of a multiple dequeuer multiple enqueuer wait-free queue whose worst case step complexity is in O(√n), where n is the number of processes. In this work, we investigate whether it is possible to improve this bound. In particular, we present a wait-free FIFO queue implementation that supports n enqueuers and k dequeuers where the worst case step complexity of an Enqueue operation is in O(log n) and of a Dequeue operation is in O(k log n). Then, we show that if the semantics of the queue can be relaxed, by allowing concurrent Dequeue operations to retrieve the same element, then we can achieve O(log n) worst-case step complexity for both the Enqueue and Dequeue operations.
Cite as

Colette Johnen, Adnane Khattabi, and Alessia Milani. Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{johnen_et_al:LIPIcs.OPODIS.2022.4,
  author =	{Johnen, Colette and Khattabi, Adnane and Milani, Alessia},
  title =	{{Efficient Wait-Free Queue Algorithms with Multiple Enqueuers and Multiple Dequeuers}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.4},
  URN =		{urn:nbn:de:0030-drops-176240},
  doi =		{10.4230/LIPIcs.OPODIS.2022.4},
  annote =	{Keywords: Distributed computing, distributed algorithms, FIFO queue, shared memory, fault tolerance, concurrent data structures, relaxed specifications, complexity}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.OPODIS.2021
LIPIcs, Volume 217, OPODIS 2021, Complete Volume

Authors: Quentin Bramas, Vincent Gramoli, and Alessia Milani

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
LIPIcs, Volume 217, OPODIS 2021, Complete Volume
Cite as

25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 1-580, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Proceedings{bramas_et_al:LIPIcs.OPODIS.2021,
  title =	{{LIPIcs, Volume 217, OPODIS 2021, Complete Volume}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{1--580},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021},
  URN =		{urn:nbn:de:0030-drops-157746},
  doi =		{10.4230/LIPIcs.OPODIS.2021},
  annote =	{Keywords: LIPIcs, Volume 217, OPODIS 2021, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.OPODIS.2021.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Quentin Bramas, Vincent Gramoli, and Alessia Milani

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.OPODIS.2021.0,
  author =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.0},
  URN =		{urn:nbn:de:0030-drops-157752},
  doi =		{10.4230/LIPIcs.OPODIS.2021.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
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.OPODIS.2015.12
On the Uncontended Complexity of Anonymous Consensus

Authors: Claire Capdevielle, Colette Johnen, Petr Kuznetsov, and Alessia Milani

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Consensus is one of the central distributed abstractions. By enabling a collection of processes to agree on one of the values they propose, consensus can be used to implement any generic replicated service in a consistent and fault-tolerant way. In this paper, we study uncontended complexity of anonymous consensus algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that contention-free operations on a consensus object perform "fast" reads and writes, and resort to more expensive synchronization primitives, such as CAS, only when contention is detected. We call such concurrent implementations interval-solo-fast and derive one of the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast consensus.
Cite as

Claire Capdevielle, Colette Johnen, Petr Kuznetsov, and Alessia Milani. On the Uncontended Complexity of Anonymous Consensus. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{capdevielle_et_al:LIPIcs.OPODIS.2015.12,
  author =	{Capdevielle, Claire and Johnen, Colette and Kuznetsov, Petr and Milani, Alessia},
  title =	{{On the Uncontended Complexity of Anonymous Consensus}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.12},
  URN =		{urn:nbn:de:0030-drops-66034},
  doi =		{10.4230/LIPIcs.OPODIS.2015.12},
  annote =	{Keywords: space and time complexity, lower bounds, consensus, interval contention, solo-fast}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.28
A Faster Counting Protocol for Anonymous Dynamic Networks

Authors: Alessia Milani and Miguel A. Mosteiro

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
We study the problem of counting the number of nodes in a slotted-time communication network, under the challenging assumption that nodes do not have identifiers and the network topology changes frequently. That is, for each time slot links among nodes can change arbitrarily provided that the network is always connected. This network model has been motivated by the ongoing development of new communication technologies that enable the deployment of a massive number of devices with highly dynamic connectivity patterns. Tolerating dynamic topologies is clearly crucial in face of mobility and unreliable communication. Current communication networks do have node identifiers though. Nevertheless, in future massive networks, it might be suitable to avoid nodes IDs to facilitate mass production. Consequently, knowing what is the cost of anonymity is of paramount importance to understand what is feasible or not for future generations of Dynamic Networks. Counting is a fundamental task in distributed computing since knowing the size of the system often facilitates the desing of solutions for more complex problems. Also, the size of the system is usually used to decide termination in distributed algorithms. Currently, the best upper bound proved on the running time to compute the exact network size is double-exponential. However, only linear complexity lower bounds are known, leaving open the question of whether efficient Counting protocols for Anonymous Dynamic Networks exist or not. In this paper we make a significant step towards answering this question by presenting a distributed Counting protocol for Anonymous Dynamic Networks which has exponential time complexity. This algorithm, which we call Incremental Counting, ensures that eventually every node knows the exact size of the system and stops executing the protocol. Previous Counting protocols have either double-exponential time complexity, or they are exponential but do not terminate, or terminate but do not provide running-time guarantees, or guarantee only an exponential upper bound on the network size. Other protocols are heuristic and do not guarantee the correct count.
Cite as

Alessia Milani and Miguel A. Mosteiro. A Faster Counting Protocol for Anonymous Dynamic Networks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{milani_et_al:LIPIcs.OPODIS.2015.28,
  author =	{Milani, Alessia and Mosteiro, Miguel A.},
  title =	{{A Faster Counting Protocol for Anonymous Dynamic Networks}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.28},
  URN =		{urn:nbn:de:0030-drops-66179},
  doi =		{10.4230/LIPIcs.OPODIS.2015.28},
  annote =	{Keywords: Anonymous Dynamic Networks, Counting, Time-varying Graphs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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