Optimizing Streaming Applications with Self-Interested Users using M-DPOP

Abstract

In this paper we deal with the problem of optimally placing a set of query operators in an overlay network. Each user is interested in performing a query on streaming data and each query has an associated set of in-network operators that filter, aggregate and process the data in various ways. Each user has private information about the operators associated with a query and about the utility from different combinations of operator placements. Each server in the overlay network is able to perform some set of operators, and servers differ in their network and computational characteristics. We model this problem as a Distributed Constraint Optimization Problem (DCOP). On this DCOP model, we apply the MDPOP algorithm from Petcu et al. that is executed by clients associated with users and situated at nodes on the overlay network. MDPOP makes truth-telling an \textit{ex-post Nash equilibrium}, and determines the social-welfare maximizing placement of operators to servers. No client can benefit by deviating from the MDPOP algorithm. Nodes need only communicate with other nodes that have an interest in placing an operator on the same server. Structure can be exploited, where it exists, to provide a scalable algorithm. The only central authority required is a bank that can extract payments from users. In addition, it is possible to develop a faithful method to redistribute some of the VCG payments back to users when desired.