[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Locally Balanced Allocations Under Strong Byzantine Influence

  • Conference paper
  • First Online:
Structural Information and Communication Complexity (SIROCCO 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14662))

  • 174 Accesses

Abstract

The Power of Two Choices (PoTC) is a commonly used technique to balance the incoming load (balls) into available resources (bins) – for each coming ball, two bins are selected uniformly at random and the one with smaller number of balls is chosen as the location of the current ball. We study a generalization of PoTC to a fault-prone setting – faulty bin(s) could present malicious information to enforce allocation decision on any of the two bins. Given m balls and n bins, such that no more than f of the bins are faulty, we show that the maximum loaded honest bin receives a surplus of a logarithmic number of balls with respect to f. Our result generalizes the classic bounds of the Power of Two Choices in the presence of a strong Byzantine adversary. Our solution and methods of analysis can help to efficiently implement and analyze resilient online local decisions made by processes when solving fundamental problems that depend on load balancing under the presence of Byzantine failures.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 89.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 109.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    “Power of Two Choices” can denote a principle as well as a greedy algorithm following said principle.

  2. 2.

    Observe that the power of two choices makes use of randomness only for \(n\ge 3\) bins.

References

  1. Abdulazeez, M., Garncarek, P., Kowalski, D.R., Wong, P.W.H.: Lightweight robust framework for workload scheduling in clouds. In: IEEE International Conference on Edge Computing, EDGE 2017, pp. 206–209. IEEE Computer Society (2017)

    Google Scholar 

  2. Alistarh, D., Aspnes, J., Gelashvili, R.: Space-optimal majority in population protocols. In: Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2221–2239 (2018)

    Google Scholar 

  3. Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235–253 (2006)

    Article  Google Scholar 

  4. Angluin, D., Aspnes, J., Eisenstat, D.: A simple population protocol for fast robust approximate majority. Distrib. Comput. 21(2), 87–102 (2008)

    Article  Google Scholar 

  5. Azar, Y., Broder, A.Z., Karlin, A.R., Upfal, E.: Balanced allocations. SIAM J. Comput. 29(1), 180–200 (1999)

    Article  MathSciNet  Google Scholar 

  6. Bansal, N., Feldheim, O.N.: The power of two choices in graphical allocation. In: STOC 2022, pp. 52–63. ACM (2022)

    Google Scholar 

  7. Bansal, N., Kuszmaul, W.: Balanced allocations: the heavily loaded case with deletions. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 801–812 (2022)

    Google Scholar 

  8. Ben-Nun, S., Kopelowitz, T., Kraus, M., Porat, E.: An \({O}(\log ^{3/2} n)\) parallel time population protocol for majority with \({O}(\log n)\) states. In: Proceedings of the 39th Symposium on Principles of Distributed Computing, PODC 2020, pp. 191–199. ACM (2020)

    Google Scholar 

  9. Ben-Or, M., Pavlov, E., Vaikuntanathan, V.: Byzantine agreement in the full-information model in \({O}(\log n)\) rounds. In: Proceedings of the \(38\)th Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 179–186. ACM (2006)

    Google Scholar 

  10. Beraldi, R., Mattia, G.: Power of random choices made efficient for fog computing. IEEE Trans. Cloud Comput. 10(02), 1130–1141 (2022)

    Article  Google Scholar 

  11. Berenbrink, P., Czumaj, A., Steger, A., Vöcking, B.: Balanced allocations: the heavily loaded case. SIAM J. Comput. 35(6), 1350–1385 (2006)

    Article  MathSciNet  Google Scholar 

  12. Bramson, M., Lu, Y., Prabhakar, B.: Asymptotic independence of queues under randomized load balancing. Queueing Syst. Theory Appl. 71(3), 247–292 (2012)

    Article  MathSciNet  Google Scholar 

  13. Busch, C., Kowalski, D.R.: Byzantine-resilient population protocols. CoRR abs/2105.07123 (2021)

    Google Scholar 

  14. Chrobak, M., Gasieniec, L., Kowalski, D.R.: The wake-up problem in multihop radio networks. SIAM J. Comput. 36(5), 1453–1471 (2007)

    Article  MathSciNet  Google Scholar 

  15. Cole, R., et al.: Randomized protocols for low-congestion circuit routing in multistage interconnection networks. In: Proceedings of the \(30\)th Annual ACM Symposium on Theory of Computing, STOC 1998, pp. 378–388 (1998)

    Google Scholar 

  16. Cooper, C., Elsässer, R., Radzik, T.: The power of two choices in distributed voting. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 435–446. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43951-7_37

    Chapter  Google Scholar 

  17. Gonnet, G.H.: Expected length of the longest probe sequence in hash code searching. J. ACM 28(2), 289–304 (1981)

    Article  MathSciNet  Google Scholar 

  18. Guerraoui, R., Ruppert, E.: Names trump malice: tiny mobile agents can tolerate byzantine failures. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5556, pp. 484–495. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02930-1_40

    Chapter  Google Scholar 

  19. Hagerup, T., Rüb, C.: A guided tour of chernoff bounds. Inf. Process. Lett. 33(6), 305–308 (1990)

    Article  MathSciNet  Google Scholar 

  20. Johnson, N.L., Kotz, S.: Urn models and their application: an approach to modern discrete probability theory. Int. Stat. Rev. 46, 319 (1978)

    Article  Google Scholar 

  21. Kenthapadi, K., Panigrahy, R.: Balanced allocation on graphs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 434–443 (2006)

    Google Scholar 

  22. Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982)

    Article  Google Scholar 

  23. Los, D., Sauerwald, T.: Balanced allocations with the choice of noise. In: Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC 2022), pp. 164–175 (2022)

    Google Scholar 

  24. Lynch, N.A.: Distributed Algorithms, 1st edn. Morgan Kaufmann (1996)

    Google Scholar 

  25. Park, C.J.: Random allocations (valentin f. kolchin, boris a. sevast’yanov and vladimir p. chistyakov). Siam Review 22, 104–104 (1980)

    Google Scholar 

  26. Peres, Y., Talwar, K., Wieder, U.: Graphical balanced allocations and the 1 + \(\beta \)-choice process. Random Struct. Algorithms 47(4), 760–775 (2015)

    Article  MathSciNet  Google Scholar 

  27. Richa, A., Mitzenmacher, M., Sitaraman, R.: The power of two random choices: a survey of techniques and results. In: Handbook of Randomized Computing (2001)

    Google Scholar 

  28. Vöcking, B.: How asymmetry helps load balancing. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1999, p. 131 (1999)

    Google Scholar 

Download references

Acknowledgments

This study was partly supported by the National Science Center, Poland (NCN), grant 2020/39/B/ST6/03288, and by the (US) National Science Foundation grant CNS-2131538.

Author information

Authors and Affiliations

  1. School of Computer and Cyber Sciences, Augusta University, Augusta, USA

    Costas Busch & Dariusz R. Kowalski

  2. Institute of Computer Science, University of Wrocław, Wrocław, Poland

    Paweł Garncarek

Authors
  1. Costas Busch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Paweł Garncarek
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dariusz R. Kowalski
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Paweł Garncarek .

Editor information

Editors and Affiliations

  1. Faculty of Data and Decision Sciences, Technion – Israel Institute of Technolog, Haifa, Israel

    Yuval Emek

Ethics declarations

Disclosure of Interests

The authors have no competing interests to declare that are relevant to the content of this article.

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Busch, C., Garncarek, P., Kowalski, D.R. (2024). Locally Balanced Allocations Under Strong Byzantine Influence. In: Emek, Y. (eds) Structural Information and Communication Complexity. SIROCCO 2024. Lecture Notes in Computer Science, vol 14662. Springer, Cham. https://doi.org/10.1007/978-3-031-60603-8_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-60603-8_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-60602-1

  • Online ISBN: 978-3-031-60603-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation