Privacy Preserving Implementation of the Max-Sum Algorithm and its Variants
Authors: Tamir Tassa, Tal Grinshpoun, Roie Zivan
JAIR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We conclude by analyzing the price of privacy in terns of runtime overhead, both theoretically and by extensive experimentation. ... We evaluate the performance of our privacy-preserving algorithms, both analytically and experimentally, in Section 6, and conclude in Section 7. ... Our experimental evaluation focuses on the computational overhead of P-Max-Sum (and P-Max-Sum AT). To realize the actual time it will take P-Max-Sum to run we followed the simulated time approach ... We ran experiments on the Agent Zero simulator that compare the runtime of P-Max-Sum to that of Max-Sum in varying constraint densities (p) and domain sizes (d). |
| Researcher Affiliation | Academia | Tamir Tassa EMAIL The Open University, Ra anana, Israel Tal Grinshpoun EMAIL Ariel University, Ariel, Israel Roie Zivan EMAIL Ben-Gurion University of the Negev, Beer Sheva, Israel |
| Pseudocode | Yes | Protocol 1 Computing shares in messages that emerge from a variable node ... Protocol 2 Computing shares in messages that emerge from a function node ... Protocol 3 Computing the best assignment for Xi ... Protocol 4 Computing shares in messages that emerge from a function node in Max Sum ADVP |
| Open Source Code | No | The paper does not provide an explicit statement about the release of source code for the methodology described. It mentions implementing the algorithm on a third-party simulator and using a common Java implementation of a cryptosystem, but no code release from the authors themselves. |
| Open Datasets | No | The paper describes generating different types of problems for experiments (unstructured random problems, scale-free problems, structured graph coloring problems, realistic meeting scheduling problems) and references models for their generation (e.g., Erd os and R enyi (1959), Barab asi and Albert (1999)). However, it does not provide concrete access information (links, DOIs, specific repositories, or formal citations to publicly available dataset instances) for the exact datasets used in the experiments. |
| Dataset Splits | No | The paper describes the generation parameters for the problem instances used in the experiments (e.g., 'n = 100 agents, constraint density of p = 0.1, and domain sizes of d = 5'). However, it does not specify training/test/validation dataset splits, as the problems addressed are distributed constraint optimization problems, which are typically solved rather than trained using such splits. |
| Hardware Specification | Yes | Our tests show that Cenc takes at most 2 milliseconds, while Cdec takes at most 3 milliseconds. ... on a hardware comprised of an Intel i7-4600U processor and 16GB memory. ... we ran the simulator on a dedicated Xeon 2.4GHz server with 24GB of memory and 24 cores |
| Software Dependencies | No | The paper mentions using 'the common Java implementation of the Paillier cryptosystem' and running experiments on the 'Agent Zero simulator (Lutati, Gontmakher, Lando, Netzer, Meisels, & Grubshtein, 2014)'. However, it does not provide specific version numbers for Java, the Paillier cryptosystem implementation, or the Agent Zero simulator. |
| Experiment Setup | Yes | Our basic setting consists of n = 100 agents, constraint density of p = 0.1, and domain sizes of d = 5. We also need to select a value for K, being the number of iterations. ... We run the algorithm for K = 50 iterations ... For this purpose we consider two types of underlying graphs random graphs and scale-free networks. ... by fixing m = 5 (which results in an average node degree of 10), and varying the number of agents n = 100, . . . , 1000. ... 3-color graph coloring problems, in which for all i, j, Ci,j(x, y) equals 1 if x = y and 0 if x = y. ... in this setting in as few as K = 5 iterations. ... The realistic problems that we consider are meeting scheduling problems, in which 20 meetings are to be scheduled into 20 time slots. Each participant takes part in two randomly chosen meetings. For each pair of meetings, a travel time was chosen uniformly at random between 6 and 10, inclusive. ... relatively fast convergence of such problems (K = 10). |