- -

Supercomputing and grid computing on the verification of covering arrays

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

Supercomputing and grid computing on the verification of covering arrays

Show simple item record

Files in this item

dc.contributor.author Avila George, Himer es_ES
dc.contributor.author Torres Jimenez, Jose es_ES
dc.contributor.author Rangel Valdez, Nelson es_ES
dc.contributor.author Carrión Collado, Abel Antonio es_ES
dc.contributor.author Hernández García, Vicente es_ES
dc.date.accessioned 2014-06-04T12:31:40Z
dc.date.issued 2012-11
dc.identifier.issn 0920-8542
dc.identifier.uri http://hdl.handle.net/10251/37921
dc.description The final publication is available at Springer via http://dx.doi.org/10.1007/s11227-012-0763-0 es_ES
dc.description.abstract The Covering Arrays (CAs) are mathematical objects with minimal coverage and maximum cardinality that are a good tool for the design of experiments. A covering array is an Nxk matrix over an alphabet v s.t. each Nxk subset contains at least one time each combination from {0,1,...,v ,1}t, given a positive integer value t. The process of ensuring that a CA contains each of the v t combinations is called verification of CA. In this paper, we present an algorithm for CA verification and its implementation details in three different computation paradigms: (a) sequential approach (SA); (b) parallel approach (PA); and (c) Grid approach (GA). Four different PAs were compared in their performance of verifying a matrix as a CA; the PA with the best performance was included in a different experimentation where the three paradigms, SA, PA, and GA were compared in a benchmark composed by 45 possible CA instances. The results showed the limitations of the different paradigms when solving the verification of CA problem, and points out the necessity of a Grid approach to solve the problem when the size of a CA grows. © 2012 Springer Science+Business Media, LLC. es_ES
dc.description.sponsorship The authors thankfully acknowledge the computer resources and assistance provided by Spanish Supercomputing Network (TIRANT-UV). This research work was partially funded by the following projects: CONACyT 58554, Calculo de Covering Arrays; 51623 Fondo Mixto CONACyT y Gobierno del Estado de Tamaulipas. en_EN
dc.format.extent 30 es_ES
dc.language Inglés es_ES
dc.publisher Springer Verlag (Germany) es_ES
dc.relation CONACyT 58554, Calculo de Covering Arrays es_ES
dc.relation 51623 Fondo Mixto CONACyT es_ES
dc.relation Gobierno del Estado de Tamaulipas es_ES
dc.relation.ispartof Journal of Supercomputing es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Covering array es_ES
dc.subject Combinatorial testing es_ES
dc.subject Supercomputing es_ES
dc.subject Grid computing es_ES
dc.subject.classification CIENCIAS DE LA COMPUTACION E INTELIGENCIA ARTIFICIAL es_ES
dc.title Supercomputing and grid computing on the verification of covering arrays es_ES
dc.type Artículo es_ES
dc.embargo.lift 10000-01-01
dc.embargo.terms forever es_ES
dc.identifier.doi 10.1007/s11227-012-0763-0
dc.rights.accessRights Cerrado es_ES
dc.contributor.affiliation Universitat Politècnica de València. Instituto de Instrumentación para Imagen Molecular - Institut d'Instrumentació per a Imatge Molecular es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation Avila George, H.; Torres Jimenez, J.; Rangel Valdez, N.; Carrión Collado, AA.; Hernández García, V. (2012). Supercomputing and grid computing on the verification of covering arrays. Journal of Supercomputing. 62(2):916-945. doi:10.1007/s11227-012-0763-0 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion http://link.springer.com/article/10.1007%2Fs11227-012-0763-0 es_ES
dc.description.upvformatpinicio 916 es_ES
dc.description.upvformatpfin 945 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 62 es_ES
dc.description.issue 2 es_ES
dc.relation.senia 238339
dc.relation.references Avila-George H, Torres-Jimenez J, Hernández V, Rangel-Valdez N (2010) Verification of general and cyclic covering arrays using Grid computing. In: Proceedings of the 3rd international conference on data management in grid and peer-to-peer systems, GLOBE 2010, Bilbao, Spain, 30 August–3 September. Lecture notes in computer science, vol 6265. Springer, Berlin, pp 112–123. doi: 10.1007/978-3-642-15108-8_10 es_ES
dc.relation.references Bryce RC, Colbourn CJ (2007) The density algorithm for pairwise interaction testing. Softw Test Verif Reliab 17(3):159–182. doi: 10.1002/stvr.365 es_ES
dc.relation.references Burr K, Young W (1998) Combinatorial test techniques: table-based automation, test generation and code coverage. In: Proceedings of the international conference on software testing, analysis, and review—STAR, pp 503–513. West, 1998 es_ES
dc.relation.references Bush KA (1952) Orthogonal arrays of index unity. Ann Math Stat 23(3):426–434. doi: 10.1214/aoms/1177729387 es_ES
dc.relation.references Calvagna A, Gargantini A, Tramontana E (2009) Building T-wise combinatorial interaction test suites by means of grid computing. In: Proceedings of the 18th IEEE international workshops on enabling technologies: infrastructures for collaborative enterprises—WETICE 2009. IEEE Comput Soc, Los Alamitos, pp 213–218. doi: 10.1109/WETICE.2009.52 es_ES
dc.relation.references Cawse JN (2003) Experimental design for combinatorial and high throughput materials development. Wiley, New York es_ES
dc.relation.references Cheng C (2007) The test suite generation problem: optimal instances and their implications. Discrete Appl Math 155:1943–1957. doi: 10.1016/j.dam.2007.04.010 es_ES
dc.relation.references Cohen DM, Dalal SR, Parelius J, Patton GC (1996) The combinatorial design approach to automatic test generation. IEEE Softw 13(5):83–88. doi: 10.1109/52.536462 es_ES
dc.relation.references Cohen MB, Colbourn CJ, Ling ACH (2003) Augmenting simulated annealing to build interaction test suites. In: Proceedings of the 14th international symposium on software reliability engineering—ISSRE 2003. IEEE Comput Soc, Los Alamitos, pp 394–405. http://doi.ieeecomputersociety.org/10.1109/ISSRE.2003.1251061 es_ES
dc.relation.references Colbourn CJ (2004) Combinatorial aspects of covering arrays. Matematiche 59(1, 2):125–172 es_ES
dc.relation.references Colbourn CJ (2011) Covering array tables for t=2,3,4,5,6. URL: http://www.public.asu.edu/~ccolbou/src/tabby/catable.html . Accessed on April 20 es_ES
dc.relation.references Colbourn CJ, Kéri G (2009) Binary covering arrays and existentially closed graphs. In: Proceedings of the 2nd international workshop on coding and cryptology—IWCC 2009. Lecture notes in computer science, vol 5557. Springer, Berlin, pp 22–33. doi: 10.1007/978-3-642-01877-0_3 es_ES
dc.relation.references Colbourn CJ, Ling ACH (2009) A recursive construction for perfect hash families. J Math Cryptol 3(4):291–306. doi: 10.1515/JMC.2009.018 es_ES
dc.relation.references Colbourn CJ, Martirosyan SS, Mullen GL, Shasha D, Sherwood GB, Yucas JL (2006) Products of mixed covering arrays of strength two. J Comb Des 12(2):124–138. doi: 10.1002/jcd.20065 es_ES
dc.relation.references Colbourn CJ, Torres-Jimenez J (2010) Heterogeneous hash families and covering arrays. In: Error-correcting codes, finite geometries and cryptography. Contemporary mathematics, vol 523. pp 3–15. ISBN-10 0-8218-4956-5 es_ES
dc.relation.references DIANE (2011) Distributed analysis environment. URL: http://it-proj-diane.web.cern.ch/it-proj-diane/ . Accessed on June 6 es_ES
dc.relation.references Foster I, Kesselman C (1999) The grid: blueprint for a new computing infrastructure. Morgan Kaufmann, San Mateo es_ES
dc.relation.references Seroussi NBG (1988) Vector sets for exhaustive testing of logic circuits. IEEE Trans Inf Theory 34:513–522 es_ES
dc.relation.references Gonzalez-Hernandez L, Rangel-Valdez N, Torres-Jimenez J (2010) Construction of mixed covering arrays of variable strength using a tabu search approach. In: Proceedings of the 4th international conference on combinatorial optimization and applications, COCOA, 2010. Lecture notes in computer science, vol 6508. Springer, Berlin, pp 51–64. doi: 10.1007/978-3-642-17458-2_6 es_ES
dc.relation.references Hedayat AS, Sloane NJA, Stufken J (1999) Orthogonal arrays: theory and applications. Springer, Berlin es_ES
dc.relation.references Katona GOH (1973) Two applications (for search theory and truth functions) of Sperner type theorems. Period Math Hung 3(1–2):19–26. doi: 10.1007/BF02018457 es_ES
dc.relation.references Kleitman DJ, Spencer J (1973) Families of k-independent sets. Discrete Math 6(3):255–262. doi: 10.1016/0012-365X(73)90098-8 es_ES
dc.relation.references Kuhn R, Lei Y, Kacker R (2008) Practical combinatorial testing: beyond pairwise. IT Prof 10(3):19–23. doi: 10.1109/MITP.2008.54 es_ES
dc.relation.references Lawrence J, Kacker R, Lei Y, Kuhn D, Forbes M (2011) A survey of binary covering arrays. Electron J Comb 18(1):84 es_ES
dc.relation.references Lei Y, Kacker R, Kuhn DR, Okun V, Lawrence J (2007) IPOG: a general strategy for t-way software testing. In: Proceedings of the 14th annual IEEE international conference and workshops on the engineering of computer-based systems—ECBS 2007. IEEE Comput Soc, Los Alamitos, pp 549–556. doi: 10.1109/ECBS.2007.47 es_ES
dc.relation.references Martinez-Pena J, Torres-Jimenez J, Rangel-Valdez N, Avila-George H (2010) A heuristic approach for constructing ternary covering arrays using trinomial coefficients. In: Proceedings of the 12th Ibero-American conference on artificial intelligence—IBERAMIA 2010. Lecture notes in computer science, vol 6433. Springer, Berlin, pp 572–581. doi: 10.1007/978-3-642-16952-6_58 es_ES
dc.relation.references Martirosyan SS, Colbourn CJ (2005) Recursive constructions of covering arrays. Bayreuth Math Schr 74:266–275 es_ES
dc.relation.references McDowell AG (2011) All-pairs testing. URL: http://www.mcdowella.demon.co.uk/allPairs.html . Accessed on June 21 es_ES
dc.relation.references Moscicki J, Brochu F, Ebke J, Egede U, Elmsheuser J, Harrison K, Jones R, Lee H, Liko D, Maier A, Muraru A, Patrick G, Pajchel K, Reece W, Samset B, Slater M, Soroko A, Tan C, van der Ster D, Williams M (2009) Ganga: a tool for computational-task management and easy access to grid resources. Comput Phys Commun 180(11):2303–2316. doi: 10.1016/j.cpc.2009.06.016 es_ES
dc.relation.references Moura L, Stardom J, Stevens B, Williams A (2003) Covering arrays with mixed alphabet sizes. J Comb Des 11(6):413–432. doi: 10.1002/jcd.10059 es_ES
dc.relation.references National Institute of Standards and Technology (2011) NIST covering array tables. URL: http://math.nist.gov/coveringarrays/ . Accessed on April 20 es_ES
dc.relation.references Nurmela KJ (2004) Upper bounds for covering arrays by tabu search. Discrete Appl Math 138:143–152. doi: 10.1016/S0166-218X(03)00291-9 es_ES
dc.relation.references Pacini F (2011) Job description language howto. URL: http://server11.infn.it/workload-grid/docs/DataGrid-01-TEN-0102-0_2-Document.pdf . Accessed on October 10 es_ES
dc.relation.references Phadke MS (1995) Quality engineering using robust design. Prentice Hall, New York es_ES
dc.relation.references Rényi A (1971) Foundations of probability. Wiley, New York es_ES
dc.relation.references Shasha DE, Kouranov AY, Lejay LV, Chou MF, Coruzzi GM (2001) Using combinatorial design to study regulation by multiple input signals: a tool for parsimony in the post-genomics era. Plant Physiol 127(4):1590–1594. doi: 10.1104/pp.010683 es_ES
dc.relation.references Sherwood GB (2008) Optimal and near-optimal mixed covering arrays by column expansion. Discrete Math 308(24):6022–6035. doi: 10.1016/j.disc.2007.11.021 es_ES
dc.relation.references Sherwood GB (2011) On the construction of orthogonal arrays and covering arrays using permutation groups. URL: http://testcover.com/pub/background/cover.htm . Accessed on June 20 es_ES
dc.relation.references Shiba T, Tsuchiya T, Kikuno T (2004) Using artificial life techniques to generate test cases for combinatorial testing. In: Proceedings of the 28th annual international computer software and applications conference, vol 01, COMPSAC 2004. IEEE Comput Soc, Los Alamitos, pp 72–77. doi: 10.1109/CMPSAC.2004.1342808 es_ES
dc.relation.references Torres-Jimenez J, Avila-George H, Rangel-Valdez N, Gonzalez-Hernandez L (2012) Construction of orthogonal arrays of index unity using logarithm tables for galois fields. In Cryptography. InTech, pp 71–90. ISBN 978-953-51-0179-6 es_ES
dc.relation.references Torres-Jimenez J, De Alfonso C, Hernández V (2004) Computation of ternary covering arrays using a grid. In: Proceedings of the second Asian applied computing conference—AACC 2004. Lecture notes in computer science, vol 3285. Springer, Berlin, pp 240–246. doi: 10.1007/978-3-540-30176-9_31 es_ES
dc.relation.references Torres-Jimenez J, Rangel-Valdez N, Gonzalez-Hernandez AL, Avila-George H (2010) Construction of logarithm tables for Galois fields. Int J Math Educ Sci Technol 42(1):91–102. doi: 10.1080/0020739X.2010.510215 es_ES
dc.relation.references Torres-Jimenez J, Rodriguez-Tello E (2012) New bounds for binary covering arrays using simulated annealing. Inf Sci 185(1):137–152. doi: 10.1016/j.ins.2011.09.020 es_ES
dc.relation.references Tung Y, Aldiwan WS (2000) Automating test case generation for the new generation mission software system. In: Proceedings of the IEEE aerospace conference, vol 1. IEEE Press, New York, pp 431–437. doi: 10.1109/AERO.2000.879426 es_ES
dc.relation.references Vadde K, Syrotiuk V (2004) Factor interaction on service delivery in mobile ad hoc networks. IEEE J Sel Areas Commun 22(7):1335–1346. doi: 10.1109/JSAC.2004.829351 es_ES
dc.relation.references Williams AW (2000) Determination of test configurations for pair-wise interaction coverage. In: Proceedings of the IFIP TC6/WG6.1 13th International conference on testing communicating systems: tools and techniques—TestCom. Kluwer, Norwell, pp 59–74 es_ES
dc.relation.references Williams AW, Probert RL (1996) A practical strategy for testing pair-wise coverage of network interfaces. In: Proceedings of the seventh international symposium on software reliability engineering—ISSRE. IEEE Comput Soc, Los Alamitos, pp 246–256. doi: 10.1109/ISSRE.1996.558835 es_ES
dc.relation.references Yilmaz C, Cohen MB, Porter AA (2006) Covering arrays for efficient fault characterization in complex configuration spaces. IEEE Trans Softw Eng 32(1):20–34. doi: 10.1109/TSE.2006.8 es_ES
dc.relation.references Younis M, Zamli K, Isa N (2008) A strategy for grid based t-way test data generation. In: First international conference on distributed framework and applications—DFmA 2008, pp 73–78. doi: 10.1109/ICDFMA.2008.4784416 es_ES


This item appears in the following Collection(s)

Show simple item record