Not logged in.

Quick Search - Contribution

Contribution Details

Type Bachelor's Thesis
Scope Discipline-based scholarship
Title Scaling message passing algorithms for Distributed Constraint Optimization Problems in Signal/Collect
Organization Unit
Authors
  • Genc Mazlami
Supervisors
  • Coralia-Mihaela Verman
Language
  • English
Institution University of Zurich
Faculty Faculty of Economics, Business Administration and Information Technology
Number of Pages 117
Date 2013
Abstract Text The concept of Distributed Constraint Optimization Problems (DCOPs) is becoming more and more relevant to research in fields such as computer science, engineering, game theory and others. Many real world problems, such as congestion management in data communication or traffic, and applications on sensor networks, are potential application fields for DCOPs. Hence, there is a need for research on different algorithms and approaches to this class of problems. This thesis considers the evaluation and distribution of the Max-Sum algorithm. Specifically, the thesis first illustrates a detailed example computation of the algorithm in order to contribute in the understanding of the algorithm. The main contribution of the thesis is the implementation of the Max-Sum algorithm in the novel graph processing framework Signal/Collect. Also, a theoretical complexity analysis of said implementation is performed. Based on the implementation, a second contribution of the thesis follows: The benchmarking of the Max-Sum algorithm and its comparison to the DSA-A, DSA-B and Best-Response algorithms. The benchmarks first tries to reproduce the results found in [Farinelli et. al, 2008] by analyzing the conflicts over the execution cycles and the cycles until convergence. Then, the thesis contributes new empirical results by evaluating and comparing synchronous and asynchronous Max-Sum with respect to conflicts over time and time to convergence. Also, the analysis of the relation between the execution cycles and the execution time will be part of the novel contribution. Another main contribution of the thesis is the distributed evaluation of the algorithm on a multiple machine cluster. The benchmarks on multiple machines first compares the solution quality of asynchronous and synchronous Max-Sum on multiple machines. This is followed by an analysis how the number of machines used in the execution impacts the results for the conflicts over time. The thesis also adresses performance questions raised by the theoretical complexity analysis by analyzing the influence of the average vertex degree on the solution quality.
Zusammenfassung Das Konzept der Distributed Constraint Optimization Problems (DCOPs) gewinnt immer mehr an Relevanz in Forschungsgebieten wie der Informatik, Ingenieurwissenschaften, Spieltheorie oder anderen. Viele Probleme aus der realen Welt, wie z. B. Überlastkontrolle in Kommunikationstechnologien oder Verkehrssystemen, und Anwendungen in Sensornetzwerken, sind potenzielle Anwendungsgebiete für DCOPs. Daher besteht ein Bedarf and Forschung an verschiedenen Ansätzen und Algorithmen in dieser Problemklasse. Diese Arbeit beschäftigt sich mit der Evaluation und Verteilung des Max-Sum Algorithmus (auf mehreren Maschinen). Die Arbeit leistet einen Beitrag zum Verständnis des Max-Sum Algorithmus indem sie eine detaillierte Beispielberechnung darlegt. Der wissenschaftliche Hauptbeitrag dieser Arbeit ist jedoch der Entwurf und die Implementierung des Max-Sum Algorithmus in einer modernen Graph-Processing Umgebung namens Signal/Collect. Des Weiteren leitet die Arbeit eine theoretische Komplexitätsanalyse der besagten Implementierung her. Mit Hilfe der Implementation wird der zweite Hauptbeitrag dieser Arbeit realisiert: Die Evaluation des Max-Sum Algorithmus im Vergleich zu den DSA-A, DSA-B und Best-Response Algorithmen. Die Experimente versuchen zum Einen die Resultate aus [Farinelli et. al, 2008] zu reproduzieren indem die Konflikte pro Zyklus und die Anzahl Zyklen bis zur Konvergenz gemessen wird. Zum Anderen wird ein neuer Beitrag geleistet in Form von empirischen Resultaten bezüglich der Konflikte pro Zeiteinheit und bezüglich der Zeit bis zur Konvergenz. Verglichen werden dabei die synchrone und asynchrone Version des Max-Sum Algorithmus. Ausserdem wird die Beziehung zwischen einem Zyklus und der Ausführungszeit analysiert. Ein weiterer Hauptbeitrag dieser Arbeit ist die verteilte Ausführung und Evaluation des Max-Sum Algorithmus auf mehreren Maschinen. Die verteilte Evaluation vergleicht zuerst die Lösungsqualität vom synchronen und asynchronen Max-Sum Algorithmus auf mehreren Maschinen. Danach wird der Einfluss der Anzahl benutzter Maschinen auf die Lösungsqualität analysiert. Zu guter Letzt werden Fragen welche durch die theoretische Komplexitätsanalyse aufgeworfen werden durch empirische Versuche bearbeitet. Diese Versuche analysieren den Einfluss des mittleren Grades der Knoten im Graph auf die Lösungsqualität.
PDF File Download
Export BibTeX