The meta-distro reproducible package manager

01 Jan 2023

Use Linux because of its strong ecosystem of package managers: a uniform interface to the vast universe of software. I remember the seams of downloading installers and zip files manually back when I used Widnows. I would have to navigate every company’s (sluggish) website and click this and that and hope I didn’t just get subscribed to an email list. When I was done using the software, I would try in vain to delete it using the “Add or remove programs” feature, only to see its residue in assorted folders months later. However, this is a non-issue for 99.9% of users who just need to surf the web or use creative tools without worrying about such things as memory and disk utilization. All is fine because every program statically links their dependencies in with them. But step foot into developing that software, and realize what a cumbersome ecosystem this is. Command Prompt feels like it was made in the 90s (it was actually made in ‘87, so this is a compliment). Those who manage to install git in Powershell have earned my respect. Package managers were born to solve this headache algorithmically, enabling reproducible changes to the state of the system. This interface enables nice things like dynamically linkable libraries, scriptable environment creation, and avoidance of dependency-hell.

Thus emerged the symbiotic relationship between the operating system and her package manager, bonded to the point that the latter tends to define the former. Package managers evolved such that the 0.09% of people who were unsatisfied with the DOS way of doing things could harmoniously develop their software without too many It works on my machine issues. However, there are damned 0.01% who will remain unsatisfied until every package can be perfectly declared and composed, no conflicts between processes, and no diamond dependencies, either out of genuine business need for reproducibility, or out of OCD. As a proud member of the latter bucket, I’ve come up with a new package management scheme based on the old paravirtualization techniques of Xen, with the goal of eliminating the distinction between distributions entirely.

From Algorithmic Efficiency to NP-Completeness

However, package management isn’t just difficult, it’s actually the hardest problem whose solution can be easily verified. Well when I say hardest, I’m lying a little bit. It actually has an infinite number of twins that are really the same problem stated in different languages, and this family is the set NP-complete. You’ve certainly come across members of this family, like TSP or SAT. But before VERSION can join this covenant, we need to demonstrate two things about it. 1 that a solution can be easily verified, and 2 it can be used to solve a problem from that family. 2 means that VERSION would be at least as hard as every other problem in NP-complete, because if a fast algorithm was found for version, even if the algorithm had runtime O(n^10^1000), then every member of NP-complete was actually easy all along and the whole family was scamming mathematicians for centuries. This decision problem in particular, called VERSION, involves determining a viable configuration of software versions and dependencies that satisfies a given set of constraints. Here’s how it maps to a broader computational context:

VERSION Problem: Given a set 𝑃 of packages, each with 𝑉 versions and 𝐷 dependencies, and a required package 𝑝 in 𝑃 can you select one version of every transitive dependency in 𝑃? This problem is not only about selecting compatible software versions; it’s about ensuring that entire systems maintain coherence amid a sprawling web of dependencies—a task that mirrors the complexity of well-known NP-complete problems like the Boolean satisfiability problem (SAT).

DISCLAIMER: Most of this rough draft was written by GPT-4 given my ideas. As such, the content is incomplete and factually ungrounded. Please check back in 2 weeks for the full version now that I have free time.

Graph-Theoretic Approaches to Dependency Resolution

Viewing the dependency resolution problem through a graph-theoretic lens offers a clearer visual and computational framework. Dependencies naturally form a directed graph, with nodes representing software packages and edges denoting dependency requirements. This structure aids in understanding and devising more efficient algorithms for resolving dependencies, moving beyond brute-force methods towards more strategic, graph-based approaches.

One such approach is the COLLAPSE-K-PARTITIONS (CKP) problem, a specialized form of graph partitioning that seeks a subgraph containing exactly one vertex from each partition, starting from a root vertex representing the primary software package. This model not only aids in visualizing the dependency problem but also in streamlining the resolution process by reducing it to manageable sub-problems.

Beyond Traditional Package Management

The dynamic nature of software development, characterized by continuous updates and iterations, demands that package managers not only install and update software but also anticipate and manage the evolution of dependencies. This requirement has led to the conceptualization of meta-distros—distributions that can adapt to a wide array of software environments through advanced file system features like OverlayFS.

OverlayFS, a union file system that allows multiple file systems to be overlaid, one on top of the other, provides a powerful abstraction for package management. It enables the construction of complex software environments that are both isolated and reproducible, mimicking the behavior of a software package within its native distribution without the overhead of duplicating its dependencies across different environments.

Rethinking Dependency Management: A Modular Approach

The challenge of NP-completeness in dependency management has inspired a reevaluation of how dependencies are defined and resolved. Traditional models, which rigidly adhere to specific versions and configurations, can be relaxed to allow for more flexibility and adaptability in software management. This flexibility can be achieved through a modular package management system that:

Utilizes the latest kernel features like namespaces and cgroups to manage dependencies more efficiently. Implements a more granular approach to dependency specification, potentially reducing the complexity of resolving these dependencies. Innovations in Package Management

The future of package management lies in leveraging cutting-edge technologies and paradigms, including AI, to streamline the process. AI can be particularly effective in automating the resolution of complex dependency graphs, predicting future dependency conflicts, and optimizing software configurations for specific user environments.

As we advance, the integration of more sophisticated computational models and the adoption of flexible, graph-based approaches will continue to revolutionize package management. By abstracting complexity and embracing modularity, we can transform the landscape of software management, making it more adaptable to the diverse and evolving needs of users and developers alike.

In essence, the meta-distro approach to package management isn’t just about managing software—it’s about redefining how we interact with software distribution systems, ensuring that our tools are as dynamic and capable as the systems they support.