Fog computing is transforming the network edge into an intelligent platform by bringing storage, computing, control, and networking functions closer to end-users, things, and sensors. How to allocate multiple resource types (e.g., CPU, memory, bandwidth) of capacity-limited heterogeneous fog nodes to competing services with diverse requirements and preferences in a fair and efficient manner is a challenging task. To this end, we propose a novel market-based resource allocation framework in which the services act as buyers and fog resources act as divisible goods in the market. The proposed framework aims to compute a market equilibrium (ME) solution at which every service obtains its favorite resource bundle under the budget constraint while the system achieves high resource utilization. This work extends the General Equilibrium literature by considering a practical case of satiated utility functions. Also, we introduce the notions of non-wastefulness and frugality for equilibrium selection, and rigorously demonstrate that all the non-wasteful and frugal ME are the optimal solutions to a convex program. Furthermore, the proposed equilibrium is shown to possess salient fairness properties including envy-freeness, sharing-incentive, and proportionality. Another major contribution of this work is to develop a privacy-preserving distributed algorithm, which is of independent interest, for computing an ME while allowing market participants to obfuscate their private information. Finally, extensive performance evaluation is conducted to verify our theoretical analyses.
Finally, although numerous distributed optimization techniques @cite_50 @cite_15 @cite_22 @cite_39 @cite_16 are available in the literature, most of them require agents to exchange and reveal their estimates explicitly to neighboring agents in every iteration to reach consensus on the final optimal solution. We are among the , which converges to the optimal solution without asking the agents to reveal any private data. Unlike differential privacy based methods @cite_28 that add carefully-designed noises to cover sensitive information and are subject to a trade-off between privacy and accuracy, our proposed scheme enables privacy preservation without sacrificing accuracy.
@cite_22 @cite_28 @cite_39 @cite_50 @cite_15 @cite_16
2953279152 2114791779 2570972465 1920382817
In distributed optimization and iterative consensus literature, a standard problem is for @math agents to minimize a function @math over a subset of Euclidean space, where the cost function is expressed as a sum @math . In this paper, we study the private distributed optimization (PDOP) problem with the additional requirement that the cost function of the individual agents should remain differentially private. The adversary attempts to infer information about the private cost functions from the messages that the agents exchange. Achieving differential privacy requires that any change of an individual's cost function only results in unsubstantial changes in the statistics of the messages. We propose a class of iterative algorithms for solving PDOP, which achieves differential privacy and convergence to the optimal value. Our analysis reveals the dependence of the achieved accuracy and the privacy levels on the the parameters of the algorithm. We observe that to achieve @math -differential privacy the accuracy of the algorithm has the order of @math . We present distributed algorithms that can be used by multiple agents to align their estimates with a particular value over a network with time-varying connectivity. Our framework is general in that this value can represent a consensus value among multiple agents or an optimal solution of an optimization problem, where the global objective function is a combination of local agent objective functions. Our main focus is on constrained problems where the estimates of each agent are restricted to lie in different convex sets. To highlight the effects of constraints, we first consider a constrained consensus problem and present a distributed "projected consensus algorithm" in which agents combine their local averaging operation with projection on their individual constraint sets. This algorithm can be viewed as a version of an alternating projection method with weights that are varying over time and across agents. We establish convergence and convergence rate results for the projected consensus algorithm. We next study a constrained optimization problem for optimizing the sum of local objective functions of the agents subject to the intersection of their local constraint sets. We present a distributed "projected subgradient algorithm" which involves each agent performing a local averaging operation, taking a subgradient step to minimize its own objective function, and projecting on its constraint set. We show that, with an appropriately selected stepsize rule, the agent estimates generated by this algorithm converge to the same optimal solution for the cases when the weights are constant and equal, and when the weights are time-varying but all agents have the same constraint set. We consider a problem where multiple agents participate in solving a quadratic optimization problem subject to linear inequality constraints in a privacy-preserving manner. Several variables of the objective function as well as the constraints are privacy-sensitive and are known to different agents. We propose a privacy-preserving protocol based on partially homomorphic encryption where each agent encrypts its own information before sending it to an untrusted cloud computing infrastructure. To find the optimal solution the cloud applies a gradient descent algorithm on the encrypted data without the ability to decrypt it. The privacy of the proposed protocol against coalitions of colluding agents is analyzed using the cryptography notion of zero knowledge proofs. Many resource allocation problems can be formulated as an optimization problem whose constraints contain sensitive information about participating users. This paper concerns a class of resource allocation problems whose objective function depends on the aggregate allocation (i.e., the sum of individual allocations); in particular, we investigate distributed algorithmic solutions that preserve the privacy of participating users. Without privacy considerations, existing distributed algorithms normally consist of a central entity computing and broadcasting certain public coordination signals to participating users. However, the coordination signals often depend on user information, so that an adversary who has access to the coordination signals can potentially decode information on individual users and put user privacy at risk. We present a distributed optimization algorithm that preserves differential privacy, which is a strong notion that guarantees user privacy regardless of any auxiliary information an adversary may have. The algorithm achieves privacy by perturbing the public signals with additive noise, whose magnitude is determined by the sensitivity of the projection operation onto user-specified constraints. By viewing the differentially private algorithm as an implementation of stochastic gradient descent, we are able to derive a bound for the suboptimality of the algorithm. We illustrate the implementation of our algorithm via a case study of electric vehicle charging. Specifically, we derive the sensitivity and present numerical simulations for the algorithm. Through numerical simulations, we are able to investigate various aspects of the algorithm when being used in practice, including the choice of step size, number of iterations, and the trade-off between privacy level and suboptimality.