Login
- Originaltitel:
- Computational Limits of Population Protocols: Space Complexity, Robustness and Expressive Power
- Übersetzter Titel:
- Rechnerische Grenzen von Populationsprotokollen: Platzkomplexität, Robustheit und Ausdrucksmächtigkeit
- Autor:
- Czerner, Philipp
- Jahr:
- 2025
- Dokumenttyp:
- Dissertation
- Fakultät/School:
- TUM School of Computation, Information and Technology
- Institution:
- Informatik 7 - Lehrstuhl für Theoretische Informatik (Prof. Esparza)
- Betreuer:
- Esparza Estaun, Francisco Javier (Prof. Dr.)
- Gutachter:
- Esparza Estaun, Francisco Javier (Prof. Dr.); Seidl, Helmut (Prof. Dr.); Ouaknine, Joël (Prof. Dr.)
- Sprache:
- en
- Fachgebiet:
- DAT Datenverarbeitung, Informatik
- Stichworte:
- distributed computing; population protocols; space complexity
- Übersetzte Stichworte:
- verteiltes Rechnen; Populationprotokolle; Platzkomplexität
- TU-Systematik:
- DAT 500
- Kurzfassung:
- Population protocols are a model of distributed computation where a large number of anonymous agents interact in pairs. We analyse their space complexity, giving matching upper and lower bounds for flock-of-birds predicates, and a succinct and optimally fast construction for arbitrary predicates. We also consider expressive power in two fault models, where agents and be added and removed during the computation, respectively. Finally, we analyse variants of the population protocol model.
- Übersetzte Kurzfassung:
- Populationsprotokolle sind ein Modell für verteilte Berechnung, in dem eine Vielzahl anonymer Agenten interagiert. Wir analysieren ihre Platzkomplexität und liefern übereinstimmende Schranken für Vogelscharprädikate sowie eine kleine, optimal schnelle Konstruktion für beliebige Prädikate. Wir betrachten auch die Ausdrucksstärke in zwei Fehlermodellen, bei denen Agenten zur Laufzeit jeweils hinzugefügt und entfernt werden können. Abschließend analysieren wir Varianten von Populationsprotokollen.
- WWW:
- https://mediatum.ub.tum.de/?id=1769438
- Eingereicht am:
- 19.02.2025
- Mündliche Prüfung:
- 22.07.2025
- Dateigröße:
- 9003020 bytes
- Seiten:
- 240
- Urn (Zitierfähige URL):
- https://nbn-resolving.org/urn:nbn:de:bvb:91-diss-20250722-1769438-0-4
- Letzte Änderung:
- 11.08.2025
BibTeX
Vorkommen:
- mediaTUM GesamtbestandElektronische PrüfungsarbeitenSchoolTUM School of Computation, Information and TechnologyComputer Science
- mediaTUM GesamtbestandElektronische PrüfungsarbeitenSchoolTUM School of Computation, Information and Technology