All distributions use some kind of meta-data describing relationships between packages such as Dependencies, Conflicts, Virtual Packages, etc. Existing package managers are often specific to a packaging format, or even use implicit assumptions on the meaning of package relations in the context of a distribution. This talk addresses the issue of how we can overcome this seclusion by resolving inter-package relations in a way that is independent from a specific distribution. We will present CUDF (Common Upgradeability Description Format) which permits to encode upgrade scenarios coming from different packaging systems, including in particular .deb-based and .rpm-based distributions. The format comes with a clear semantics which makes it possible to share resolution tools among distributions, and to adapt general-purpose solvers to the needs of FLOSS distributions. We also show how, in the context of the Mancoosi project, we are using the CUDF format to improve the solving abilities of state-of-the-art package managers in distributions such as Debian, Mandriva, and Caixa Magica.