Premium
Parallelizing secure linear programming
Author(s) -
Deitos Rafael,
Kerschbaum Florian
Publication year - 2009
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.1424
Subject(s) - computer science , distributed computing , scheduling (production processes) , computation , synchronization (alternating current) , secure two party computation , critical path method , secure multi party computation , parallel computing , computer network , mathematical optimization , algorithm , channel (broadcasting) , mathematics , systems engineering , engineering
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.