Document Open Access Logo

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost

Authors Aaron Berger , William Kuszmaul , Adam Polak , Jonathan Tidor , Nicole Wein

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.19.pdf
  • Filesize: 0.8 MB
  • 19 pages

Document Identifiers

Author Details

Aaron Berger
  • MIT, Cambridge, MA, USA
William Kuszmaul
  • MIT, Cambridge, MA, USA
Adam Polak
  • EPFL, Lausanne, Switzerland
Jonathan Tidor
  • MIT, Cambridge, MA, USA
Nicole Wein
  • DIMACS, Piscataway, NJ, USA

Funding

  • Berger, Aaron: NSF Graduate Research Fellowship Program DGE-1745302.
  • Kuszmaul, William: NSF GRFP fellowship and a Fannie and John Hertz Fellowship. Research was partially sponsored by the United States Air Force Research Laboratory and was accomplished under Cooperative Agreement Number FA8750-19-2-1000. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the United States Air Force or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
  • Polak, Adam: Swiss National Science Foundation project Lattice Algorithms and Integer Programming (185030). Part of this work was done at Jagiellonian University, supported by National Science Center of Poland grant 2017/27/N/ST6/01334.
  • Tidor, Jonathan: NSF Graduate Research Fellowship Program DGE-1745302.
  • Wein, Nicole: This work was done at MIT, supported by NSF Grant CCF-1514339.

Cite AsGet BibTex

Aaron Berger, William Kuszmaul, Adam Polak, Jonathan Tidor, and Nicole Wein. Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.19

Abstract

We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of w workers and a multiset T ⊆ [t] of |T| = w tasks, a memoryless worker-task assignment function is any function ϕ that assigns the workers [w] to the tasks T based only on the current value of T. The assignment function ϕ is said to have switching cost at most k if, for every task multiset T, changing the contents of T by one task changes ϕ(T) by at most k worker assignments. The goal of memoryless worker task assignment is to construct an assignment function with the smallest possible switching cost. In past work, the problem of determining the optimal switching cost has been posed as an open question. There are no known sub-linear upper bounds, and after considerable effort, the best known lower bound remains 4 (ICALP 2020). We show that it is possible to achieve polylogarithmic switching cost. We give a construction via the probabilistic method that achieves switching cost O(log w log (wt)) and an explicit construction that achieves switching cost polylog (wt). We also prove a super-constant lower bound on switching cost: we show that for any value of w, there exists a value of t for which the optimal switching cost is w. Thus it is not possible to achieve a switching cost that is sublinear strictly as a function of w. Finally, we present an application of the worker-task assignment problem to a metric embeddings problem. In particular, we use our results to give the first low-distortion embedding from sparse binary vectors into low-dimensional Hamming space.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Random projections and metric embeddings
  • Mathematics of computing → Combinatorics
Keywords
  • Distributed Task Allocation
  • Metric Embeddings
  • Probabilistic Method

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alexandr Andoni, Moses S Charikar, Ofer Neiman, and Huy L Nguyen. Near linear lower bound for dimension reduction in 𝓁₁. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 315-323. IEEE, 2011. Google Scholar
  2. Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A polylogarithmic-competitive algorithm for the k-server problem. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 267-276. IEEE, 2011. Google Scholar
  3. Radu Berinde, Anna C Gilbert, Piotr Indyk, Howard Karloff, and Martin J Strauss. Combining geometry and combinatorics: A unified approach to sparse signal recovery. In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pages 798-805. IEEE, 2008. Google Scholar
  4. Samuel N Beshers and Jennifer H Fewell. Models of division of labor in social insects. Annual review of entomology, 46(1):413-440, 2001. Google Scholar
  5. Jean Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel Journal of Mathematics, 52(1-2):46-52, 1985. Google Scholar
  6. Bo Brinkman and Moses Charikar. On the impossibility of dimension reduction in $$1ell _1. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, page 514, 2003. Google Scholar
  7. Diptarka Chakraborty, Elazar Goldenberg, and Michal Kouckỳ. Streaming algorithms for embedding and computing edit distance in the low distance regime. In Proceedings of the 48th annual ACM Symposium on Theory of Computing, pages 712-725, 2016. Google Scholar
  8. Moses Charikar, Ofir Geri, Michael P Kim, and William Kuszmaul. On estimating edit distance: Alignment, dimension reduction, and embeddings. In 45th International Colloquium on Automata, Languages, and Programming (ICALP), volume 107, page 34, 2018. Google Scholar
  9. Moses Charikar and Robert Krauthgamer. Embedding the Ulam metric into 𝓁₁. Theory of Computing, 2(1):207-224, 2006. Google Scholar
  10. Moses Charikar and Amit Sahai. Dimension reduction in the 𝓁₁ norm. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 551-560. IEEE, 2002. Google Scholar
  11. P Erdős and A Hajnal. On chromatic number of infinite graphs. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 83-98. Academic Press, 1968. Google Scholar
  12. Paul Erdős and Richard Rado. Combinatorial theorems on classifications of subsets of a given set. Proceedings of the London mathematical Society, 3(1):417-439, 1952. Google Scholar
  13. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM Symposium on Theory of Computing, pages 448-455, 2003. Google Scholar
  14. Stefan Felsner. Interval orders: combinatorial structure and algorithms. PhD thesis, Technische Universität Berlin, 1992. URL: http://page.math.tu-berlin.de/~felsner/Paper/diss.pdf.
  15. Chryssis Georgiou and Alexander A Shvartsman. Cooperative task-oriented computing: Algorithms and complexity. Synthesis Lectures on Distributed Computing Theory, 2(2):1-167, 2011. Google Scholar
  16. A. C. Gilbert, M. J. Strauss, J. A. Tropp, and R. Vershynin. Algorithmic linear dimension reduction in the 𝓁₁ norm for sparse vectors. In Allerton 2006 (44th Annual Allerton Conference on Communication, Control, and Computing, 2006. Google Scholar
  17. Anna Gilbert and Piotr Indyk. Sparse recovery using sparse matrices. Proceedings of the IEEE, 98(6):937-947, 2010. Google Scholar
  18. Piotr Indyk. Explicit constructions for compressed sensing of sparse signals. In Proceedings of the nineteenth annual ACM-SIAM Symposium on Discrete Algorithms, pages 30-33, 2008. Google Scholar
  19. William B Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics, 26(189-206):1, 1984. Google Scholar
  20. Michael JB Krieger, Jean-Bernard Billeter, and Laurent Keller. Ant-like task allocation and recruitment in cooperative robots. Nature, 406(6799):992, 2000. Google Scholar
  21. Kristina Lerman, Chris Jones, Aram Galstyan, and Maja J Matarić. Analysis of dynamic task allocation in multi-robot systems. The International Journal of Robotics Research, 25(3):225-241, 2006. Google Scholar
  22. Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995. Google Scholar
  23. Kathryn Sarah Macarthur, Ruben Stranders, Sarvapali D Ramchurn, and Nicholas R Jennings. A distributed anytime algorithm for dynamic task allocation in multi-agent systems. In AAAI, pages 701-706, 2011. Google Scholar
  24. Jiří Matoušek. On variants of the Johnson-Lindenstrauss lemma. Random Structures & Algorithms, 33(2):142-156, 2008. Google Scholar
  25. Colin McDiarmid. On the method of bounded differences. Surveys in combinatorics, 141(1):148-188, 1989. Google Scholar
  26. James McLurkin and Daniel Yamins. Dynamic task assignment in robot swarms. In Robotics: Science and Systems, volume 8. Citeseer, 2005. Google Scholar
  27. James Dwight McLurkin. Stupid robot tricks: A behavior-based distributed algorithm library for programming swarms of robots. PhD thesis, Massachusetts Institute of Technology, 2004. Google Scholar
  28. Raghu Meka, Omer Reingold, and Yuan Zhou. Deterministic Coupon Collection and Better Strong Dispersers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), volume 28 of Leibniz International Proceedings in Informatics (LIPIcs), pages 872-884, 2014. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.872.
  29. Rafail Ostrovsky and Yuval Rabani. Low distortion embeddings for edit distance. Journal of the ACM (JACM), 54(5):23-es, 2007. Google Scholar
  30. Tsvetomira Radeva, Anna Dornhaus, Nancy Lynch, Radhika Nagpal, and Hsin-Hao Su. Costs of task allocation with local feedback: Effects of colony size and extra workers in social insects and other multi-agent systems. PLoS computational biology, 13(12):e1005904, 2017. Google Scholar
  31. Gene E Robinson. Regulation of division of labor in insect societies. Annual review of entomology, 37(1):637-665, 1992. Google Scholar
  32. Erol Şahin. Swarm robotics: From sources of inspiration to domains of application. In International workshop on swarm robotics, pages 10-20. Springer, 2004. Google Scholar
  33. Hsin-Hao Su, Lili Su, Anna Dornhaus, and Nancy Lynch. Ant-inspired dynamic task allocation via gossiping. In International Symposium on Stabilization, Safety, and Security of Distributed Systems, pages 157-171. Springer, 2017. Google Scholar
  34. Hsin-Hao Su and Nicole Wein. Lower Bounds for Dynamic Distributed Task Allocation. In 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168, pages 99:1-99:14, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.99.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact