Running a workflow without workflows: a basic algorithm for dynamically constructing and traversing an implied Directed Acyclic Graphin a non-deterministic environment

• Autorzy: Smilianets Fedir , Finogenov Oleksii

Identyfikatory

DOI

10.35784/iapgos.5858

Warianty tytułu

PL

Obliczanie przepływów pracy bez przepływów pracy: podstawowy algorytm dynamicznego konstruowania i przeszukiwania niejawnego skierowanego grafu acyklicznego w środowisku niedeterministycznym

• Języki publikacji: EN

Abstrakty

EN

This paper introduces a novel algorithm for dynamically constructing and traversing Directed Acyclic Graphs (DAGs) in workflow systems, particularly targeting distributed computation and data processing domains. Traditional workflow managementsystems rely on explicitly defined, rigid DAGs, which can be cumbersome to maintain, especially in response to frequent changes or updates in the system. Our proposed algorithm circumvents the need for explicit DAG construction, instead opting for a dynamic approach that iteratively builds and executes the workflow based on available data and operations, through a combination of entities like Data Kinds, Operators, and Data Units, the algorithm implicitly forms a DAG, thereby simplifying the process of workflow management. We demonstrate the algorithm’s functionality and assess its performance through a series of tests in a simulated environment. The paper discusses the implications of this approach, especially focusing on cycle avoidance and computational complexity, and suggests future enhancements and potential applications.

PL

W artykule przedstawiono nowy algorytm dynamicznego konstruowania i przejść skierowanych grafów acyklicznych (DAG) w systemach zarządzania przepływem pracy, w szczególności tych ukierunkowanych na domeny obliczeń rozproszonych i przetwarzania danych. Tradycyjne systemy zarządzania przepływem pracy opierają się na jawnie zdefiniowanych, sztywnych grafach DAG, które mogą być uciążliwe w utrzymaniu, zwłaszczaw odpowiedzi na częste zmiany lub aktualizacje systemu. Proponowany algorytm pozwala uniknąć konieczności jawnego konstruowania SAG, zamiast tego wybierając dynamiczne podejście, które iteracyjnie buduje i wykonuje przepływy pracy w oparciu o dostępne dane i operacje. Korzystając z kombinacji jednostek, takich jak typ danych, operator i element danych, algorytm niejawnie buduje DAG, upraszczając w ten sposób proces zarządzania przepływami pracy. Demonstrujemy funkcjonalność algorytmu i oceniamy jego wydajność za pomocą serii testów w symulowanym środowisku. W artykule omówiono implikacje tego podejścia, ze szczególnym uwzględnieniem unikania pętli i złożoności obliczeniowej, a także zasugerowano dalsze ulepszenia i potencjalne zastosowania.

Słowa kluczowe

EN

distributed computing; directed acyclic graph; pipeline processing

PL

obliczenia rozproszone; skierowane grafy acykliczne; potokowe przetwarzanie danych

• Wydawca: Wydawnictwo Politechniki Lubelskiej
• Czasopismo: Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Środowiska
• Rocznik: 2024
• Tom: T. 14, nr 1
• Strony: 115--118
• Opis fizyczny: Bibliogr. 6 poz., rys.

Twórcy

autor

Smilianets Fedir

• National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, Ukraine

• https://orcid.org/0000-0002-0061-7479

autor

Finogenov Oleksii

• National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute", Kyiv, Ukraine

• https://orcid.org/0000-0002-1708-5632

Bibliografia

• [1] Brewer L. E. et al.: Causal inference in cumulative risk assessment: The roles of directed acyclic graphs. Environment International 102, 2017, 30–41 [https://doi.org/https://doi.org/10.1016/j.envint.2016.12.005].
• [2] Colonnelli I. et al.: Bringing AI pipelines onto cloud-HPC: setting a baseline for accuracy of COVID-19 diagnosis. ENEA CRESCO in the Fight Against COVID-19, 2021, 66–73 [https://doi.org/10.5281/ZENODO.5151511].
• [3] Eugster P. Th. et al.: The many faces of publish/subscribe. ACM Comput. Surv. 35(2), 2003, 114–131.
• [4] Ferguson K. D. et al.: Evidence synthesis for constructing directed acyclic graphs (ESC-DAGs): a novel and systematic method for building directed acyclic graphs. International Journal of Epidemiology 49(1), 2019, 322–329 [https://doi.org/10.1093/ije/dyz150].
• [5] Georgeson P. et al.: Bionitio: demonstrating and facilitating best practices for bioinformatics command-line software. GigaScience 8(9), 2019, giz109 [https://doi.org/10.1093/gigascience/giz109].
• [6] Jackson M. et al.: Using prototyping to choose a bioinformatics workflow management system. PLOS Computational Biology 17(2), 2021.