Privacy preserving region optimal algorithms for symmetric and asymmetric DCOPs

Tal Grinshpoun, Tamir Tassa, Vadim Levit, Roie Zivan

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


Region-optimal algorithms are local search algorithms for solving Distributed Constraint Optimization Problems (DCOPs). In each iteration of the search in such algorithms, every agent selects a group of agents that comply with some selection criteria (each algorithm specifies different criteria). Then, the agent who selected the group, called the mediator, collects assignment information from the group and neighboring agents outside the group, in order to find an optimal set of assignments for its group's agents. A contest between mediators of adjacent groups determines which groups will replace their assignments in that iteration to the found optimal ones. In this work we present a framework called RODA (Region Optimal DCOP Algorithm) that encompasses the algorithms in the region optimality family, and in particular any method for selecting groups. We devise a secure implementation of RODA, called P-RODA, which preserves constraint privacy and partial decision privacy. Our discussion covers both symmetric and asymmetric DCOPs. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. We estimate the computational overhead of P-RODA with respect to RODA and give an upper bound that depends on the group and domain sizes and on the graph topology, but not on the number of agents. The estimations are substantiated with experimental results, including experiments on a simulator, that compare the performance of P-RODA to that of its competing algorithm, P-Max-Sum.

שפה מקוריתאנגלית
עמודים (מ-עד)27-50
מספר עמודים24
כתב עתArtificial Intelligence
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ינו׳ 2019

הערה ביבליוגרפית

Publisher Copyright:
© 2018

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Privacy preserving region optimal algorithms for symmetric and asymmetric DCOPs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי