A Note on the Message Complexity of Cidon’s Distributed Depth-First Search Algorithm

Saidgani Musaev; Wan Fokkink

doi:10.1007/978-3-031-15629-8_24

A Note on the Message Complexity of Cidon’s Distributed Depth-First Search Algorithm

Saidgani Musaev, Wan Fokkink^*

^*Corresponding author for this work

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

109 Downloads (Pure)

Abstract

The same distributed depth-first search algorithm was proposed independently by Lakshmanan, Meenakshi, and Thulasiraman, who gave 4 E- N as upper bound on the worst-case message complexity of the algorithm, and by Cidon, who gave 3E as upper bound. We determine the exact worst-case message complexity and show that the upper bound of 3E by Cidon is too strict.

Original language	English
Title of host publication	A Journey from Process Algebra via Timed Automata to Model Learning
Subtitle of host publication	Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday
Editors	Nils Jansen, Mariëlle Stoelinga, Petra van den Bos
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	467-471
Number of pages	5
ISBN (Electronic)	9783031156298
ISBN (Print)	9783031156281
DOIs	https://doi.org/10.1007/978-3-031-15629-8_24
Publication status	Published - 2022

Publication series

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

Bibliographical note

Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Access to Document

10.1007/978-3-031-15629-8_24

A Note on the Message Complexity of Cidon’s Distributed Depth-First Search AlgorithmFinal published version, 230 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

Musaev, S., & Fokkink, W. (2022). A Note on the Message Complexity of Cidon’s Distributed Depth-First Search Algorithm. In N. Jansen, M. Stoelinga, & P. van den Bos (Eds.), A Journey from Process Algebra via Timed Automata to Model Learning: Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday (pp. 467-471). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13560 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-15629-8_24

Musaev, Saidgani ; Fokkink, Wan. / A Note on the Message Complexity of Cidon’s Distributed Depth-First Search Algorithm. A Journey from Process Algebra via Timed Automata to Model Learning: Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday. editor / Nils Jansen ; Mariëlle Stoelinga ; Petra van den Bos. Springer Science and Business Media Deutschland GmbH, 2022. pp. 467-471 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{72ee2a73d099465597cd106d88ba0cbf,

title = "A Note on the Message Complexity of Cidon{\textquoteright}s Distributed Depth-First Search Algorithm",

abstract = "The same distributed depth-first search algorithm was proposed independently by Lakshmanan, Meenakshi, and Thulasiraman, who gave 4 E- N as upper bound on the worst-case message complexity of the algorithm, and by Cidon, who gave 3E as upper bound. We determine the exact worst-case message complexity and show that the upper bound of 3E by Cidon is too strict.",

author = "Saidgani Musaev and Wan Fokkink",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.",

year = "2022",

doi = "10.1007/978-3-031-15629-8\_24",

language = "English",

isbn = "9783031156281",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "467--471",

editor = "Nils Jansen and Mari{\"e}lle Stoelinga and \{van den Bos\}, Petra",

booktitle = "A Journey from Process Algebra via Timed Automata to Model Learning",

address = "Germany",

}

Musaev, S & Fokkink, W 2022, A Note on the Message Complexity of Cidon’s Distributed Depth-First Search Algorithm. in N Jansen, M Stoelinga & P van den Bos (eds), A Journey from Process Algebra via Timed Automata to Model Learning: Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13560 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 467-471. https://doi.org/10.1007/978-3-031-15629-8_24

A Note on the Message Complexity of Cidon’s Distributed Depth-First Search Algorithm. / Musaev, Saidgani; Fokkink, Wan.
A Journey from Process Algebra via Timed Automata to Model Learning: Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday. ed. / Nils Jansen; Mariëlle Stoelinga; Petra van den Bos. Springer Science and Business Media Deutschland GmbH, 2022. p. 467-471 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13560 LNCS).

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

TY - CHAP

T1 - A Note on the Message Complexity of Cidon’s Distributed Depth-First Search Algorithm

AU - Musaev, Saidgani

AU - Fokkink, Wan

PY - 2022

Y1 - 2022

N2 - The same distributed depth-first search algorithm was proposed independently by Lakshmanan, Meenakshi, and Thulasiraman, who gave 4 E- N as upper bound on the worst-case message complexity of the algorithm, and by Cidon, who gave 3E as upper bound. We determine the exact worst-case message complexity and show that the upper bound of 3E by Cidon is too strict.

AB - The same distributed depth-first search algorithm was proposed independently by Lakshmanan, Meenakshi, and Thulasiraman, who gave 4 E- N as upper bound on the worst-case message complexity of the algorithm, and by Cidon, who gave 3E as upper bound. We determine the exact worst-case message complexity and show that the upper bound of 3E by Cidon is too strict.

UR - https://www.scopus.com/pages/publications/85138163871

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

U2 - 10.1007/978-3-031-15629-8_24

DO - 10.1007/978-3-031-15629-8_24

M3 - Chapter

AN - SCOPUS:85138163871

SN - 9783031156281

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

SP - 467

EP - 471

BT - A Journey from Process Algebra via Timed Automata to Model Learning

A2 - Jansen, Nils

A2 - Stoelinga, Mariëlle

A2 - van den Bos, Petra

PB - Springer Science and Business Media Deutschland GmbH

ER -

Musaev S, Fokkink W. A Note on the Message Complexity of Cidon’s Distributed Depth-First Search Algorithm. In Jansen N, Stoelinga M, van den Bos P, editors, A Journey from Process Algebra via Timed Automata to Model Learning: Essays Dedicated to Frits Vaandrager on the Occasion of His 60th Birthday. Springer Science and Business Media Deutschland GmbH. 2022. p. 467-471. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2022 Sept 7. doi: 10.1007/978-3-031-15629-8_24