Search Results

Documents authored by Dolev, Shlomi

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.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/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},
}
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 About DROPS Imprint Privacy Contact