Parallelizing secure linear programming
Rafael J. Deitos, Florian Kerschbaum · Concurrency and Computation Practice and Experience · 2009
Abstract Information sharing in supply chain management can dramatically improve the performance of the supply chain. Although many such problems can be modeled and efficiently solved using linear programming (LP), security requirements prevent their implementation in the traditional way. Companies are simply reluctant to exchange such sensitive information. Secure multi‐party computation can help by realizing protocols with guaranteed security. However, efficiency is a major concern. Parallel computing presents an opportunity to improve performance utilizing inherent parallel secure operations. This work focuses on practical approaches to privacy preserving parallel protocols for collaborative LP. First, it theoretically compares the approach of parallelizing a secure algorithm and securing a parallel algorithm. Their complexity being equal we implemented the simpler choice: parallelizing a secure algorithm. Different synchronization methods for the implementation are compared under different network conditions. Given the best implementation, the performance is almost independent of the network conditions, but parallelization, i.e. number of threads, needs to be adapted to such conditions. We present and evaluate an adaptive scheduling algorithm for the dynamic selection of the number of threads, such that it's not necessary to statically and up‐front determine the number for optimal speed‐up. The algorithm can even deal with varying network conditions. Copyright © 2009 John Wiley & Sons, Ltd.