DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2024.13

Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory

Authors: Jérémie Chalopin, Shantanu Das, and Maria Kokkou

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract

The problem of electing a unique leader is central to all distributed systems, including programmable matter systems where particles have constant size memory. In this paper, we present a silent self-stabilising, deterministic, stationary, election algorithm for particles having constant memory, assuming that the system is simply connected. Our algorithm is elegant and simple, and requires constant memory per particle. We prove that our algorithm always stabilises to a configuration with a unique leader, under a daemon satisfying some fairness guarantees (Gouda fairness [Mohamed G. Gouda, 2001]). We use the special geometric properties of programmable matter in 2D triangular grids to obtain the first self-stabilising algorithm for such systems. This result is surprising since it is known that silent self-stabilising algorithms for election in general distributed networks require Ω(log n) bits of memory per node, even for ring topologies [Shlomi Dolev et al., 1999].

Cite as

Jérémie Chalopin, Shantanu Das, and Maria Kokkou. Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.DISC.2024.13,
  author =	{Chalopin, J\'{e}r\'{e}mie and Das, Shantanu and Kokkou, Maria},
  title =	{{Deterministic Self-Stabilising Leader Election for Programmable Matter with Constant Memory}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.13},
  URN =		{urn:nbn:de:0030-drops-212395},
  doi =		{10.4230/LIPIcs.DISC.2024.13},
  annote =	{Keywords: Leader Election, Programmable Matter, Self-Stabilisation, Silent, Deterministic, Unique Leader, Simply Connected, Gouda fair Daemon, Constant Memory}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2019.43

Brief Announcement: Neighborhood Mutual Remainder and Its Self-Stabilizing Implementation of Look-Compute-Move Robots

Authors: Shlomi Dolev, Sayaka Kamei, Yoshiaki Katayama, Fukuhito Ooshita, and Koichi Wada

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

Abstract

In this paper, we define a new concept neighborhood mutual remainder (NMR). An NMR distributed algorithms should satisfy global fairness, l-exclusion and repeated local rendezvous requirements. We give a simple self-stabilizing algorithm to demonstrate the design paradigm to achieve NMR, and also present applications of NMR to a Look-Compute-Move robot system.

Cite as

Shlomi Dolev, Sayaka Kamei, Yoshiaki Katayama, Fukuhito Ooshita, and Koichi Wada. Brief Announcement: Neighborhood Mutual Remainder and Its Self-Stabilizing Implementation of Look-Compute-Move Robots. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dolev_et_al:LIPIcs.DISC.2019.43,
  author =	{Dolev, Shlomi and Kamei, Sayaka and Katayama, Yoshiaki and Ooshita, Fukuhito and Wada, Koichi},
  title =	{{Brief Announcement: Neighborhood Mutual Remainder and Its Self-Stabilizing Implementation of Look-Compute-Move Robots}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{43:1--43:3},
  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.43},
  URN =		{urn:nbn:de:0030-drops-113504},
  doi =		{10.4230/LIPIcs.DISC.2019.43},
  annote =	{Keywords: neighborhood mutual remainder, self-stabilization, LCM robot}
}

Document

DOI: 10.4230/DagSemProc.09371.4

On the Fairness of Probabilistic Schedulers for Population Protocols

Authors: Ioannis Chatzigiannakis, Shlomi Dolev, Sándor Fekete, Othon Michail, and Paul Spirakis

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract

We propose a novel, generic definition of emph{probabilistic schedulers} for population protocols. We design two new schedulers, the emph{State Scheduler} and the emph{Transition Function Scheduler}. Both possess the significant capability of being emph{protocol-aware}, i.e. they can assign transition probabilities based on information concerning the underlying protocol. We prove that the proposed schedulers, and also the emph{Random Scheduler} that was defined by Angluin et al. cite{AADFP04}, are all fair with probability $1$. We also define and study emph{equivalence} between schedulers w.r.t. emph{performance} and emph{correctness} and prove that there exist fair probabilistic schedulers that are not equivalent w.r.t. to performance and others that are not equivalent w.r.t. correctness. We implement our schedulers using a new tool for simulating population protocols and evaluate their performance from the viewpoint of experimental analysis and verification. We study three representative protocols to verify stability, and compare the experimental time to convergence with the known complexity bounds. We run our experiments from very small to extremely large populations (of up to $10^{8}$ agents). We get very promising results both of theoretical and practical interest.

Cite as

Ioannis Chatzigiannakis, Shlomi Dolev, Sándor Fekete, Othon Michail, and Paul Spirakis. On the Fairness of Probabilistic Schedulers for Population Protocols. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chatzigiannakis_et_al:DagSemProc.09371.4,
  author =	{Chatzigiannakis, Ioannis and Dolev, Shlomi and Fekete, S\'{a}ndor and Michail, Othon and Spirakis, Paul},
  title =	{{On the Fairness of Probabilistic Schedulers for Population Protocols}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.4},
  URN =		{urn:nbn:de:0030-drops-24286},
  doi =		{10.4230/DagSemProc.09371.4},
  annote =	{Keywords: Population Protocols, Fairness, Probabilistic Schedulers, Communicating Automata, Sensor Networks, Experimental Evaluation}
}

Document

DOI: 10.4230/DagSemProc.08371.1

08371 Abstracts Collection – Fault-Tolerant Distributed Algorithms on VLSI Chips

Authors: Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract

From September the $7^{\text{th}}$, 2008 to September the $10^{\text{th}}$, 2008 the Dagstuhl Seminar 08371 ``Fault-Tolerant Distributed Algorithms on VLSI Chips '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. The seminar was devoted to exploring whether the wealth of existing fault-tolerant distributed algorithms research can be utilized for meeting the challenges of future-generation VLSI chips. During the seminar, several participants from both the VLSI and distributed algorithms' discipline, presented their current research, and ongoing work and possibilities for collaboration were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid. 08371 Abstracts Collection – Fault-Tolerant Distributed Algorithms on VLSI Chips. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:DagSemProc.08371.1,
  author =	{Charron-Bost, Bernadette and Dolev, Shlomi and Ebergen, Jo and Schmid, Ulrich},
  title =	{{08371 Abstracts Collection – Fault-Tolerant Distributed Algorithms on VLSI Chips }},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.1},
  URN =		{urn:nbn:de:0030-drops-19283},
  doi =		{10.4230/DagSemProc.08371.1},
  annote =	{Keywords: Fault-tolerant distributed algorithms, fault tolerance, VLSI systems-on-chip, synchronous vs.\backslash asynchronous circuits, digital logic, specifications}
}

Document

DOI: 10.4230/DagSemProc.08371.2

08371 Summary – Fault-Tolerant Distributed Algorithms on VLSI Chips

Authors: Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract

Chips was devoted to exploring whether the wealth of existing fault-tolerant distributed algorithms research can be utilized for meeting the challenges of future-generation VLSI chips. Participants from both the distributed fault-tolerant algorithms community, interested in this emerging application domain, and from the VLSI systems-on-chip and digital design community, interested in well-founded system-level approaches to fault-tolerance, surveyed the current state-of-the-art and tried to identify possibilities to work together. The seminar clearly achieved its purpose: It became apparent that most existing research in Distributed Algorithms is too heavy-weight for being immediately applied in the “core” VLSI design context, where power, area etc. are scarce resources. At the same time, however, it was recognized that emerging trends like large multicore chips and increasingly critical applications create new and promising application domains for fault-tolerant distributed algorithms. We are convinced that the very fruitful cross-community interactions that took place during the Dagstuhl seminar will contribute to new research activities in those areas.

Cite as

Bernadette Charron-Bost, Shlomi Dolev, Jo Ebergen, and Ulrich Schmid. 08371 Summary – Fault-Tolerant Distributed Algorithms on VLSI Chips. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{charronbost_et_al:DagSemProc.08371.2,
  author =	{Charron-Bost, Bernadette and Dolev, Shlomi and Ebergen, Jo and Schmid, Ulrich},
  title =	{{08371 Summary – Fault-Tolerant Distributed Algorithms on VLSI Chips }},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.2},
  URN =		{urn:nbn:de:0030-drops-19270},
  doi =		{10.4230/DagSemProc.08371.2},
  annote =	{Keywords: Fault-tolerant distributed algorithms, fault tolerance, VLSI systemson- chip, synchronous vs. asynchronous circuits, digital logic, specifications}
}

Document

DOI: 10.4230/DagSemProc.08371.3

Error Containment in the Presence of Metastability

Authors: Andreas Steininger

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract

Error containment is an important concept in fault tolerant system design, and techniques like voting are applied to mask erroneous outputs, thus preventing their propagation. In this presentation we will use the example of DARTS, a fault-tolerant distributed clock generation scheme in hardware, to demonstrate that metastability is a substantial threat to error containment. We will illustrate how metastability can originate and propagate such that a single fault may upset the system. The main conclusion is that modeling efforts on all design levels are definitely required in order to mitigate and quantify the deteriorating effect of metastability on system dependability.

Cite as

Andreas Steininger. Error Containment in the Presence of Metastability. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{steininger:DagSemProc.08371.3,
  author =	{Steininger, Andreas},
  title =	{{Error Containment in the Presence of Metastability}},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.3},
  URN =		{urn:nbn:de:0030-drops-19235},
  doi =		{10.4230/DagSemProc.08371.3},
  annote =	{Keywords: Metastability, fault tolerance, clock generation}
}

Document

DOI: 10.4230/DagSemProc.08371.4

Implications of VLSI Fault Models and Distributed Systems Failure Models – A hardware designer's view

Authors: Gottfried Fuchs

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract

The fault and failure models as well as their semantics within the VLSI and the distributed systems/algorithms community are quite different. Pointing out the mismatch of those fault respectively failure models is the main part of this work. The impact of the implemented failure model in terms of hardware effort and system complexity will be shown on different VLSI implementations of distributed algorithms. However, still, there are a lot of open questions left mostly related to the coverage analysis of hardware implemented fault-tolerant algorithms.

Cite as

Gottfried Fuchs. Implications of VLSI Fault Models and Distributed Systems Failure Models – A hardware designer's view. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{fuchs:DagSemProc.08371.4,
  author =	{Fuchs, Gottfried},
  title =	{{Implications of VLSI Fault Models and Distributed Systems Failure Models – A hardware designer's view}},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.4},
  URN =		{urn:nbn:de:0030-drops-19245},
  doi =		{10.4230/DagSemProc.08371.4},
  annote =	{Keywords: VLSI, fault model, distributed system, failure model}
}

Document

DOI: 10.4230/DagSemProc.08371.5

Methods and Metrics for Reliability Assessment

Authors: Lirida Alves de Barros-Naviner, Jean-François Naviner, Denis Teixeira Franco, and Mai Correia de Vasconcelos

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract

This paper deals with digital VLSI design aspects related to reliability. The focus is on the problem of reliability evaluation in combinational logic circuits.We present some methods for this evaluation that can be easily integrated in a tradidional design flow. Also we describe suitable metrics for performance estimation of concurrent error detection schemes.

Cite as

Lirida Alves de Barros-Naviner, Jean-François Naviner, Denis Teixeira Franco, and Mai Correia de Vasconcelos. Methods and Metrics for Reliability Assessment. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{alvesdebarrosnaviner_et_al:DagSemProc.08371.5,
  author =	{Alves de Barros-Naviner, Lirida and Naviner, Jean-Fran\c{c}ois and Teixeira Franco, Denis and Correia de Vasconcelos, Mai},
  title =	{{Methods and Metrics for Reliability Assessment}},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.5},
  URN =		{urn:nbn:de:0030-drops-19252},
  doi =		{10.4230/DagSemProc.08371.5},
  annote =	{Keywords: Reliability, fault tolerance, combinational logic}
}

Document

DOI: 10.4230/DagSemProc.08371.6

Multiple Event Upsets Aware FPGAs Using Protected Schemes

Authors: Costas Argyrides and Dhiraj K. Pradhan

Published in: Dagstuhl Seminar Proceedings, Volume 8371, Fault-Tolerant Distributed Algorithms on VLSI Chips (2009)

Abstract

Multiple upsets would be available in SRAM-based FPGAs which utilizes SRAM in different parts to implement circuit configuration and to implement circuit data. Moreover, configuration bits of SRAM-based FPGAs are more sensible to upsets compared to circuit data due to significant number of SRAM bits. In this paper, a new protected Configurable Logic Block (CLB) and FPGA architecture are proposed which utilize multiple error correction (DEC) and multiple error detection. This is achieved by the incorporation of recently proposed coding technique Matrix codes [1] inside the FPGA. The power and area analysis of the proposed techniques show that these methods are more efficient than the traditional schemes such as duplication with comparison and TMR circuit design in the FPGAs.

Cite as

Costas Argyrides and Dhiraj K. Pradhan. Multiple Event Upsets Aware FPGAs Using Protected Schemes. In Fault-Tolerant Distributed Algorithms on VLSI Chips. Dagstuhl Seminar Proceedings, Volume 8371, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{argyrides_et_al:DagSemProc.08371.6,
  author =	{Argyrides, Costas and Pradhan, Dhiraj K.},
  title =	{{Multiple Event Upsets Aware FPGAs Using Protected Schemes}},
  booktitle =	{Fault-Tolerant Distributed Algorithms on VLSI Chips},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8371},
  editor =	{Bernadette Charron-Bost and Shlomi Dolev and Jo Ebergen and Ulrich Schmid},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08371.6},
  URN =		{urn:nbn:de:0030-drops-19261},
  doi =		{10.4230/DagSemProc.08371.6},
  annote =	{Keywords: FPGA, SEUs, ECC, Reliability, MTTF}
}

Document

DOI: 10.4230/DagSemProc.05411.1

05411 Abstracts Collection – Anonymous Communication and its Applications

Authors: Shlomi Dolev, Andreas Pfitzmann, and Rafail Ostrovsky

Published in: Dagstuhl Seminar Proceedings, Volume 5411, Anonymous Communication and its Applications (2006)

Abstract

From 09.10.05 to 14.10.05, the Dagstuhl Seminar 05411 ``Anonymous Communication and its Applications'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Shlomi Dolev, Andreas Pfitzmann, and Rafail Ostrovsky. 05411 Abstracts Collection – Anonymous Communication and its Applications. In Anonymous Communication and its Applications. Dagstuhl Seminar Proceedings, Volume 5411, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{dolev_et_al:DagSemProc.05411.1,
  author =	{Dolev, Shlomi and Pfitzmann, Andreas and Ostrovsky, Rafail},
  title =	{{05411 Abstracts Collection – Anonymous Communication and its Applications}},
  booktitle =	{Anonymous Communication and its Applications},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5411},
  editor =	{Shlomi Dolev and Rafail Ostrovsky and Andreas Pfitzmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05411.1},
  URN =		{urn:nbn:de:0030-drops-7950},
  doi =		{10.4230/DagSemProc.05411.1},
  annote =	{Keywords: Anonymous Communication, Cryptography, Privacy, Security, Anonymity}
}

Document

DOI: 10.4230/DagSemProc.05411.2

Anonymity Metrics Revisited

Authors: Claudia Diaz

Published in: Dagstuhl Seminar Proceedings, Volume 5411, Anonymous Communication and its Applications (2006)

Abstract

In 2001, two information theoretic anonymity metrics were proposed: the "effective anonymity set size" and the "degree of anonymity". In this talk, we propose an abstract model for a general anonymity system which is consistent with the definition of anonymity on which the metrics are based. We revisit entropy-based anonymity metrics, and we apply them to Crowds, a practical anonymity system. We discuss the differences between the two metrics and the results obtained in the example.

Cite as

Claudia Diaz. Anonymity Metrics Revisited. In Anonymous Communication and its Applications. Dagstuhl Seminar Proceedings, Volume 5411, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{diaz:DagSemProc.05411.2,
  author =	{Diaz, Claudia},
  title =	{{Anonymity Metrics Revisited}},
  booktitle =	{Anonymous Communication and its Applications},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5411},
  editor =	{Shlomi Dolev and Rafail Ostrovsky and Andreas Pfitzmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05411.2},
  URN =		{urn:nbn:de:0030-drops-4833},
  doi =		{10.4230/DagSemProc.05411.2},
  annote =	{Keywords: Anonymity, metrics, entropy}
}

Document

DOI: 10.4230/DagSemProc.05411.3

Improving the Decoding Efficiency of Private Search

Authors: George Danezis and Claudia Diaz

Published in: Dagstuhl Seminar Proceedings, Volume 5411, Anonymous Communication and its Applications (2006)

Abstract

We show two ways of recovering all matching documents, in the Ostrovsky et al. Private Search, while requiring considerably shorter buffers. Both schemes rely on the fact that documents colliding in a buffer position provide the sum of their plaintexts. Efficient decoding algorithms can make use of this property to recover documents never present alone in a buffer position.

Cite as

George Danezis and Claudia Diaz. Improving the Decoding Efficiency of Private Search. In Anonymous Communication and its Applications. Dagstuhl Seminar Proceedings, Volume 5411, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{danezis_et_al:DagSemProc.05411.3,
  author =	{Danezis, George and Diaz, Claudia},
  title =	{{Improving the Decoding Efficiency of Private Search}},
  booktitle =	{Anonymous Communication and its Applications},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5411},
  editor =	{Shlomi Dolev and Rafail Ostrovsky and Andreas Pfitzmann},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05411.3},
  URN =		{urn:nbn:de:0030-drops-4829},
  doi =		{10.4230/DagSemProc.05411.3},
  annote =	{Keywords: Private search, private information retrieval, cryptography}
}

Document

DOI: 10.4230/DagSemRep.290

Self-Stabilization (Dagstuhl Seminar 00431)

Authors: Anish Arora, Joffroy Beauquier, Shlomi Dolev, Ted Herman, and Willem-Paul de Roever

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract

Cite as

Anish Arora, Joffroy Beauquier, Shlomi Dolev, Ted Herman, and Willem-Paul de Roever. Self-Stabilization (Dagstuhl Seminar 00431). Dagstuhl Seminar Report 290, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{arora_et_al:DagSemRep.290,
  author =	{Arora, Anish and Beauquier, Joffroy and Dolev, Shlomi and Herman, Ted and de Roever, Willem-Paul},
  title =	{{Self-Stabilization (Dagstuhl Seminar 00431)}},
  pages =	{1--17},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{290},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.290},
  URN =		{urn:nbn:de:0030-drops-151744},
  doi =		{10.4230/DagSemRep.290},
}

Document

DOI: 10.4230/DagSemRep.220

Self-Stabilization (Dagstuhl Seminar 98331)

Authors: Anish Arora, Shlomi Dolev, and Willem-Paul de Roever

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract

Cite as

Anish Arora, Shlomi Dolev, and Willem-Paul de Roever. Self-Stabilization (Dagstuhl Seminar 98331). Dagstuhl Seminar Report 220, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1998)

Copy BibTex To Clipboard

@TechReport{arora_et_al:DagSemRep.220,
  author =	{Arora, Anish and Dolev, Shlomi and de Roever, Willem-Paul},
  title =	{{Self-Stabilization (Dagstuhl Seminar 98331)}},
  pages =	{1--17},
  ISSN =	{1619-0203},
  year =	{1998},
  type = 	{Dagstuhl Seminar Report},
  number =	{220},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.220},
  URN =		{urn:nbn:de:0030-drops-151066},
  doi =		{10.4230/DagSemRep.220},
}

14 Search Results for "Dolev, Shlomi"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message