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 proceedingChapterAcademicpeer-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 languageEnglish
Title of host publicationThe Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy
Subtitle of host publicationEssays Dedicated to Catuscia Palamidessi on the Occasion of Her 60th Birthday
EditorsMário S. Alvim, Kostas Chatzikokolakis, Carlos Olarte, Frank Valencia
PublisherSpringer Verlag
Pages3-13
Number of pages11
ISBN (Electronic)9783030311759
ISBN (Print)9783030311742
DOIs
Publication statusPublished - 2019

Publication series

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

Fingerprint

Dive into the research topics of 'Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size'. Together they form a unique fingerprint.

Cite this