The communication complexity of distributed task allocation

Andrew Drucker, Fabian Kuhn, Rotem Oshman

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider a distributed task allocation problem in which m players must divide a set of n tasks between them. Each player i receives as input a set Xi of tasks such that the union of all input sets covers the task set. The goal is for each player to output a subset Yi ⊆ Xi, such that the outputs (Y1,...,Ym) form a partition of the set of tasks. The problem can be viewed as a distributed one-shot variant of the well-known k-server problem, and we also show that it is closely related to the problem of finding a rooted spanning tree in directed broadcast networks.

We study the communication complexity and round complexity of the task allocation problem. We begin with the classical two-player communication model, and show that the randomized communication complexity of task allocation is Ω(n), even when the set of tasks is known to the players in advance. For the multi-player setting with m = O(n) we give two upper bounds in the shared-blackboard model of communication. We show that the problem can be solved in O(log n) rounds and O(n log n) total bits for arbitrary inputs; moreover, if for any set X of tasks, there are at least α|X| players that have at least one task from X in their inputs, then O((1/α + log m)log n) rounds suffice even if each player can only write O(log n) bits on the blackboard in each round. Finally, we extend our results to the case where the players communicate over an arbitrary directed communication graph instead of a shared blackboard. As an application of these results, we also consider the related problem of constructing a directed spanning tree in strongly-connected directed networks and we show lower and upper bounds for that problem.
Original languageEnglish
Title of host publicationACM Symposium on Principles of Distributed Computing, PODC '12, Funchal, Madeira, Portugal, July 16-18, 2012
Number of pages10
ISBN (Electronic)978-1-4503-1450-3
Publication statusPublished - 2012


Dive into the research topics of 'The communication complexity of distributed task allocation'. Together they form a unique fingerprint.

Cite this