Distributed computing on core-periphery networks: Axiom-based design

作者：Avin Chen; Borokhovich Michael^*; Lotker Zvi; Peleg David

来源：Journal of Parallel and Distributed Computing, 2017, 99: 51-67.

DOI：10.1016/j.jpdc.2016.08.003

• Distributed computing
• Core-periphery networks
• Axiom-base design
• Minimum spanning tree

Inspired by social networks and complex systems, we propose a core-periphery network architecture that supports fast computation for many distributed algorithms, is robust and uses a linear number of links. Rather than providing a concrete network model, we take an axiom-based design approach. We provide three intuitive and independent algorithmic axioms and prove that any network that satisfies all axioms enjoys an efficient algorithm for a range of tasks (such as MST, sparse matrix multiplication, and more). We also show the necessity of our axiom set: for networks that satisfy any subset of the axioms, the same efficiency cannot be guaranteed for any deterministic algorithm.

• 出版日期2017-1