caa a22 4500 555285510 20190715031130.0 cr unu---uuuuu 190206s2018 xx s 100 0 eng 10.3929/ethz-b-000315337 doi 10.4230/LIPIcs.DISC.2018.30 doi (ETHRESEARCH)oai:www.research-collection.ethz.ch:20.500.11850/315337 Ghaffari Mohsen Distributed MST and broadcast with fewer messages, and faster gossiping [Elektronische Daten] [Mohsen Ghaffari, Fabian Kuhn, Ulrich Schmid (Editor), Josef Widder (Editor)] Leibniz int. proc. inform. Dagstuhl Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018 Open access ethresearch We present a distributed minimum spanning tree algorithm with near-optimal round complexity of O~(D+sqrt{n}) and message complexity O~(min{n^{3/2}, m}). This is the first algorithm with sublinear message complexity and near-optimal round complexity and it improves over the recent algorithms of Elkin [PODC'17] and Pandurangan et al. [STOC'17], which have the same round complexity but message complexity O~(m). Our method also gives the first broadcast algorithm with o(n) time complexity - when that is possible at all, i.e., when D=o(n) - and o(m) messages. Moreover, our method leads to an O~(sqrt{nD})-round GOSSIP algorithm with bounded-size messages. This is the first such algorithm with a sublinear round complexity. 32nd International Symposium on Distributed Computing (DISC 2018) in New Orleans, LA, USA (October 15-19, 2018) Creative Commons Attribution 3.0 Unported http://creativecommons.org/licenses/by/3.0 ethresearch Distributed Algorithms ethresearch Minimum Spanning Tree ethresearch Round Complexity ethresearch Message Complexity ethresearch Gossiping ethresearch Broadcast ethresearch Kuhn Fabian joint author Schmid Ulrich Editor edt Widder Josef Editor edt 32nd International Symposium on Distributed Computing (DISC 2018) Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik pp. 30:1-30:12 978-3-95977-092-7 http://hdl.handle.net/20.500.11850/315337 text/html WWW-Backlink auf das Repository (Open access) 1 Conference Paper ethresearch ETHRESEARCH 856 40 http://hdl.handle.net/20.500.11850/315337 text/html WWW-Backlink auf das Repository (Open access) ETHRESEARCH 100 1- Ghaffari Mohsen ETHRESEARCH 700 1- Kuhn Fabian joint author ETHRESEARCH 700 1- Schmid Ulrich Editor edt ETHRESEARCH 700 1- Widder Josef Editor edt ETHRESEARCH 773 0- 32nd International Symposium on Distributed Computing (DISC 2018) Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik pp. 30:1-30:12 978-3-95977-092-7 BK010053 XK010053 XK010000 ETHRESEARCH ETHRESEARCH ETHRESEARCH Conference Paper Open access