@inproceedings{papp23a,
  author = {Papp, P\'{a}l Andr\'{a}s and Anegg, Georg and Yzelman, A. N.},
  keywords = {Computational Complexity (cs.CC), FOS: Computer and information sciences, FOS: Computer and information sciences, G.2.2; F.2.2, 68Q17, 68Q85, 05C20},
  title = {{DAG} Scheduling in the {BSP} Model},
  booktitle="{SOFSEM 2025}: Theory and Practice of Computer Science",
  year = {2025},
  publisher="Springer Nature Switzerland",
  address="Cham",
  pages="238--253",
  abstract="We study the problem of scheduling an arbitrary computational {DAG} on a fixed number of processors while minimizing the makespan. While previous works have mostly studied this problem in fairly restricted models, we define and analyze {DAG} scheduling in the {Bulk Synchronous Parallel (BSP)} model, which is a well-established parallel computing model that captures the communication cost between processors much more accurately. We provide a taxonomy of simpler scheduling models that can be understood as variants or special cases of {BSP}, and discuss how the properties and optimum cost of these models relate to {BSP}. This essentially allows us to dissect the different building blocks of the {BSP} model, and gain insight into how these influence the scheduling problem.",
  isbn="978-3-031-82697-9"
}