Distributed Computing on Core-Periphery Networks: Axiom-based Design

Inspired by social networks and complex systems, we propose a core-periphery network architecture that supports fast computation for many distributed algorithms and is robust and efficient in number of links. Rather than providing a concrete network model, we take an axiom-based design approach. We...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2015-09
Main Authors: Chen, Avin, Borokhovich, Michael, Lotker, Zvi, Peleg, David
Format: Article
Language:English
Subjects:
Algorithms
Axioms
Complex systems
Computer networks
Distributed processing
Microprocessors
Multiplication
Social networks
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Inspired by social networks and complex systems, we propose a core-periphery network architecture that supports fast computation for many distributed algorithms and is robust and efficient in 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 (e.g., MST, sparse matrix multiplication, etc.). We also show the minimality of our axiom set: for networks that satisfy any subset of the axioms, the same efficiency cannot be guaranteed for any deterministic algorithm.
ISSN:2331-8422