2026-07-23T22:06:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14839 2024-03-06T10:54:58Z ddc:004 open_access

Truthful Information Dissemination in General Asynchronous Networks Solodkin, Lior Oshman, Rotem game theory asynchronous networks information dissemination We give a protocol for information dissemination in asynchronous networks of rational players, where each player may have its own desires and preferences as to the outcome of the protocol, and players may deviate from the protocol if doing so achieves their goals. We show that under minimalistic assumptions, it is possible to solve the information dissemination problem in a truthful manner, such that no participant has an incentive to deviate from the protocol we design. Our protocol works in any asynchronous network, provided the network graph is at least 2-connected. We complement the protocol with two impossibility results, showing that 2-connectivity is necessary, and also that our protocol achieves optimal bit complexity. As an application, we show that truthful information dissemination can be used to implement a certain class of communication equilibria, which are equilibria that are typically reached by interacting with a trusted third party. Recent work has shown that communication equilibria can be implemented in synchronous networks, or in asynchronous, complete networks; we show that in some useful cases, our protocol yields a lightweight mechanism for implementing communication equilibria in any 2-connected asynchronous network. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lior Solodkin and Rotem Oshman 2021 Is Part Of LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2021.37 urn:nbn:de:0030-drops-148398 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.37 eng https://creativecommons.org/licenses/by/4.0/legalcode