Abstract: In today's networked world, resource providers and consumers are distributed globally and locally, especially under current cloud computing environment. However, with resource constraints, optimization is necessary to ensure the best possible usage of such scarce resources. Distributed linear programming (DisLP) problems allow collaborative agents to jointly maximize profits or minimize costs with a linear objective function while conforming to several shared as well as local linear constraints. Since each agent's share of the global constraints and the local constraints generally refer to its private limitations or capacities, serious privacy problems may arise if such information is revealed. While there have been some solutions raised that allow secure computation of such problems, they typically rely on inefficient protocols with enormous computation and communication cost. In this paper, we study the DisLP problems where constraints are arbitrarily partitioned and every agent privately holds a set of variables, and propose secure and extremely efficient approach based on mathematical transformation in two adversary models – semi-honest and malicious model. Specifically, we first present a secure column generation (SCG) protocol that securely solves the above DisLP problem amongst two or more agents without any private information disclosure, assuming semi-honest behavior (all agents properly follow the protocol but may be curious to derive private information from other agents). Furthermore, we discuss potential selfish actions and colluding issues in malicious model (distributed agents may corrupt the protocol to gain extra benefit) and propose an incentive compatible protocol to resolve such malicious behavior. To address the effectiveness of our protocols, we present security analysis for both adversary models as well as the communication/computation cost analysis. Finally, our experimental results validate the efficiency of our approach and demonstrate its scalability.
Keywords: Distributed linear programming, security, efficiency, transformation
