Using Answer Set Programming for Assigning Tasks to Computing Nodes Franz Wotawa1,* 1 Graz University of Technology (TU Graz), Institute of Software Technology, Inffeldgasse 16b/2, A-8010 Graz, Austria Abstract Allocating tasks to computing nodes in a network is an important configuration problem. In the case of fail-safe networks, such configuration must be changed during operation if a computing node fails. Hence, a fast configuration is required. In this paper, we formulate a tasks-to-computing-nodes assignment problem and its constraints using answer set programming. We performed an initial experimental evaluation utilizing several smaller to mid-size problem instances to show whether logic reasoning based on answer set programming is feasible for practical applications. We discovered that reasoning is fast if a solution exists but not when there is no solution. Further constraints help to decide that a problem instance is unsolvable early in the search, which improves the outcome. Keywords Configuring computing nodes, ASP models for configuration, Experimental analysis 1. Introduction clingo [8]. The question we want to answer is regard- ing the approach’s limitations regarding the problem size. There has been plenty of work in the area of configuration Can we use answer set programming (and in particular and recommender systems, including service configura- clingo) to provide task assignments fast enough to be tion [1], governance systems [2], or product configura- used during operation? tion [3] to refer to recent work. However, answer set We structure this paper as follows. First, we introduce programming for representing models used for config- the underlying configuration problem and clingo im- uration and reasoning to obtain valid configuration has plementation. Afterward, we discuss the experimental recently gained more attention, e.g., see [3, 4, 5]. In this evaluation, i.e., the basic setup and the results obtained. paper, we contribute to this research direction and intro- Finally, we conclude the paper. duce a model and an evaluation for configuring networks comprising computing nodes for executing pre-defined tasks. The underlying problem is related to scheduling 2. Problem description and shift designs [6]. The main motivation behind our work comes from We start defining the task to node assignment problem. practical applications, where, for example, tasks, i.e., pro- We assume we have π‘˜ computing nodes 𝑛1 , . . . , π‘›π‘˜ and grams, have to be deployed on computing nodes in a 𝑛 tasks 𝑑1 , . . . , 𝑑𝑛 to be assigned to the nodes. For each network. Although this problem can be seen as a static node 𝑛𝑖 , we know the maximum number of tasks 𝑐(𝑛𝑖 ) one that must only be solved before the operation, we it can hold and the available memory π‘š(𝑛𝑖 ). For each may require to re-configure such a task assignment dur- task 𝑑𝑗 , we know its memory consumption π‘š(𝑑𝑗 ). From ing operation whenever a computing node fails (see, e.g., this knowledge, we obtain several constraints an as- [7]). Such re-configuration tasks have to be carried out signment must fulfill to be valid. In the following, we under time restrictions. To evaluate whether modern formalize these constraints assuming that the function reasoning methods like answer set programming can be π‘Žπ‘ π‘ π‘–π‘”π‘›π‘’π‘‘(𝑛𝑖 ) returns a set of tasks that is assigned to a used for this task, we conduct an experimental evalua- node 𝑛𝑖 tion. This evaluation comprises several instances of the First, the required memory from the tasks assigned to corresponding task to computing node assignment prob- a node shall never exceed the available memory of this lems considering various sizes of nodes and tasks. The node. These constraints can be formalized as follows: βŽ› ⎞ evaluation utilizes the answer set programming solver βˆ‘οΈ βˆ€π‘– ∈ {1, . . . , π‘˜} : ⎝ π‘š(𝑑𝑗 ) ≀ π‘š(𝑛𝑖 )⎠ 𝑑𝑗 βˆˆπ‘Žπ‘ π‘ π‘–π‘”π‘›π‘’π‘‘(𝑛𝑖 ) ConfWS’24: 26th International Workshop on Configuration, Sep 2–3, 2024, Girona, Spain (1) * Corresponding author. Second, the number of tasks assigned to a node shall " wotawa@ist.tugraz.at (F. Wotawa) never exceed the maximum number of tasks the node ~ https://www.tugraz.at/ (F. Wotawa) can hold, i.e., formally, we write:  0000-0002-0462-2283 (F. Wotawa) Β© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). βˆ€π‘– ∈ {1, . . . , π‘˜} : (|π‘Žπ‘ π‘ π‘–π‘”π‘›π‘’π‘‘(𝑛𝑖 )| ≀ 𝑐(𝑛𝑖 )) (2) CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings A solution to the tasks to computing nodes assignment of a task. Let us call this predicate select that takes a problem is an assignment of all tasks to all nodes such task T as the first parameter and node N as the second. that βˆ€π‘— ∈ {1, . . . , π‘˜} : βˆƒπ‘– ∈ {1, . . . , 𝑛} : 𝑑𝑗 ∈ In clingo, the generate part for the node assignment π‘Žπ‘ π‘ π‘–π‘”π‘›π‘’π‘‘(𝑛𝑖 ), there is no tasks assigned to two different problem is given as follows: nodes, i.e., βˆ€π‘–, 𝑗 ∈ {1, . . . , π‘˜}, 𝑖 ΜΈ= 𝑗 : π‘Žπ‘ π‘ π‘–π‘”π‘›π‘’π‘‘(𝑛𝑖 ) ∩ π‘Žπ‘ π‘ π‘–π‘”π‘›π‘’π‘‘(𝑛𝑗 ) = βˆ…, and all constraints are fulfilled. Such { select(T,N) : node(N) } = 1 :- task(T). an assignment is a valid one and may not exist. For ex- ample, if the number of tasks exceeds the number of free This rule generates a grounded predicate that assigns slots of the nodes or if the required memory for the tasks tasks to each computing node. Obviously, not all as- is not provided, there is no solution. Hence, we have signments are correct when considering the constraints. two necessary conditions that must hold for obtaining a Hence, in the last part, we formalize the first two con- solution, i.e.: straints of the general problem, i.e., Equations 1 and 2, π‘˜ but not the other Equations 3 and 4. For this purpose, we introduce a predicate nrTasksAssigned that holds the βˆ‘οΈ 𝑛≀ 𝑐(𝑛𝑖 ) (3) 𝑖=1 number of tasks that are assigned to a particular node and 𝑛 π‘˜ a predicate memRequired that holds the required mem- ory for a node considering the assigned tasks. The infor- βˆ‘οΈ βˆ‘οΈ π‘š(𝑑𝑗 ) ≀ π‘š(𝑛𝑖 ) (4) 𝑗=1 𝑖=1 mation regarding the predicates can be obtained from the selected task for a node (select predicate) and the mem- It is worth noting that similar problems have additional ory required for a task. For the latter, we introduce the constraints, e.g., stating that tasks need to be together predicate memory. The predicate nrTasksAssigned in the same computing node. We may also introduce can be formalized in clingo as follows: optimality criteria like preferring solutions requiring the least amount of computing nodes. Furthermore, we may nrTasksAssigned(N,M) :- also consider variants of the problem, i.e., reconfiguration M = #count {T:select(T,N)}, of assignments. In the context of this paper, we do not node(N). tackle such extensions. We solely focus on answering the question regarding the applicability of the answer Similar, we can define the memRequired predicate: set program to solve the problem within a reasonable amount of time. memRequired(N,M) :- M = #sum {NM:select(T,N), memory(T,NM)}, After outlining the problem in general, we present a node(N). solution using answer set programming where we rely on the syntax of the clingo solver1 [8], which is similar Using these predicates, we can formulate the con- to the Prolog language. Due to space restrictions, we straints: do not give an introduction to answer set programming (ASP). Instead, we refer to introductory literature into :- nrTasksAssigned(N,M), tcapacity(N,C), M>C. ASP, e.g., [9]. :- memRequired(N,M), mcapacity(N,C), M > C. A clingo model for the node assignment problem comprises three parts. First, we define the number of The first constraint states that it is impossible to as- computing nodes and tasks and their capacities and re- sign more tasks to a node than the node can hold. The quirements. For every node, e.g., n2, we use three facts, second constraint states that the memory requirements where the predicate tcapacity denotes the maximum of all tasks should not exceed the memory capacity of number of tasks, and mcapacity the maximum available the computing node. memory for the given task.: node(n2). tcapacity(n2,1). mcapacity(n2,20). 3. Experimental evaluation For each task, e.g., t1, we add two facts, where the The following experimental evaluation aims to investi- predicate memory is for defining the required memory gate the runtime behavior for finding one solution of the of the given task to a pre-defined value: task to computation node assignment problem using the ASP solver clingo. In particular, we are interested in task(t1). memory(t1,30). the number of nodes that can be handled requiring less than a fixed boundary of time, e.g., 0.01 or 0.1 seconds. Second, we generate all potential solutions. For this In the following, we outline the experimental setup and purpose, we introduce a predicate for a node assignment present and discuss the obtained results. 1 See https://potassco.org/about/ which can be achieved for 20 or 13 nodes, respectively. Runtime in seconds vs. number of nodes Motivated by the results, we performed further ex- periments, considering problems that likely cannot be 100 time 𝑑 in seconds solved. Unfortunately, in this case, we often ran into reaching the solving time limit of 10 seconds, even start- 10βˆ’1 ing with small examples only considering 5 computing nodes. Instances with more than 7 nodes that might be 10βˆ’2 unsatisfiable always reach the 10-second limit. For those instances where unsatisfiability could be established, the 10βˆ’3 runtime varies between 0.003 and 6.255 seconds. The 0 50 100 latter was obtained for a problem instance comprising nodes 𝑛 7 computing nodes. Hence, unsatisfiable instances can hardly be identified when considering more computing Figure 1: Solving runtime of consistent instances nodes, which might also be an issue for practical applica- tions. We carried out another experiment to tackle the men- Experimental setup: To develop several instances of tioned problem of potential unsatisfiability. We selected the task assignment problem, we wrote a Java program 3 problem instances for which we could not compute for generating such instances automatically. We ranged a result. Two instances had 7 nodes, and one had 15 the number of nodes from 5 to 100. The number of tasks nodes. For these problem instances, we added further for each instance was randomly chosen between the num- constraints that cover Equations 3 and 4. For all three ber of nodes and double the number of nodes. The ca- clingo files that correspond to the problem instances, pacity of each node was randomly set from 1,2, . . . , 10. we added the following code: The memory provided by each node was randomly cho- sen from 20, 40, 60,. . . , 200. The memory required by totalCapacity(C) :- C=#sum{T:tcapacity(N,T)}. every task was randomly set from 10, 20, and 30. With totalMemReq(C) :- C=#sum{M:memory(T,M)}. this setup, we generated only satisfiable instances, i.e., totalMem(C) :- C=#sum{N:mcapacity(CN,N)}. problem instances where a solution exists. For a category :- totalCapacity(C), C < 21. :- totalMemReq(Ctask), totalMem(Cnode), of instances comprising 𝑛 nodes, we called the instance Ctask > Cnode. generator 10 times. Finally, we received 200 different problem instances. Note that the 21 in the above code represents the num- We conducted the experiments using an Apple Mac- ber of tasks2 . We adapted this value for each instance Book Pro, with an Apple M1 CPU comprising 8 cores and and set it to 21, 28, and 60 respectively. When running 16 GB of main memory, running under macOS Sonoma clingo on the three files, we obtained an immediate Version 14.4.1. For computing solutions, we relied on response of unsatisfiability. In all cases, this response clingo version 5.7.1 and applied the standard setup. was less than 0.025 seconds. Hence, adding further con- straints that allow distinguishing satisfiable from unsat- Experimental results: After generating the prob- isfiable cases as early as possible solves the problem. lem instances, we ran clingo to compute one solu- In summary, clingo allows for fast computation of tion, i.e., we ran clingo using the prompt clingo solutions if they exist. The reasoning for the mentioned –time-limit=10 –outf=2 for each file. Hence, we tasks-to-computing-nodes assignment problem is fast set a time limit of 10 seconds and obtained all results in enough for at least smaller examples to ensure a timely JSON format. After analyzing the results for correctness, response. However, whether this is good enough depends we summarized the outcome, i.e., the runtime for each on the application domain. The challenges we obtained in category of a particular number of nodes. Figure 1 de- the case of unsatisfiability can be solved by setting a time picts the minimum, maximum, and average runtime for limit for clingo and introducing additional constraints. all 10 runs for each category. Results from this case study may also apply to other We see that when using ASP solving utilizing clingo configuration problems. we can provide one solution even for larger instances of 100 computing nodes in a reasonable amount of time. Threats to validity: There are many threats to valid- However, when using the approach during operation, and ity worth mentioning. The experimental evaluation is especially for systems with harder requirements regard- 2 ing answering time, e.g., real-time systems, a runtime of The number of tasks for a particular problem instance can also be obtained using clingo. The command #count{T:task(T)} almost 3 seconds might not be feasible. We would like delivers this number. However, we set the number manually for answers in less than 0.1 or 0.01 seconds for such systems, the three experiments. limited in the number of problem instances. There might Taupe, L. Fuentes (Eds.), Proc. 25th Intl. Workshop be satisfiable instances that may take longer than re- on Configuration, MΓ‘laga, Spain, September 6-7, ported for a given number of computing nodes. However, 2023, CEUR-WS.org, 2023, pp. 67–74. URL: https: we do not expect a very large deviation from the results. //ceur-ws.org/Vol-3509/paper10.pdf. Furthermore, we only considered one rather simple con- [3] R. Comploi-Taupe, G. Friedrich, T. Niestroj, Dynamic figuration problem. In case of more complex problems, aggregates in expressive ASP heuristics for config- we expect different runtimes. Nevertheless, the effect of uration problems, in: J. M. Horcas, J. A. Galindo, adding constraints to determine unsatisfiability as early R. Comploi-Taupe, L. Fuentes (Eds.), Proc. 25th Intl. as possible should still be visible. This might also hold Workshop on Configuration, MΓ‘laga, Spain, Septem- for the observation that unsatisfiability might be hard ber 6-7, 2023, CEUR-WS.org, 2023, pp. 75–84. URL: to identify and, therefore, require more computing time. https://ceur-ws.org/Vol-3509/paper11.pdf. We carried out all experiments using clingo’s standard- [4] N. RΓΌhling, T. Schaub, T. Stolzmann, Towards a for- setting. There might be differences to observe when malization of configuration problems for asp-based changing parameters and setup. There might also be reasoning: Preliminary report, in: J. M. Horcas, J. A. differences when considering other versions of clingo, Galindo, R. Comploi-Taupe, L. Fuentes (Eds.), Proc. the hardware, or the operating system. Finally, the repre- 25th Intl. Workshop on Configuration, MΓ‘laga, Spain, sentation of the problem in clingo might also influence September 6-7, 2023, CEUR-WS.org, 2023, pp. 85–94. the performance. URL: https://ceur-ws.org/Vol-3509/paper12.pdf. [5] R. Comploi-Taupe, A. A. Falkner, S. Hahn, T. Schaub, G. Schenner, Interactive configuration with ASP 4. Conclusions multi-shot solving, in: J. M. Horcas, J. A. Galindo, R. Comploi-Taupe, L. Fuentes (Eds.), Proc. 25th Intl. In this paper, we used the configuration problem of as- Workshop on Configuration, MΓ‘laga, Spain, Septem- signing tasks to computing nodes to answer whether ber 6-7, 2023, CEUR-WS.org, 2023, pp. 95–103. URL: answer-set programming is feasible for practical appli- https://ceur-ws.org/Vol-3509/paper13.pdf. cations. For smaller problem instances, answer set pro- [6] M. Abseher, M. Gebser, N. Musliu, T. Schaub, gramming might be feasible, providing a fast response S. Woltran, Shift design with answer set program- within a fraction of a second. For larger instances, we ming, in: F. Calimeri, G. Ianni, M. Truszczyn- may not be able to provide a solution within a reasonable ski (Eds.), Proc. 13th Intl. Conf. on Logic Program- answer time. Furthermore, we identified a challenge, i.e., ming and Nonmonotonic Reasoning, 2015, Lex- the extended runtime required for providing an answer ington, KY, USA, September 27-30, 2015., volume in case of unsatisfiability, and a solution, i.e., the effect of 9345 of LNCS, Springer, 2015, pp. 32–39. URL: additional constraints on reducing the runtime. In future https://doi.org/10.1007/978-3-319-23264-5_4. doi:10. research, we want to extend the configuration problem to 1007/978-3-319-23264-5\_4. capture the case of task assignments for computing net- [7] A. Ballesteros, M. Barranco, J. Proenza, L. Almeida, works at runtime. For this purpose, we want to formulate F. Pozo, P. Palmer-RodrΓ­guez, An infrastructure a corresponding re-configuration problem. Furthermore, for enabling dynamic fault tolerance in highly- we want to extend the experimental evaluation using reliable adaptive distributed embedded systems more example instances and additional constraints and based on switched ethernet, Sensors 22 (2022) consider computing optimal solutions concerning a given 7099. URL: https://doi.org/10.3390/s22187099. doi:10. optimization criteria, e.g., using the least number of com- 3390/S22187099. puting nodes. [8] M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, Multi-shot asp solving with clingo, Theory and References Practice of Logic Programming 19 (2019) 27–82. doi:10.1017/S1471068418000054. [1] E. M. StrΓΈm, T. M. MΓΌnsberg, L. Hvam, Identifying [9] T. Eiter, G. Ianni, T. Krennwallner, Answer potential applications of service configuration sys- set programming: A primer, in: S. Tessaris, tems in a logistics company, in: J. M. Horcas, J. A. E. Franconi, T. Eiter, C. Gutierrez, S. Hand- Galindo, R. Comploi-Taupe, L. Fuentes (Eds.), Proc. schuh, M.-C. Rousset, R. A. Schmidt (Eds.), Rea- 25th Intl. Workshop on Configuration, MΓ‘laga, Spain, soning Web. Semantic Technologies for Informa- September 6-7, 2023, CEUR-WS.org, 2023, pp. 60–66. tion Systems: 5th Intl. Summer School, Brixen- URL: https://ceur-ws.org/Vol-3509/paper9.pdf. Bressanone, Italy, August 30 - September 4, 2009, [2] S. MuΓ±oz-Hermoso, D. Benavides, F. J. D. Mayo, pp. 40–110, Springer Berlin Heidelberg, . URL: Multi-level configuration in smart governance sys- https://doi.org/10.1007/978-3-642-03754-2_2. doi:10. tems, in: J. M. Horcas, J. A. Galindo, R. Comploi- 1007/978-3-642-03754-2\_2.