TY - GEN
T1 - Heuristically speeding up anonymous dynamic network computations
AU - Halper, Austin
AU - Kowalski, Dariusz R.
AU - Mosteiro, Miguel A.
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/12
Y1 - 2020/12
N2 - Motivated by the current large gap between lower and upper bounds for Counting, i.e. the problem of computing the number of nodes, in Anonymous Dynamic Networks, we study heuristic modifications of the deterministic Methodical Multi-counting (MMC) protocol [1] aimed to reduce its running time in practical applications. The heuristic presented here is the result of an extensive experimental study tuning all the parameters of the algorithm while maintaining correctness. We evaluate our heuristic MMC with thorough simulations on worst and average case topologies under different assumptions of dynamicity. Our results achieve speed-ups up to one or two orders of magnitude, which demonstrates that, as expected, the theoretical analysis overestimates the necessary running time to cope with adversarial scenarios, but in practice it is possible to tune the algorithm for specific topologies or other network characteristics without sacrificing correctness.
AB - Motivated by the current large gap between lower and upper bounds for Counting, i.e. the problem of computing the number of nodes, in Anonymous Dynamic Networks, we study heuristic modifications of the deterministic Methodical Multi-counting (MMC) protocol [1] aimed to reduce its running time in practical applications. The heuristic presented here is the result of an extensive experimental study tuning all the parameters of the algorithm while maintaining correctness. We evaluate our heuristic MMC with thorough simulations on worst and average case topologies under different assumptions of dynamicity. Our results achieve speed-ups up to one or two orders of magnitude, which demonstrates that, as expected, the theoretical analysis overestimates the necessary running time to cope with adversarial scenarios, but in practice it is possible to tune the algorithm for specific topologies or other network characteristics without sacrificing correctness.
KW - Algebraic Computations
KW - Anonymous Dynamic Networks
KW - Counting
UR - http://www.scopus.com/inward/record.url?scp=85108024303&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85108024303&partnerID=8YFLogxK
U2 - 10.1109/ISPA-BDCloud-SocialCom-SustainCom51426.2020.00186
DO - 10.1109/ISPA-BDCloud-SocialCom-SustainCom51426.2020.00186
M3 - Conference contribution
AN - SCOPUS:85108024303
T3 - Proceedings - 2020 IEEE International Symposium on Parallel and Distributed Processing with Applications, 2020 IEEE International Conference on Big Data and Cloud Computing, 2020 IEEE International Symposium on Social Computing and Networking and 2020 IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020
SP - 1257
EP - 1263
BT - Proceedings - 2020 IEEE International Symposium on Parallel and Distributed Processing with Applications, 2020 IEEE International Conference on Big Data and Cloud Computing, 2020 IEEE International Symposium on Social Computing and Networking and 2020 IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020
A2 - Hu, Jia
A2 - Min, Geyong
A2 - Georgalas, Nektarios
A2 - Zhao, Zhiwei
A2 - Hao, Fei
A2 - Miao, Wang
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 18th IEEE International Symposium on Parallel and Distributed Processing with Applications, 10th IEEE International Conference on Big Data and Cloud Computing, 13th IEEE International Symposium on Social Computing and Networking and 10th IEEE International Conference on Sustainable Computing and Communications, ISPA-BDCloud-SocialCom-SustainCom 2020
Y2 - 17 December 2020 through 19 December 2020
ER -
