A package manager automates the lifecycle of software dependencies: fetch, install, upgrade, configure, and remove. At scale, it answers the question:

Given a set of packages, each with version constraints on its own dependencies, does there exist a consistent assignment of versions such that every constraint is satisfied?

This is, at heart, a constraint-satisfaction problem — and different package managers attack it with different algorithms, trade-offs, and scopes of responsibility. This article surveys the landscape, unpacks the resolution mechanisms, and provides a decision framework for choosing the right tool.

1. What Is a Package?

• Payload: the actual binaries, libraries, headers, or source code.
• Metadata: name, version, description, license, checksums.
• Dependency constraints: a Boolean formula over package–version pairs, e.g. $\texttt{libssl} \geq 1.1 \land \texttt{libssl} < 2.0$.

A package manager’s job is to take a request (“install fastapi”) and produce a consistent install plan — a set of concrete versions that satisfy all constraints transitively.

2. System-Level Package Managers

2.1 APT & dpkg (Debian/Ubuntu)

APT (Advanced Package Tool) operates on .deb packages, a binary format consisting of an ar archive containing control.tar.gz (metadata + dependency constraints) and data.tar.gz (the payload — binaries placed under /usr/).

How resolution works

APT models the dependency graph as a set of (package, version) nodes. Each control file specifies Depends:, Conflicts:, Provides:, and Replaces: fields. The solver performs a heuristic-guided search:

1. Mark the requested package for installation.
2. Expand dependencies recursively — each Depends: clause must be satisfied by at least one installed or installable package.
3. Resolve conflicts — if two packages conflict or one Breaks: another, the solver backtracks and tries alternatives.
4. Score alternatives — APT prefers already-installed packages and higher version numbers, biasing toward minimal change.

1
2
3
4

# Inspect the dependency tree
apt-cache depends nginx
# Simulate an install plan without executing
apt install --dry-run nginx

APT is fundamentally a system-level manager: it installs into global paths (/usr/bin, /usr/lib). There is no per-project isolation — the entire OS shares one set of installed packages. This is why containers and virtual environments exist.

2.2 Homebrew (macOS / Linux)

Homebrew takes a different approach: it installs every package into its own prefix (a “keg”) under /usr/local/Cellar/<name>/<version>/, then symlinks selected files into /usr/local/bin/. This provides a form of version coexistence that APT lacks:

/usr/local/Cellar/
├── openssl@3/3.3.0/
│   ├── bin/openssl
│   └── lib/libssl.3.dylib
├── openssl@1.1/1.1.1w/
│   └── lib/libssl.1.1.dylib
└── python@3.12/3.12.3/
    └── bin/python3.12

Homebrew uses Ruby-based formulae as build recipes. A formula declares dependencies, and the resolver performs a topological sort of the complete dependency graph, installing everything from source or precompiled “bottles.” The key design difference from APT:

3. Language-Level Package Managers

3.1 pip & PyPI (Python)

pip is the de facto Python package installer, fetching from the Python Package Index (PyPI). It handles pure-Python packages well, but its limitation is the boundary between Python and the native world.

Resolution: from ad-hoc to backtracking

Historically, pip used a greedy first-fit resolver: iterate dependencies, pick the first compatible version, and pray there’s no conflict later. This was fast but unsound — it could produce broken environments, a notorious source of “works on my machine” bugs.

Since pip 20.3 (2020), the resolver uses a backtracking algorithm: when a conflict is detected, it unwinds to the point where the conflicting constraint was introduced and tries the next compatible version. This is sound but potentially slow — a worst-case exponential search over the version space.

1
2
3
4

# pip's dependency resolver with verbose output
pip install --dry-run fastapi 2>&1 | grep -E "Requirement|Collecting"
# Inspect what's actually installed
pipdeptree

The native-code gap

pip can install wheels (precompiled .whl files), but a wheel assumes the system provides required shared libraries (libssl.so, libffi.so). When those system libraries are absent or incompatible, you get inscrutable ImportError or Symbol not found errors. This is the gap Conda fills.

3.2 npm, Yarn & pnpm (JavaScript/Node)

The Node.js ecosystem has evolved three generations of package managers, each solving problems of the previous.

npm — Flat node_modules

myproject/
└── node_modules/
    ├── express/          ← direct dependency
    ├── accepts/          ← hoisted transitive dep
    ├── negotiator/       ← hoisted
    └── ...

npm v3+ flattens the dependency tree into a single node_modules/ directory. When two packages need different versions of the same dependency, the nested version is placed inside the dependent’s own node_modules/. This is non-deterministic — the hoisting order depends on installation order, which can lead to “phantom dependencies” (your code imports a package you didn’t explicitly declare because it was hoisted).

Yarn — Lockfile-driven determinism

Yarn introduced the yarn.lock file, which records the exact resolved version and integrity hash of every dependency. Combined with a deterministic resolution algorithm (breadth-first traversal with a fixed version preference), it guarantees that the same package.json + yarn.lock produces identical node_modules/ on every machine.

pnpm — Content-addressed storage

pnpm takes the idea further. Instead of copying packages into node_modules/, it uses hard links from a global content-addressable store:

~/.pnpm-store/
├── v3/
│   ├── files/            ← content-addressed by SHA-512 hash
│   └── index/
└── ...

myproject/
└── node_modules/
    └── .pnpm/
        ├── express@4.18.2/
        │   └── node_modules/
        │       └── express → hard link to ~/.pnpm-store/v3/files/...
        └── ...

This is directly analogous to Conda’s pkgs/ directory and uv’s global wheel cache — the same package is stored once on disk, shared across all projects.

3.3 Cargo (Rust)

Cargo is Rust’s build system and package manager, and it is notable for its unified approach: the same tool handles dependency resolution, compilation, testing, and publishing. Its lockfile, Cargo.lock, is the single source of truth for exact versions, and the resolver uses SemVer-aware backtracking — it understands that req >=1.2.3, <2.0.0 is compatible with 1.5.0 but not 2.0.0 by construction, because Rust’s SemVer convention (major.minor.patch) is enforced by tooling, not convention.

4. Conda: The Hybrid

Conda is neither a pure system-level manager nor a pure language-level one. It occupies a unique niche:

Conda’s SAT-based solver (see the Virtual Environment article, §2.3) models the problem as $n$ Boolean variables $p_v$ (install package $p$ at version $v$) with mutual-exclusion and implication clauses. This is strictly more expressive than pip’s backtracking resolver, because Conda must handle cross-language constraints (e.g., Python package A depends on C library B which depends on CUDA toolkit version C).

5. The Resolution Problem, Formalised

Let $\mathcal{P} = \{p_1, p_2, \dots, p_n\}$ be the set of all packages. Each package $p$ has a set of available versions $V(p)$. A dependency constraint is a Boolean formula $\phi$ over atoms of the form $p@v$, meaning “package $p$ at version $v$ is installed.”

Package Resolution Problem (PRP). Given a set of requested packages $R \subseteq \mathcal{P}$ with version constraints $\psi_p$ for each $p \in R$, find an assignment $\alpha \subseteq \{p@v : p \in \mathcal{P}, v \in V(p)\}$ such that:

1. $\alpha$ satisfies $\psi_p$ for all $p \in R$ (user request satisfaction).
2. For every $p@v \in \alpha$, $\alpha$ satisfies the dependency constraints of $p@v$ (transitive closure).
3. No two versions of the same package are in $\alpha$ (version uniqueness).

If no such $\alpha$ exists, report the minimal unsatisfiable core.

PRP is NP-complete (reduction from SAT). In practice, real dependency graphs are sparse and have structure that solvers exploit, but pathological cases (like npm’s node_modules/ with diamond-dependency conflicts) can cause exponential blowup.

Resolution Strategies

6. Semantic Versioning and Lockfiles

6.1 SemVer: A Social Contract

Semantic Versioning (SemVer) is a convention: MAJOR.MINOR.PATCH.

• MAJOR: incompatible API changes → must not auto-upgrade.
• MINOR: backward-compatible new functionality → safe to upgrade.
• PATCH: backward-compatible bug fixes → always safe.

The crucial word is convention. SemVer is not enforced — a package author can release a breaking change in a PATCH bump, and nothing stops them. Package managers trust SemVer: pip’s numpy>=1.20, <2.0 assumes all 1.x releases are compatible, but this is a social guarantee, not a technical one.

6.2 Lockfiles: Turning Trust into Certainty

A lockfile records the exact resolved version and content-hash of every transitive dependency:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

# Example: uv.lock (simplified)
[[package]]
name = "fastapi"
version = "0.115.2"
source = { registry = "https://pypi.org/simple" }
dependencies = [
    { name = "starlette" },
    { name = "pydantic" },
]

[[package]]
name = "pydantic"
version = "2.9.2"
source = { registry = "https://pypi.org/simple" }

Without a lockfile, pip install -r requirements.txt on different days may produce different results (a dependency released a new compatible version overnight). With a lockfile, the install is deterministic for a given lockfile, across time and across machines.

7. Common Failure Modes and Debugging

7.1 “Dependency Hell”

The classic scenario: package A depends on B v1, package C depends on B v2, and B v1 and B v2 are mutually exclusive.

Debugging:

1
2
3
4
5
6
7
8
9

# pip
pip install pipdeptree
pipdeptree --reverse --packages B  # who depends on B?

# npm
npm ls B                           # find all versions of B in the tree

# apt
apt-cache rdepends libB            # reverse dependencies

Mitigations:

• Diamond dependency: when A and C both depend on B, but with overlapping version ranges — resolve to a common compatible version.
• Dependency overrides: npm overrides, pip constraints, cargo [patch] — override a transitive dependency version globally. Dangerous but sometimes necessary.

7.2 “It Works on My Machine” — OS-Specific Wheel Failures

A requirements.txt that worked on macOS fails on a Linux server because a package’s macOS wheel was available but the Linux equivalent requires compilation from source, and the necessary system headers are missing.

1
2
3
4

# Check what platform a wheel targets
python -c "import pip; print(pip.pep425tags.get_platform())"
# Force pip to download source distributions (sdists) to verify compilability
pip install --no-binary :all: numpy

7.3 Stale Cache and Index Drift

A package author yanks a release from PyPI. Your requirements.txt pins an exact version that no longer exists. pip install fails despite nothing changing on your end.

1
2
3

# Check if a version is still available
pip index versions numpy
# Use a local package mirror (devpi, Artifactory) for air-gapped reproducibility

8. Choosing a Package Manager

Are you installing system tools (CLIs, daemons, compilers)?
├── Yes → Linux: apt / dnf. macOS: Homebrew.
└── No → Is the dependency within a single language ecosystem?
          ├── Yes → Use that language's package manager
          │         Python: uv (or pip/pip-tools)
          │         JavaScript: pnpm (or yarn)
          │         Rust: Cargo
          │         Go: go mod
          └── No → Do you need cross-platform binary reproducibility?
                    ├── Yes → Conda
                    └── No  → Docker (OS-level encapsulation)

The trend in 2025–2026 is toward unified, fast resolvers with content-addressed caches — uv for Python, pnpm for JavaScript, Cargo for Rust. All three share the architectural insight that packages should be stored once (content-addressed), installed via hard links or symlinks, and resolved deterministically via a lockfile. The days of copying megabytes of duplicate node_modules/ or site-packages/ into every project are numbered.

References

1. Abate, P. et al. “Dependency Solving: A Separate Concern in Component Evolution Management.” Journal of Systems and Software, 2013.
2. Pip documentation — Dependency Resolution
3. npm documentation — How npm handles conflicts
4. Conda documentation — Deep dive into the solver
5. PubGrub algorithm — Dart documentation
6. uv documentation — Resolver design
7. Cargo Book — Package resolution