Options
Stateless information dissemination algorithms
Publikationstyp
Conference Paper
Date Issued
2020-06
Sprache
English
Author(s)
Institut
TORE-URI
First published in
Number in series
12156 LNCS
Start Page
183
End Page
199
Citation
Lecture Notes in Computer Science 12156: 183-199 (2020-06)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Springer
Stateless protocols are advantageous in high volume applications, increasing performance by removing the load caused by retention of session information and by providing crash tolerance. In this paper we present an optimal stateless information dissemination algorithm for synchronous distributed systems. The termination time is considerable lower than that of a recently proposed stateless dissemination protocol. Apart from a special case the new algorithm achieves the minimum possible termination time. The problem of selecting k dissemination nodes with minimal termination time is NP-hard. We prove that unless NP = P there is no approximation algorithm for this problem with approximation ratio 3/2-ε. We also prove for asynchronous systems that deterministic stateless information dissemination is only possible if a large enough part of the message can be updated by each node.
DDC Class
510: Mathematik