The communication complexity of distributed task allocation

DOI10.1145/2332432.2332443MaRDI QIDQ2933777zbMATH OpenOpenAlexFDO

Authors Andrew Drucker, Fabian Kuhn, Rotem Oshman

Publication date 5 December 2014

Published in Proceedings of the 2012 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.261.2512

zbMATH Keywords

directed spanning treesmultiparty communication complexitytask allocationunidirectional links

Mathematics Subject Classification ID

Distributed systems (68M14) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) 2-person games (91A05) (n)-person games, (n>2) (91A06) Signaling and communication in game theory (91A28)

Recommendations

• The task allocation problem with constant communication.
• Distributed communication complexity of spanning tree construction
• Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity
• Placement Des Taches D’Un Programme A Structure Arborescente Sur Un Reseau De Processeurs: Synthese De Resultats Recents
• scientific article; zbMATH DE number 4058884

Cited in

(17)

• The task allocation problem with constant communication.
• Optimal bounds on the gain of permitting dynamic allocation of communication channels in distributed computing
• The role of randomness in the broadcast congested clique model
• Connectivity and connected components in the number-in-hand computation model
• Distributed balanced color assignment on arbitrary networks
• Solving the \textsc{induced subgraph} problem in the randomized multiparty simultaneous messages model
• A combinatorial characterization of the distributed 1-solvable tasks
• Amortized Communication Complexity of Distributions
• Solving the at-most-once problem with nearly optimal effectiveness
• On the average communication complexity of asynchronous distributed algorithms
• scientific article; zbMATH DE number 758132 (Why is no real title available?)
• The Communication Complexity of Distributed epsilon-Approximations
• Large-scale distributed algorithms for facility location with outliers
• Doing-it-all with bounded work and communication
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Bounds on oblivious multiparty quantum communication complexity
• Lessons from the congested clique applied to MapReduce

This page was built for publication: The communication complexity of distributed task allocation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933777)