Paulo Trezentos
Inês Lynce
Arlindo L. Oliveira
ABSTRACT
The installation of software packages depends on the correct resolution of dependencies and conflicts between packages. This problem is NP-complete and, as expected, is a hard task. Moreover, today's technology still does not address this problem in an acceptable way. This paper introduces a new approach to solving the software dependency problem in a Linux environment, devising a way for solving dependencies according to available packages and user preferences. This work introduces the "apt-pbo" tool, the first publicly available tool that solves dependencies in a complete and optimal way.
- }}B. Alidaee, H. Wang, and Y. Xu. A pseudo-boolean optimization for multiple criteria decision making in complex systems. In Proceedings of the 7th international conference on Computational Science (ICCS '07), Part IV, pages 194--201, Berlin, Heidelberg, 2007. Springer-Verlag. Google Scholar
Digital Library
- }}P. Barth. A Davis-Putnam based enumeration algorithm for linear pseudo-Boolean optimization. Technical report, Technical Report MPI-I-95-2-003, Max Planck Institute., 1995.Google Scholar
- }}D. L. Berre, O. Roussel, and L. Simon. International SAT 2009 competition, 2009. http://www.satcompetition.org/2009/.Google Scholar
- }}L. Bixin. Managing dependencies in component-based systems based on matrix model. In NETObjectDays'03, 2003.Google Scholar
- }}D. Burrows. Modelling and resolving software dependencies, 2005. Debian.Google Scholar
- }}D. Di Ruscio, P. Pelliccione, A. Pierantonio, and S. Zacchiroli. Towards maintainer script modernization in foss distributions. In Proceedings of the 1st international workshop on Open component ecosystems (IWOCE '09), pages 11--20, New York, NY, USA, 2009. ACM. Google ScholarDigital Library
- }}N. Eéen and N. Sörensson. Translating pseudo-Boolean constraints into SAT. Journal on Satisfiability, Boolean Modeling and Computation, 2:1--26, March 2006.Google ScholarCross Ref
- }}M. Ehrgott. Multicriteria optimization. Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, 2000. Google ScholarDigital Library
- }}M. Ehrgott and X. Gandibleux. A survey and annoted bibliography of multiobjective combinatorial optimization. OR Spektrum, 2000.Google Scholar
- }}F. Heras, V. Manquinho, and J. Marques-Silva. On applying unit propagation-based lower bounds in pseudo-Boolean optimization. In Proceedings of International FLAIRS Conference, 2008.Google Scholar
- }}N. LaBelle and E. Wallingford. Inter-package dependency networks in open-source software. Technical report, Computer Science Department, University of Northern Iowa, 2004.Google Scholar
- }}D. Le Berre and A. Parrain. On SAT technologies for dependency management and beyond. ASPL, 2008.Google Scholar
- }}D. Le Berre and P. Rapicault. Dependency management for the eclipse ecosystem: eclipse p2, metadata and resolution. In Proceedings of the 1st international workshop on Open component ecosystems(IWOCE '09), pages 21--30, New York, NY, USA, 2009. ACM. Google ScholarDigital Library
- }}F. Mancinelli, J. Boender, R. Di Cosmo, J. Vouillon, B. Durak, X. Leroy, and R. Treinen. Managing the complexity of large free and open source package-based software distributions. In International Conference on Automated Software Engineering (ASE'06), pages 199--208. IEEE Computer Society, 2006. Google ScholarDigital Library
- }}P. Manolios, D. Vroon, and G. Subramanian. Automating component-based system assembly. In Proceedings of the 2007 international symposium on Software testing and analysis (ISSTA '07), pages 61--72, New York, NY, USA, 2007. ACM. Google ScholarDigital Library
- }}V. Manquinho, J. Marques-Silva, and J. Planes. Algorithms for weighted boolean optimization. In Proceedings of the 12th International Conference on Theory and Applications of Satisfiability Testing, 2009. Google ScholarDigital Library
- }}V. Manquinho and O. Roussel. PBO competition 2009, 2009. http://www.cril.univ-artois.fr/PB09/.Google Scholar
- }}S. Mouthuy, L. Quesada, and G. Doom. Search heuristics and optimisations to solve package installability problems by constraint programming. Technical report, Department of CSE, UC Louvain, October 2006.Google Scholar
- }}G. Niemeyer. Smart package manager, 2009. http://labix.org/smart.Google Scholar
- }}R. D. C. Pietro Abate, Jaap Boender and S. Zacchiroli. Strong dependencies between software components. In Proceedings of 3rd International Symposium on Empirical Software Engineering and Measurement (ESEM '09), 2009. Google ScholarDigital Library
- }}D. project. Debian popularity contest, 2009. http://popcon.debian.org/.Google Scholar
- }}O. Roussel and V. M. Manquinho. Pseudo-Boolean and cardinality constraints. In A. Biere, M. Heule, H. van Maaren, and T. Walsh, editors, Handbook of Satisfiability, volume 185 of Frontiers in Artificial Intelligence and Applications, pages 695--733. IOS Press, 2009.Google Scholar
- }}H. M. Sheini and K. A. Sakallah. Pueblo: A hybrid pseudo-boolean sat solver. Journal on Satisfiability, Boolean Modeling and Computation, 2:2006, 2006.Google Scholar
- }}J. A. Stafford and A. L. Wolf. Architecture-level dependence analysis in support of software maintenance. In Proceedings of the third international workshop on Software architecture (ISAW '98), pages 129--132, New York, NY, USA, 1998. ACM. Google ScholarDigital Library
- }}R. Treinen and S. Zacchiroli. Expressing advanced user preferences in component installation. In Proceedings of the 1st international workshop on Open component ecosystems (IWOCE '09), pages 31--40, New York, NY, USA, 2009. ACM. Google ScholarDigital Library
- }}P. Trezentos. Apt-pbo homepage, 2009. http://aptpbo.caixamagica.pt/.Google Scholar
- }}P. Trezentos, R. Di Cosmo, L. Lauriére, M. Morgado, J. Abecasis, F. Mancinelli, and A. Oliveira. New Generation of Linux Meta-installers. Research Track of FOSDEM 2007, 2007.Google Scholar
- }}C. Tucker, D. Shufflelton, R. Jhala, and S. Lerner. Opium: Optimal package install/uninstall manager. In 29th International Conference on Software Engineering (ICSE 07), pages 178--188, 2007. Google ScholarDigital Library
- }}M. Vieira and D. Richardson. Analyzing dependencies in large component-based systems. In Proceedings of the 17th IEEE international conference on Automated Software Engineering (ASE '02), page 241, Washington, DC, USA, 2002. IEEE Computer Society. Google ScholarDigital Library
- }}I.-C. Yoon, A. Sussman, A. Memon, and A. Porter. Effective and scalable software compatibility testing. In Proceedings of the 2008 international symposium on Software testing and analysis (ISSTA '08), pages 63--74, New York, NY, USA, 2008. ACM. Google ScholarDigital Library
- }}S. Zacchiroli, R. Di Cosmo, and P. Trezentos. Package upgrades in FOSS distributions: Details and challenges. In First ACM Workshop on Hot Topics in Software Upgrades (HotSWUp), October 2008. Google ScholarDigital Library
Index Terms
- Apt-pbo: solving the software dependency problem using pseudo-boolean optimization
Recommendations
APT: a data structure for optimal control dependence computation
PLDI '95: Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementationThe control dependence relation is used extensively in restructuring compilers. This relation is usually represented using the control dependence graph; unfortunately, the size of this data structure can be quadratic in the size of the program, even for ...
APT: a data structure for optimal control dependence computation
The control dependence relation is used extensively in restructuring compilers. This relation is usually represented using the control dependence graph; unfortunately, the size of this data structure can be quadratic in the size of the program, even for ...
Combinatorial Optimization Solutions for the Maximum Quartet Consistency Problem
RCRA 2008 Experimental Evaluation of Algorithms for Solving Problems with Combinatorial ExplosionPhylogenetic analysis is a widely used technique, for example in biology and biomedical sciences. The construction of phylogenies can be computationally hard. A commonly used solution for construction of phylogenies is to start from a set of biological ...
Comments