Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size

Wan Fokkink; Guus Samsom

doi:10.1007/978-3-030-31175-9_1

Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size

Wan Fokkink^*, Guus Samsom

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Chapter › Academic › peer-review

148 Downloads (Pure)

Abstract

We propose two adaptations of the probabilistic Itai-Rodeh algorithm for computing the size of an anonymous asynchronous ring. This Monte Carlo algorithm (inevitably) allows for wrong outcomes. Our adaptations reduce the chance that this happens. Furthermore, we propose a new algorithm that has a better message complexity.

Original language	English
Title of host publication	The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy
Subtitle of host publication	Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday
Editors	Mário S. Alvim, Kostas Chatzikokolakis, Carlos Olarte, Frank Valencia
Publisher	Springer Verlag
Pages	3-13
Number of pages	11
ISBN (Electronic)	9783030311759
ISBN (Print)	9783030311742
DOIs	https://doi.org/10.1007/978-3-030-31175-9_1
Publication status	Published - 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11760 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/978-3-030-31175-9_1

Fokkink-Samsom2019_Chapter_VariationsOfTheItai-RodehAlgorithmForComputingAnonymousRingSizeFinal published version, 357 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

Fokkink, W., & Samsom, G. (2019). Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size. In M. S. Alvim, K. Chatzikokolakis, C. Olarte, & F. Valencia (Eds.), The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy: Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday (pp. 3-13). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11760 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-31175-9_1

Fokkink, Wan ; Samsom, Guus. / Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size. The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy: Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday. editor / Mário S. Alvim ; Kostas Chatzikokolakis ; Carlos Olarte ; Frank Valencia. Springer Verlag, 2019. pp. 3-13 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{0208ed9bb998459c859cb99677fc95e1,

title = "Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size",

abstract = "We propose two adaptations of the probabilistic Itai-Rodeh algorithm for computing the size of an anonymous asynchronous ring. This Monte Carlo algorithm (inevitably) allows for wrong outcomes. Our adaptations reduce the chance that this happens. Furthermore, we propose a new algorithm that has a better message complexity.",

author = "Wan Fokkink and Guus Samsom",

year = "2019",

doi = "10.1007/978-3-030-31175-9_1",

language = "English",

isbn = "9783030311742",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "3--13",

editor = "Alvim, {M{\'a}rio S.} and Kostas Chatzikokolakis and Carlos Olarte and Frank Valencia",

booktitle = "The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy",

address = "Germany",

}

Fokkink, W & Samsom, G 2019, Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size. in MS Alvim, K Chatzikokolakis, C Olarte & F Valencia (eds), The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy: Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11760 LNCS, Springer Verlag, pp. 3-13. https://doi.org/10.1007/978-3-030-31175-9_1

Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size. / Fokkink, Wan; Samsom, Guus.
The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy: Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday. ed. / Mário S. Alvim; Kostas Chatzikokolakis; Carlos Olarte; Frank Valencia. Springer Verlag, 2019. p. 3-13 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11760 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size

AU - Fokkink, Wan

AU - Samsom, Guus

PY - 2019

Y1 - 2019

N2 - We propose two adaptations of the probabilistic Itai-Rodeh algorithm for computing the size of an anonymous asynchronous ring. This Monte Carlo algorithm (inevitably) allows for wrong outcomes. Our adaptations reduce the chance that this happens. Furthermore, we propose a new algorithm that has a better message complexity.

AB - We propose two adaptations of the probabilistic Itai-Rodeh algorithm for computing the size of an anonymous asynchronous ring. This Monte Carlo algorithm (inevitably) allows for wrong outcomes. Our adaptations reduce the chance that this happens. Furthermore, we propose a new algorithm that has a better message complexity.

UR - http://www.scopus.com/inward/record.url?scp=85075075598&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075075598&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-31175-9_1

DO - 10.1007/978-3-030-31175-9_1

M3 - Chapter

AN - SCOPUS:85075075598

SN - 9783030311742

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 13

BT - The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy

A2 - Alvim, Mário S.

A2 - Chatzikokolakis, Kostas

A2 - Olarte, Carlos

A2 - Valencia, Frank

PB - Springer Verlag

ER -

Fokkink W, Samsom G. Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size. In Alvim MS, Chatzikokolakis K, Olarte C, Valencia F, editors, The Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy: Essays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday. Springer Verlag. 2019. p. 3-13. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2019 Nov 4. doi: 10.1007/978-3-030-31175-9_1

Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size

Abstract

Publication series

UN SDGs

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this