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:

Max Hahn-Klimroth, Dominik Kaaser and Malin Rau.
Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes.
CoRR abs/2303.00043, 2023.
URL BibTeX

@article{https://doi.org/10.48550/arxiv.2303.00043,
	%doi = "10.48550/ARXIV.2303.00043",
	url = "https://arxiv.org/abs/2303.00043",
	author = "Hahn-Klimroth, Max and Kaaser, Dominik and Rau, Malin",
	title = "Efficient Approximate Recovery from Pooled Data Using Doubly Regular Pooling Schemes",
	journal = "CoRR",
	year = 2023,
	volume = "abs/2303.00043"
}

Petra Berenbrink, Lukas Hintze, Hamed Hosseinpour, Dominik Kaaser and Malin Rau.
Dynamic Averaging Load Balancing on Arbitrary Graphs.
CoRR abs/2302.12201, 2023.
URL BibTeX

@article{https://doi.org/10.48550/arxiv.2302.12201,
	author = "Berenbrink, Petra and Hintze, Lukas and Hosseinpour, Hamed and Kaaser, Dominik and Rau, Malin",
	title = "Dynamic Averaging Load Balancing on Arbitrary Graphs",
	journal = "CoRR",
	volume = "abs/2302.12201",
	url = "https://arxiv.org/abs/2302.12201",
	year = 2023
}

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, Colin Cooper, Cristina Gava, David Kohan Marzagão, Frederik Mallmann-Trenn, Nicolás Rivera and Tomasz Radzik.
Distributed Averaging in Population Protocols.
CoRR abs/2211.17125, 2022.
URL BibTeX

@article{toappear/nlpa5,
	author = "Berenbrink, Petra and Cooper, Colin and Gava, Cristina and Marzagão, David Kohan and Mallmann-Trenn, Frederik and Rivera, Nicolás and Radzik, Tomasz",
	title = "Distributed Averaging in Population Protocols",
	journal = "CoRR",
	volume = "abs/2211.17125",
	url = "https://arxiv.org/abs/2211.17125",
	year = 2022
}

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"
}

Petra Berenbrink, Max Hahn-Klimroth, Dominik Kaaser, Lena Krieg and Malin Rau.
Inference of a Rumor's Source in the Independent Cascade Model.
CoRR abs/2205.12125, 2022.
URL, DOI BibTeX

@article{DBLP:journals/corr/abs-2205-12125,
	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",
	journal = "CoRR",
	volume = "abs/2205.12125",
	year = 2022,
	url = "https://doi.org/10.48550/arXiv.2205.12125",
	doi = "10.48550/arXiv.2205.12125",
	eprinttype = "arXiv",
	eprint = "2205.12125",
	timestamp = "Mon, 30 May 2022 15:47:29 +0200",
	biburl = "https://dblp.org/rec/journals/corr/abs-2205-12125.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