Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-030-57675-2_24
Title: On the power of randomization in distributed algorithms in dynamic networks with adaptive adversaries
Authors: I. Jahja 
H. Yu 
R. Hou 
Keywords: Adversaries
Dynamic networks
Power of randomization
Issue Date: Aug-2020
Publisher: Springer
Citation: I. Jahja, H. Yu, R. Hou (2020-08). On the power of randomization in distributed algorithms in dynamic networks with adaptive adversaries. International European Conference on Parallel and Distributed Computing (Euro-Par), Aug 2020 12247 : 376 - 391. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-030-57675-2_24
Abstract: This paper investigates the power of randomization in general distributed algorithms in dynamic networks where the network’s topology may evolve over time, as determined by some adaptive adversary. In such a context, randomization may help algorithms to better deal with i) “bad” inputs to the algorithm, and ii) evolving topologies generated by “bad” adaptive adversaries. We prove that randomness offers limited power to better deal with “bad” adaptive adversary. We define a simple notion of prophetic adversary for determining the evolving topologies. Such an adversary accurately predicts all randomness in the algorithm beforehand, and hence the randomness will be useless against “bad” prophetic adversaries. Given a randomized algorithm P whose time complexity satisfies some mild conditions, we prove that P can always be converted to a new algorithm Q with comparable time complexity, even when Q runs against prophetic adversaries. This implies that the benefit of P using randomness for dealing with the adaptive adversaries is limited.
Source Title: International European Conference on Parallel and Distributed Computing (Euro-Par), Aug 2020
URI: https://scholarbank.nus.edu.sg/handle/10635/186040
ISBN: 9783030576745
ISSN: 03029743
DOI: 10.1007/978-3-030-57675-2_24
Appears in Collections:Elements
Staff Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
1. derandomize-europar20-tr.pdf424.38 kBAdobe PDF

OPEN

Post-printView/Download

Page view(s)

190
checked on Feb 2, 2023

Download(s)

5
checked on Feb 2, 2023

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.