Dependency resolving in Package Managers: pacman vs apt vs dnf

Installing one package isn’t isolated

install nginx it actually needs:

nginx → openssl → libc → pcre → zlib so software deps form a graph, not a list.

humans can’t resolve graphs reliably.

that’s why package managers exist.

what package managers do:

given:

find:

valid install set satisfying all constraints

this is dependency graph + constraint solving.

To understand this more we need to understand what is a SAT solver

SAT = Boolean satisfiability problem

given:

find:

assignment of true/false so that the whole formula becomes TRUE

Example:

(A OR B) AND (NOT A OR C) assignment for this problem would be A=0, B=1, C=0

since formula is TRUE it’s a SAT

UNSAT example -> A AND (NOT A)

this formula is impossible

SAT is used in many areas:

how this SAT works in package managers:

nginx → openssl1.1 curl → NOT openssl1.1 system → openssl1.1 OR openssl1.0 for this problem the variables and constraints are,

Variables = N, O1, O0, C

O1 = openssl1.1

O0 = openssl1.0

constraints = N → O1, C → NOT O1, O1 OR O0

solver input form:

CNF(Conjunctive Normal Form) (AND of OR classes) — this you might have studied in your CS degree (i slept in class lol 🥲)

The following packages will be upgraded: openssl The following will be removed: curl(A OR B) (NOT A OR C) (D OR NOT C) which assignment satisfies all the classes?

N=1, O1=1, C=0, O0=0 -> this satsfies the so solution exists

1 = installed / true

0 = not installed / false

How solver searches (intuition)?

A = true? check constraints B = true? conflict backtrack B = false continue many systems use SAT:

so now you know dependency conflict isn’t just a random error it’s a UNSAT state.

now let’s come back to understand the solver differences in pacman, dnf and apt.

1. Pacman

pacman’s philosophy is very simple,

Behavior:

which means maintainers ensure all packages in the repo already work together,

so at any moment repo snapshot = one consistent universe

if they update any package they have to rebuild all other packages that depends on this and make sure a exactly one valid dependency graph.

which means Arch repo usually has:

openssl 3.0 ONLY

Older removed.

So dependency graph has single version per node

That massively simplifies solving.

Pacman does less SAT solving than apt/dnf.

That’s why Arch repos must stay consistent.

pacman -S nginx when you do this, Pacman does:

No branching. No alternatives. No SAT solving.

So effectively:

install latest deps from repo

2. apt(Debian/ubuntu)

Philosophy:

APT uses a real dependency resolver:

apt install nginx when you try to install nginx in apt, tis is what apt does.

The following packages will be upgraded: openssl The following will be removed: curl APT is solving a constraint satisfaction problem.

3. dnf (Fedora/RHEL)

Philosophy:

DNF uses libsolv

This is a full SAT solver.

It can handle:

So DNF resolution is mathematically strongest.

given package nodes, dependency edges, version constraints, conflicts

package managers has to find a valid install set.

other package mangers like npm, yarn, cargo, pip solves similar problems

after resolving package manager creates a topoloically sorted plan,

like this,

install openssl install pcre install zlib install nginx