Gerdus Benade (MSc - Operations Research).

Designing a distributed framework for the enumeration of MOLS

Latin squares have been the subject of study since Leonard Euler posed the so-called 36-officers problem in 1782. A Latin square of order n is an nxn array containing the symbols 0,1,…,n-1, such that no symbol is repeated in any row or column. Two Latin squares are considered orthogonal if all the superimposed ordered pairs of symbols, one pair for every position in the matrix, are distinct. Latin squares, specifically sets of k pairwise orthogonal Latin squares (k-MOLS), have been shown to have applications in various fields, ranging from experimental design to sports tournament scheduling and the design of error-correcting codes.

The number of distinct Latin squares have been shown to grow exponentially as a function of the order of the square, making the enumeration of equivalence classes of Latin squares very challenging. The exact number of main classes of Latin squares are still unknown for all but the smallest orders. In addition, the existence of a 3-MOLS of order 10 remains unresolved.

Volunteer or distributed computing projects have employed the idle computing resources of hundreds of thousands of users since 1996 and have proven to be a very valuable facilitation of  computationally expensive algorithms. From the finding of large Mersenne primes to different protein-folding models and the factorisation of very large integers (something which is crucial for internet security), distributed computing has enabled computations and discoveries that would otherwise have lain in wait for decades.  The enumeration of sets of orthogonal Latin squares is another such a computationally expensive prospect which may benefit from large-scale distribution.

Various frameworks exist for the design of distributed computing projects.   The current frontrunner seems to be the Berkeley Open Infrastructure for Network Computing, or BOINC.  After implementing an algorithm that enumerates the main classes of MOLS, a BOINC project will be launched for the enumeration of 3-MOLS.  The success of this project and the results obtained will then serve as a proof-of-concept that the use of volunteer computing is computationally feasible in the enumeration of 3-MOLS of small order.

My contact details: jgbenade@ml.sun.ac.za