Notes on Satisfiability and/vs Comparison

October 5, 2024

This post is a collection of notes while thinking and discussing on the following issue Satisfiability in resource interface . While the issue itself relates mostly to the question of designing the proper interface in dms-v0.5.0 for driving job orchestration or, more specifically, for matching proper machines for ensemble of jobs, it seems that we soon realized, that the immediate question is actually related to quite a few more general and fundamental platform design questions – up to the ultimate question ‘what is the purpose of the NuNet platform’.

I spend some time thinking how to properly describe my thoughts about the issue and it seemed that the best way would be to collect all related thoughts (some of which started in Slack and Zoom discussions) into a separate post and then refer to them in the comments on the issue. Lets try and see how it works.

Declarative vs Operational Semantics (in computer science) #

A useful distinction that @vyzo proposed in the beginning of the discussion is that my formulations of the design seems to be gearing towards ‘declarative semantics’, while he is more inclined to think in terms of ‘operational semantics’. Which also somehow relates to the long lasting dynamics between me and @dagim on the relation between ‘high level architecture design’ and ’low level implementation details’. In the more general realm of ‘IT management’ it seems that this distinction is a some source of tension between general ‘architecture’ and ‘implementation’ aspects of software systems.

It is clear to me and hope to all that we need both in order to achieve the desired result – a software product that is has working features now and can evolve into full potential of the envisioned platform. Therefore the most important aspects for me in terms of this context is to find a proper balance between the two – for which we need to have not only a clear idea of both notions, but, even more importantly, the relation between them.

Possibly somewhat simplistically, but also quite clearly:

Declarative semantics specifies what the result of a computation should be, while operational semantics explains how that computation proceeds step-by-step.
A program may have the same declarative semantics but different operational semantics based on the specific implementation or rules used for execution.
That pretty much in line with the “why” -> “what” -> “how” line of reasoning for any engineering problem.

To say bluntly, the relations between these is that there is no point in answering the question ‘how to do stuff?’ when we do not have a clear ‘what stuff are we doing?’ or ‘why are we doing this stuff?’. We can apply (and are applying actually) this model to the solving concrete and immediate issue, but we also could extend it to the whole platform conceptual, architectural and further implementation design and details.

For any reasonably complex problem / system there is always a path from where we are to where we want to be, therefore any implementation step (‘how’) will only cover part of the path to where we want to be (‘what’). The ‘why’ here is a context based on which we do the decisions of how to navigate that path. What is important is to keep the context clear and navigate the path step by step, making sure that we do not lose the big picture. The last sentence pretty much summarizes my general approach of relation between ‘declarative semantics’ (‘what are we doing?’) and ‘operational semantics’ (‘how are going it?’).

Search and Matching & Constraint Satisfaction #

As we know, the goal of the job orchestration sequence is to find an overlap between two spaces (for the starters, we can think in terms of each ensemble / computing workflow that is submitted to the network): (1) job requirements of each ensemble and (2) available machines in the network. One way to think about this is that it is a constraint satisfaction problem, where the constraints are specified in terms of job requirements and machine capabilities. In principle that is all correct, except that usual constraint satisfaction approaches do not work here, because (1) the space of requirements and machine properties is close to infinite and trying to do optimal constraint satisfaction will surely lead to the combinatorial explosion; (2) the space of machine configurations and their properties is not stable, since the very goal of NuNet platform is to operate on heterogenous network of independently owned and controller devices which can connect / disconnect and change their preferences at will. A third aspect of the picture is that we want both both machine providers and users f the network (so the ones which submit jobs/ensembles) to be able to express arbitrary preferences and constraints – which pushes the search&matching/constraint satisfaction problem even further towards the cliff of combinatorial explosion.

Some prior research work that informs my thoughts on this (along the whole conceptual design of the NuNet platform) can be found in the opening sections of this and this chapters of the research done on ‘OfferNetworks’ research project of SNET. This research is not an ultimate source of truth of course, but gives good enough foundations to frame the problem and possible approaches to it.

Ordering and Comparable interface #

Comparable interfaces as far as I know and understand are the interfaces that define ordering relations between variables of chosen type. Usually, the ordering relations are defined for natural numbers, numeric types, strings, etc, where such comparator interfaces express ’natural’ ordering relations between members of sets (or something in this spirit). That does not mean that one cannot define ordering relations via comparison operators for other types, including composite types, in our case machine resources, or GPUs or even ensembles of machines (e.g. cloud providers, etc). In this case, Comparable interface would actually define an ordering relation the way it is needed. I this sense, at least in the space of a programming language constructs, there are no ’natural’ orders – they have to be explicitly defined and implemented.

A more relevant question is ‘do we need such ordering for all variables that are involved in the search&matching / constrain satisfaction problem that we are solving?’. In principle, i do not see how can any constraint satisfaction problem be solved without defining ordering / comparison relations between all variables involved in that problem. That was the idea behind defining and enforcing [Comparable interface in the first place] ( https://gitlab.com/search?group_id=6160918&project_id=35912922&repository_ref=main&scope=issues&search=comparable). This ‘declarative design’ does have problems though, at least with respect to two aspects:

Since we have different types which are not ’naturally’ comparable (like executors, locations, etc.) and we need to define how we compare them for each time, there is a limit how much we can do with a single Comparable interface;
Since not all variables are of the same importance, we may need to do constraint satisfaction for each property of a machine separately, therefore comparison / ordering operations between these variables can be defined separately without enforcing single Comparable interface for them.
On the other and, eventual result of the search and matching problem will be ordering of machines according to some (potentially user-defined as Preferences) criteria, therefore there is a point to have a notion of ability to compare / order machines with all their properties. In that sense, if we have a constraint on a job / ensemble that it needs 4 GPUs and run in EU, these constraints are equally important to pick a machine and therefore I would are qualitatively equivalent in constraint satisfaction sense.
The immediate practical problem now is not exactly ordering machines (which I would argue will eventually be needed, otherwise we cannot really achieve asymptotically optimal results), but to define how we express machine properties and job/ensemble requirements in a way that requirements can be matched against properties in a clear and computable way. My idea with the Comparable interface was to describe both using the same variable types, define how we compare them – and only then define constraints on the basis of these comparison operators (as I do not even know how to define constraint without having a notion of comparing variables involved in the property that is being estimated for constraint satisfaction).

‘Decentralized’ vs ‘Centralized’ #

The fun with decentralized vs centralized constraint satisfaction is that there is not way to pull all available constraints in one central place and estimate them ‘optimally’ – which is the point of us building a ‘decentralized search and matching’ into the platform with the idea that i will be able to asymptotically move towards more optimal solutions. However, in order to do that, we have to consider not only which variables we are comparing and which properties we are defining for jobs / machines, but also which ones we check first and which ones later. If we take the overall graph computing aspect of the ‘open-ended decentralized computing’ notion (in terms of ‘declarative semantics’), this relates to the efficient routing problem (i.e. what is the pattern by which BidRequests reach machines and Bids are submitted). Before the graph computing package is developed, however, in [more or less] full swing, we most probably have to take the ‘operational semantics’ approach as primary and move forward.

Having said this, with each choice of ‘how’ we do things (in ‘operational semantics’ sense), I think it is always important to keep tabs on how it relates to ‘what’ we are doing (in ‘declarative semantics’ sense) and to have at least approximate mapping between the two until we get to a place where ‘declarative semantics’ and ‘operational semantics’ will express the same thing – but that will take a while, because we will reach this place when the platform will be fully implemented.

Maintainer: @kabir.kbr (please tag all edit merge requests accordingly)