Distributed and Collaborative Systems of Agents

Distributed and Collaborative Systems of Agents

Description:

To understand and algorithmically exploit the properties of dynamics, we consider models from distributed computing where agents are embedded in a network, and the system evolves via iterative message passing. We study the task of agents arriving at and agreeing on a joint decision, captured formally by majority, leader election and consensus problems. The goal of the subproject is the design and analysis of fast protocols for these problems, focusing in particular on simple k-majority dynamics in the message passing model and natural extensions. Beyond this task, we will generalize the analysis techniques to other models for, e.g., game-theoretic opinion formation or more general epidemic dynamics.

Staff:

Prof. Dr. Petra Berenbrink (Main PI)
Dr. Malin Rau

Publications:

Abdou Majeed Alidou, Júlia Baligács, Max Hahn-Klimroth, Jan Hazla, Lukas Hintze and Olga Scheftelowitsch.
Inevitability of Polarization in Geometric Opinion Exchange.
CoRR abs/2402.08446, 2024.
URL, DOI BibTeX

@article{DBLP:journals/corr/abs-2402-08446,
	author = "Abdou Majeed Alidou and J{\'{u}}lia Balig{\'{a}}cs and Max Hahn{-}Klimroth and Jan Hazla and Lukas Hintze and Olga Scheftelowitsch",
	title = "Inevitability of Polarization in Geometric Opinion Exchange",
	journal = "CoRR",
	volume = "abs/2402.08446",
	year = 2024,
	url = "https://doi.org/10.48550/arXiv.2402.08446",
	doi = "10.48550/ARXIV.2402.08446",
	timestamp = "Mon, 19 Feb 2024 15:25:43 +0100",
	biburl = "https://dblp.org/rec/journals/corr/abs-2402-08446.bib"
}

Amin Coja-Oghlan, Max Hahn-Klimroth, Lukas Hintze, Dominik Kaaser, Lena Krieg, Maurice Rolvien and Olga Scheftelowitsch.
Noisy group testing via spatial coupling.
CoRR abs/2402.02895, 2024.
URL, DOI BibTeX

@article{DBLP:journals/corr/abs-2402-02895,
	author = "Amin Coja{-}Oghlan and Max Hahn{-}Klimroth and Lukas Hintze and Dominik Kaaser and Lena Krieg and Maurice Rolvien and Olga Scheftelowitsch",
	title = "Noisy group testing via spatial coupling",
	journal = "CoRR",
	volume = "abs/2402.02895",
	year = 2024,
	url = "https://doi.org/10.48550/arXiv.2402.02895",
	doi = "10.48550/ARXIV.2402.02895",
	timestamp = "Mon, 12 Feb 2024 13:36:38 +0100",
	biburl = "https://dblp.org/rec/journals/corr/abs-2402-02895.bib"
}

Petra Berenbrink, Martin Hoefer, Dominik Kaaser, Pascal Lenzner, Malin Rau and Daniel Schmand.
Asynchronous opinion dynamics in social networks.
Distributed Computing 37:207-224, 2024.
URL, DOI BibTeX

@article{berenbrink2024asynchronous,
	title = "Asynchronous opinion dynamics in social networks",
	author = "Berenbrink, Petra and Hoefer, Martin and Kaaser, Dominik and Lenzner, Pascal and Rau, Malin and Schmand, Daniel",
	journal = "Distributed Computing",
	pages = "207-224",
	year = 2024,
	publisher = "Springer",
	volume = 37,
	url = "https://link.springer.com/article/10.1007/s00446-024-00467-3",
	doi = "dx.doi.org/10.1007/s00446-024-00467-3"
}

Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser and Philipp Loick.
Information-theoretic and algorithmic aspects of parallel and distributed reconstruction from pooled data.
J. Parallel Distributed Comput. 180:104718, 2023.
URL, DOI BibTeX

@article{DBLP:journals/jpdc/GebhardHKL23,
	author = "Oliver Gebhard and Max Hahn{-}Klimroth and Dominik Kaaser and Philipp Loick",
	title = "Information-theoretic and algorithmic aspects of parallel and distributed reconstruction from pooled data",
	journal = "J. Parallel Distributed Comput.",
	volume = 180,
	pages = 104718,
	year = 2023,
	url = "https://doi.org/10.1016/j.jpdc.2023.104718",
	doi = "10.1016/J.JPDC.2023.104718",
	timestamp = "Fri, 18 Aug 2023 08:46:39 +0200",
	biburl = "https://dblp.org/rec/journals/jpdc/GebhardHKL23.bib"
}

Max Hahn-Klimroth and Dominik Kaaser.
On Reconstructing the Patient Zero from Sensor Measurements.
In 43rd IEEE International Conference on Distributed Computing Systems, ICDCS 2023, Hong Kong, July 18-21, 2023. 2023, 1–11.
URL, DOI BibTeX

@inproceedings{DBLP:conf/icdcs/HahnKlimrothK23,
	author = "Max Hahn{-}Klimroth and Dominik Kaaser",
	title = "On Reconstructing the Patient Zero from Sensor Measurements",
	booktitle = "43rd {IEEE} International Conference on Distributed Computing Systems, {ICDCS} 2023, Hong Kong, July 18-21, 2023",
	pages = "1--11",
	year = 2023,
	url = "https://doi.org/10.1109/ICDCS57875.2023.00065",
	doi = "10.1109/ICDCS57875.2023.00065",
	timestamp = "Tue, 07 May 2024 20:07:22 +0200",
	biburl = "https://dblp.org/rec/conf/icdcs/HahnKlimrothK23.bib"
}

Petra Berenbrink, Lukas Hintze, Hamed Hosseinpour, Dominik Kaaser and Malin Rau.
Dynamic Averaging Load Balancing on Arbitrary Graphs.
In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany 261. 2023, 18:1–18:18.
URL, DOI BibTeX

@inproceedings{DBLP:conf/icalp/BerenbrinkHHKR23,
	author = "Petra Berenbrink and Lukas Hintze and Hamed Hosseinpour and Dominik Kaaser and Malin Rau",
	title = "Dynamic Averaging Load Balancing on Arbitrary Graphs",
	booktitle = "50th International Colloquium on Automata, Languages, and Programming, {ICALP} 2023, July 10-14, 2023, Paderborn, Germany",
	series = "LIPIcs",
	volume = 261,
	pages = "18:1--18:18",
	year = 2023,
	url = "https://doi.org/10.4230/LIPIcs.ICALP.2023.18",
	doi = "10.4230/LIPICS.ICALP.2023.18",
	timestamp = "Wed, 05 Jul 2023 16:52:15 +0200",
	biburl = "https://dblp.org/rec/conf/icalp/BerenbrinkHHKR23.bib"
}

Petra Berenbrink, Colin Cooper, Cristina Gava, David Kohan Marzagão, Frederik Mallmann-Trenn, Tomasz Radzik and Nicolas Rivera.
Distributed Averaging in Opinion Dynamics.
In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023. 2023, 211–221.
URL, DOI BibTeX

@inproceedings{DBLP:conf/podc/BerenbrinkCGMMR23,
	author = "Petra Berenbrink and Colin Cooper and Cristina Gava and David Kohan Marzag{\~{a}}o and Frederik Mallmann{-}Trenn and Tomasz Radzik and Nicolas Rivera",
	title = "Distributed Averaging in Opinion Dynamics",
	booktitle = "Proceedings of the 2023 {ACM} Symposium on Principles of Distributed Computing, {PODC} 2023, Orlando, FL, USA, June 19-23, 2023",
	pages = "211--221",
	year = 2023,
	url = "https://doi.org/10.1145/3583668.3594593",
	doi = "10.1145/3583668.3594593",
	timestamp = "Fri, 07 Jul 2023 23:30:23 +0200",
	biburl = "https://dblp.org/rec/conf/podc/BerenbrinkCGMMR23.bib"
}

Petra Berenbrink, Max Hahn-Klimroth, Dominik Kaaser, Lena Krieg and Malin Rau.
Inference of a rumor's source in the independent cascade model.
In Uncertainty in Artificial Intelligence, UAI 2023, July 31 - 4 August 2023, Pittsburgh, PA, USA 216. 2023, 152–162.
URL BibTeX

@inproceedings{DBLP:conf/uai/BerenbrinkHKKR23,
	author = "Petra Berenbrink and Max Hahn{-}Klimroth and Dominik Kaaser and Lena Krieg and Malin Rau",
	title = "Inference of a rumor's source in the independent cascade model",
	booktitle = "Uncertainty in Artificial Intelligence, {UAI} 2023, July 31 - 4 August 2023, Pittsburgh, PA, {USA}",
	series = "Proceedings of Machine Learning Research",
	volume = 216,
	pages = "152--162",
	year = 2023,
	url = "https://proceedings.mlr.press/v216/berenbrink23a.html",
	timestamp = "Tue, 07 May 2024 20:09:01 +0200",
	biburl = "https://dblp.org/rec/conf/uai/BerenbrinkHKKR23.bib"
}

Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser and Malin Rau.
On the Hierarchy of Distributed Majority Protocols.
In 26th International Conference on Principles of Distributed Systems (OPODIS 2022) 253. 2023, 23:1–23:19.
URL, DOI BibTeX

@inproceedings{berenbrink_et_al:LIPIcs.OPODIS.2022.23,
	author = "Berenbrink, Petra and Coja-Oghlan, Amin and Gebhard, Oliver and Hahn-Klimroth, Max and Kaaser, Dominik and Rau, Malin",
	title = "{On the Hierarchy of Distributed Majority Protocols}",
	booktitle = "26th International Conference on Principles of Distributed Systems (OPODIS 2022)",
	pages = "23:1--23:19",
	series = "Leibniz International Proceedings in Informatics (LIPIcs)",
	isbn = "978-3-95977-265-5",
	issn = "1868-8969",
	year = 2023,
	volume = 253,
	publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
	address = "Dagstuhl, Germany",
	url = "https://drops.dagstuhl.de/opus/volltexte/2023/17643",
	urn = "urn:nbn:de:0030-drops-176434",
	doi = "10.4230/LIPIcs.OPODIS.2022.23",
	annote = "Keywords: Consensus, Majority, Hierarchy, Stochastic Dominance, Population Protocols, Gossip Model, Strassen’s Theorem"
}

Petra Berenbrink, Felix Biermeier, Christopher Hahn and Dominik Kaaser.
Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem.
In 1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022, March 28-30, 2022, Virtual Conference 221. 2022, 7:1–7:17.
URL, DOI BibTeX

@inproceedings{DBLP:conf/sand/BerenbrinkBHK22,
	author = "Petra Berenbrink and Felix Biermeier and Christopher Hahn and Dominik Kaaser",
	title = "Loosely-Stabilizing Phase Clocks and The Adaptive Majority Problem",
	booktitle = "1st Symposium on Algorithmic Foundations of Dynamic Networks, {SAND} 2022, March 28-30, 2022, Virtual Conference",
	series = "LIPIcs",
	volume = 221,
	pages = "7:1--7:17",
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = 2022,
	url = "https://doi.org/10.4230/LIPIcs.SAND.2022.7",
	doi = "10.4230/LIPIcs.SAND.2022.7",
	timestamp = "Fri, 29 Apr 2022 14:20:08 +0200",
	biburl = "https://dblp.org/rec/conf/sand/BerenbrinkBHK22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser and Peter Kling.
Fast Consensus via the Unconstrained Undecided State Dynamics.
In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022. 2022, 3417–3429.
URL, DOI BibTeX

@inproceedings{DBLP:conf/soda/BankhamerBBEHKK22,
	author = {Gregor Bankhamer and Petra Berenbrink and Felix Biermeier and Robert Els{\"{a}}sser and Hamed Hosseinpour and Dominik Kaaser and Peter Kling},
	title = "Fast Consensus via the Unconstrained Undecided State Dynamics",
	booktitle = "Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022",
	pages = "3417--3429",
	publisher = "{SIAM}",
	year = 2022,
	url = "https://doi.org/10.1137/1.9781611977073.135",
	doi = "10.1137/1.9781611977073.135",
	timestamp = "Tue, 12 Apr 2022 11:24:57 +0200",
	biburl = "https://dblp.org/rec/conf/soda/BankhamerBBEHKK22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Petra Berenbrink, Martin Hoefer, Dominik Kaaser, Pascal Lenzner, Malin Rau and Daniel Schmand.
Asynchronous Opinion Dynamics in Social Networks.
In 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2022, Auckland, New Zealand, May 9-13, 2022. 2022, 109–117.
URL, DOI BibTeX

@inproceedings{DBLP:conf/atal/Berenbrink0KLRS22,
	author = "Petra Berenbrink and Martin Hoefer and Dominik Kaaser and Pascal Lenzner and Malin Rau and Daniel Schmand",
	title = "Asynchronous Opinion Dynamics in Social Networks",
	booktitle = "21st International Conference on Autonomous Agents and Multiagent Systems, {AAMAS} 2022, Auckland, New Zealand, May 9-13, 2022",
	pages = "109--117",
	publisher = "International Foundation for Autonomous Agents and Multiagent Systems {(IFAAMAS)}",
	year = 2022,
	url = "https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p109.pdf}, %doi = {10.5555/3535850.3535864",
	doi = "10.48550/ARXIV.2201.12923",
	timestamp = "Mon, 18 Jul 2022 17:13:00 +0200",
	biburl = "https://dblp.org/rec/conf/atal/Berenbrink0KLRS22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser and Philipp Loick.
On the Parallel Reconstruction from Pooled Data.
In 2022 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2022, Lyon, France, May 30 - June 3, 2022. 2022, 425–435.
URL, DOI BibTeX

@inproceedings{DBLP:conf/ipps/GebhardHKL22,
	author = "Oliver Gebhard and Max Hahn{-}Klimroth and Dominik Kaaser and Philipp Loick",
	title = "On the Parallel Reconstruction from Pooled Data",
	booktitle = "2022 {IEEE} International Parallel and Distributed Processing Symposium, {IPDPS} 2022, Lyon, France, May 30 - June 3, 2022",
	pages = "425--435",
	publisher = "{IEEE}",
	year = 2022,
	url = "https://doi.org/10.1109/IPDPS53621.2022.00048",
	doi = "10.1109/IPDPS53621.2022.00048",
	timestamp = "Fri, 22 Jul 2022 11:43:23 +0200",
	biburl = "https://dblp.org/rec/conf/ipps/GebhardHKL22.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Max Hahn-Klimroth and Dominik Kaaser.
Distributed Reconstruction of Noisy Pooled Data.
In 2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS) (). 2022, 89-99.
URL, DOI BibTeX

@inproceedings{9912157,
	author = "Hahn-Klimroth, Max and Kaaser, Dominik",
	booktitle = "2022 IEEE 42nd International Conference on Distributed Computing Systems (ICDCS)",
	title = "Distributed Reconstruction of Noisy Pooled Data",
	year = 2022,
	volume = "",
	number = "",
	url = "https://ieeexplore.ieee.org/abstract/document/9912157",
	pages = "89-99",
	doi = "10.1109/ICDCS54860.2022.00018"
}

Petra Berenbrink, David Hammer, Dominik Kaaser, Ulrich Meyer, Manuel Penschuck and Hung Tran.
Simulating Population Protocols in Sub-Constant Time per Interaction.
In 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference) 173. 2020, 16:1–16:22.
URL, DOI BibTeX

@inproceedings{DBLP:conf/esa/BerenbrinkHK0PT20,
	author = "Petra Berenbrink and David Hammer and Dominik Kaaser and Ulrich Meyer and Manuel Penschuck and Hung Tran",
	title = "Simulating Population Protocols in Sub-Constant Time per Interaction",
	booktitle = "28th Annual European Symposium on Algorithms, {ESA} 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference)",
	series = "LIPIcs",
	volume = 173,
	pages = "16:1--16:22",
	publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
	year = 2020,
	url = "https://doi.org/10.4230/LIPIcs.ESA.2020.16",
	doi = "10.4230/LIPIcs.ESA.2020.16",
	timestamp = "Thu, 16 Sep 2021 18:07:51 +0200",
	biburl = "https://dblp.org/rec/conf/esa/BerenbrinkHK0PT20.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Petra Berenbrink, George Giakkoupis and Peter Kling.
Optimal time and space leader election in population protocols.
In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. 2020, 119–129.
URL, DOI BibTeX

@inproceedings{DBLP:conf/stoc/BerenbrinkGK20,
	author = "Petra Berenbrink and George Giakkoupis and Peter Kling",
	title = "Optimal time and space leader election in population protocols",
	booktitle = "Proccedings of the 52nd Annual {ACM} {SIGACT} Symposium on Theory of Computing, {STOC} 2020, Chicago, IL, USA, June 22-26, 2020",
	pages = "119--129",
	publisher = "{ACM}",
	year = 2020,
	url = "https://doi.org/10.1145/3357713.3384312",
	doi = "10.1145/3357713.3384312",
	timestamp = "Sat, 08 Jan 2022 02:24:27 +0100",
	biburl = "https://dblp.org/rec/conf/stoc/BerenbrinkGK20.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Gregor Bankhamer, Robert Elsässer, Dominik Kaaser and Matjaz Krnc.
Positive Aging Admits Fast Asynchronous Plurality Consensus.
In PODC '20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020. 2020, 385–394.
URL, DOI BibTeX

@inproceedings{DBLP:conf/podc/BankhamerEKK20,
	author = {Gregor Bankhamer and Robert Els{\"{a}}sser and Dominik Kaaser and Matjaz Krnc},
	title = "Positive Aging Admits Fast Asynchronous Plurality Consensus",
	booktitle = "{PODC} '20: {ACM} Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020",
	pages = "385--394",
	publisher = "{ACM}",
	year = 2020,
	url = "https://doi.org/10.1145/3382734.3406506",
	doi = "10.1145/3382734.3406506",
	timestamp = "Tue, 04 Aug 2020 16:14:27 +0200",
	biburl = "https://dblp.org/rec/conf/podc/BankhamerEKK20.bib",
	bibsource = "dblp computer science bibliography, https://dblp.org"
}

Algorithms, Dynamics, and Information Flow in NetworksDFG Research Unit

Description:

Staff:

Publications:

Algorithms, Dynamics, and Information Flow in Networks
DFG Research Unit