Why does libperconaserverclient18 package metadata not include a Provides-field with libmysqlcient18? Provides: libmysqlclient18 That would probably fix this issue (and I think we had that issue before) and libmysqlclient18.1 seems to do this right: aptitude show libperconaserverclient18 :( Package: libperconaserverclient18 New: yes State: not installed Version: 5.5.37-rel35.1-666.wheezy Priority: extra Section: libs Maintainer: Percona Server Development Team