Distributed Isomorph-free Exhaustive Generation of Anti-Pasch Partial Triple Systems

摘要

Anti-Pasch partial Steiner triple systems (anti-Pasch PSTSs) arise in erasure codes, extremal set systems and combinatorial design theory. Maximal anti-Pasch PSTSs correspond to erasure-resilient codes that are used for handling failures in large disk arrays. These codes support failure of any set of 3 disks and most sets of 4 disks while having the smallest possible update penalty and check-disk overhead. In this article, we apply a general algorithm for isomorph-free exhaustive generation of incidence structures to the specific case of anti-Pasch PSTSs. We develop and implement a distributed version of the algorithm, which is experimentally analysed. Using this implementation, we obtain a complete, isomorph-free catalogue of the maximal anti-Pasch PSTSs of order υ, for υ ≤ 15. The enumeration and classification results for 10 ≤ υ ≤ 14 are new and computationally nontrivial.