2 Search Results for "Felber, David"

Document
DOI: 10.4230/LIPIcs.OPODIS.2019.16
On Deterministic Linearizable Set Agreement Objects

Authors: Felipe de Azevedo Piovezan, Vassos Hadzilacos, and Sam Toueg

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
A recent work showed that, for all n and k, there is a linearizable (n,k)-set agreement object O_L that is equivalent to the (n,k)-set agreement task [David Yu Cheng Chan et al., 2017]: given O_L, it is possible to solve the (n,k)-set agreement task, and given any algorithm that solves the (n,k)-set agreement task (and registers), it is possible to implement O_L. This linearizable object O_L, however, is not deterministic. It turns out that there is also a deterministic (n,k)-set agreement object O_D that is equivalent to the (n,k)-set agreement task, but this deterministic object O_D is not linearizable. This raises the question whether there exists a deterministic and linearizable (n,k)-set agreement object that is equivalent to the (n,k)-set agreement task. Here we show that in general the answer is no: specifically, we prove that for all n ≥ 4, every deterministic linearizable (n,2)-set agreement object is strictly stronger than the (n,2)-set agreement task. We prove this by showing that, for all n ≥ 4, every deterministic and linearizable (n,2)-set agreement object (together with registers) can be used to solve 2-consensus, whereas it is known that the (n,2)-set agreement task cannot do so. For a natural subset of (n,2)-set agreement objects, we prove that this result holds even for n = 3.
Cite as

Felipe de Azevedo Piovezan, Vassos Hadzilacos, and Sam Toueg. On Deterministic Linearizable Set Agreement Objects. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{deazevedopiovezan_et_al:LIPIcs.OPODIS.2019.16,
  author =	{de Azevedo Piovezan, Felipe and Hadzilacos, Vassos and Toueg, Sam},
  title =	{{On Deterministic Linearizable Set Agreement Objects}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.16},
  URN =		{urn:nbn:de:0030-drops-118026},
  doi =		{10.4230/LIPIcs.OPODIS.2019.16},
  annote =	{Keywords: Asynchronous shared-memory systems, consensus, set agreement, deterministic objects}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.775
A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words

Authors: David Felber and Rafail Ostrovsky

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
A quantile summary is a data structure that approximates to epsilon-relative error the order statistics of a much larger underlying dataset. In this paper we develop a randomized online quantile summary for the cash register data input model and comparison data domain model that uses O((1/epsilon) log(1/epsilon)) words of memory. This improves upon the previous best upper bound of O((1/epsilon) (log(1/epsilon))^(3/2)) by Agarwal et al. (PODS 2012). Further, by a lower bound of Hung and Ting (FAW 2010) no deterministic summary for the comparison model can outperform our randomized summary in terms of space complexity. Lastly, our summary has the nice property that O((1/epsilon) log(1/epsilon)) words suffice to ensure that the success probability is 1 - exp(-poly(1/epsilon)).
Cite as

David Felber and Rafail Ostrovsky. A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 775-785, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{felber_et_al:LIPIcs.APPROX-RANDOM.2015.775,
  author =	{Felber, David and Ostrovsky, Rafail},
  title =	{{A Randomized Online Quantile Summary in O(1/epsilon * log(1/epsilon)) Words}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{775--785},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.775},
  URN =		{urn:nbn:de:0030-drops-53357},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.775},
  annote =	{Keywords: order statistics, data stream, streaming algorithm}
}
  • Refine by Author
  • 1 Felber, David
  • 1 Hadzilacos, Vassos
  • 1 Ostrovsky, Rafail
  • 1 Toueg, Sam
  • 1 de Azevedo Piovezan, Felipe

  • Refine by Classification
  • 1 Theory of computation → Concurrency
  • 1 Theory of computation → Distributed computing models
  • 1 Theory of computation → Parallel computing models

  • Refine by Keyword
  • 1 Asynchronous shared-memory systems
  • 1 consensus
  • 1 data stream
  • 1 deterministic objects
  • 1 order statistics
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2020

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