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.
clingo [8]. The question we want to answer is regarding the approach’s limitations regarding the problem size.
Can we use answer set programming (and in particular clingo) to provide task assignments fast enough to be used during operation?
We structure this paper as follows. First, we introduce the underlying configuration problem and clingo implementation. Afterward, we discuss the experimental evaluation, i.e., the basic setup and the results obtained.
Finally, we conclude the paper.
There has been plenty of work in the area of configuration and recommender systems, including service configuration [1], governance systems [2], or product configuration [3] to refer to recent work. However, answer set programming for representing models used for configuration and reasoning to obtain valid configuration has recently gained more attention, e.g., see [3, 4, 5]. In this paper, we contribute to this research direction and introduce 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, . . . , } : ⎝ ( ) ≤ ()⎠ ∈()
(1) Second, the number of tasks assigned to a node shall never exceed the maximum number of tasks the node can hold, i.e., formally, we write: ∀ ∈ {1, . . . , } : (|()| ≤ ()) (2) 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 diferent 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 example, 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 asis 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 consolution, 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 ≤ ∑︁ () (3) introduce a predicate nrTasksAssigned that holds the =1 number of tasks that are assigned to a particular node and a predicate memRequired that holds the required mem∑︁ () ≤ ∑︁ () (4) ory for a node considering the assigned tasks. The infor=1 =1 mation regarding the predicates can be obtained from the selected task for a node (select predicate) and the memory required for a task. For the latter, we introduce the predicate memory. The predicate nrTasksAssigned can be formalized in clingo as follows:
It is worth noting that similar problems have additional constraints, e.g., stating that tasks need to be together in the same computing node. We may also introduce 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) :
After outlining the problem in general, we present a M = #sum {NM:select(T,N), memory(T,NM)}, solution using answer set programming where we rely node(N). on the syntax of the clingo solver1 [8], which is similar Using these predicates, we can formulate the conto 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 ascomputing 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).
For each task, e.g., t1, we add two facts, where the The following experimental evaluation aims to investipredicate 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. 1See https://potassco.org/about/
Runtime in seconds vs. number of nodes which can be achieved for 20 or 13 nodes, respectively.
Motivated by the results, we performed further experiments, considering problems that likely cannot be sdn 100 solved. Unfortunately, in this case, we often ran into co reaching the solving time limit of 10 seconds, even startisen10− 1 ing with small examples only considering 5 computing nodes. Instances with more than 7 nodes that might be iem10− 2 unsatisfiable always reach the 10-second limit. For those t 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 Figure 1: Solving runtime of consistent instances hardly be identified when considering more computing nodes, which might also be an issue for practical applications.
We carried out another experiment to tackle the menExperimental 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 chosen 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. of instances comprising nodes, we called the instance :- totalMeCmtRaesqk(C>taCsnko)d,e.totalMem(Cnode), generator 10 times. Finally, we received 200 diferent 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 constraints that allow distinguishing satisfiable from unsatExperimental 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 validHowever, when using the approach during operation, and ity worth mentioning. The experimental evaluation is especially for systems with harder requirements regarding answering time, e.g., real-time systems, a runtime of 2The number of tasks for a particular problem instance can also almost 3 seconds might not be feasible. We would like bdeeliovbetrasinthedisunsuinmgbcerl.iHngoow.eTvehre, wcoemsmetatnhde#ncuomubnetr{mT:atnausalkly(Tf)or} answers in less than 0.1 or 0.01 seconds for such systems, the three experiments.