Search Results

Documents authored by Moscibroda, Thomas

Document
DOI: 10.4230/LIPIcs.ICALP.2016.64
Information Cascades on Arbitrary Topologies

Authors: Jun Wan, Yu Xia, Liang Li, and Thomas Moscibroda

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
In this paper, we study information cascades on graphs. In this setting, each node in the graph represents a person. One after another, each person has to take a decision based on a private signal as well as the decisions made by earlier neighboring nodes. Such information cascades commonly occur in practice and have been studied in complete graphs where everyone can overhear the decisions of every other player. It is known that information cascades can be fragile and based on very little information, and that they have a high likelihood of being wrong. Generalizing the problem to arbitrary graphs reveals interesting insights. In particular, we show that in a random graph G(n,q), for the right value of q, the number of nodes making a wrong decision is logarithmic in n. That is, in the limit for large n, the fraction of players that make a wrong decision tends to zero. This is intriguing because it contrasts to the two natural corner cases: empty graph (everyone decides independently based on his private signal) and complete graph (all decisions are heard by all nodes). In both of these cases a constant fraction of nodes make a wrong decision in expectation. Thus, our result shows that while both too little and too much information sharing causes nodes to take wrong decisions, for exactly the right amount of information sharing, asymptotically everyone can be right. We further show that this result in random graphs is asymptotically optimal for any topology, even if nodes follow a globally optimal algorithmic strategy. Based on the analysis of random graphs, we explore how topology impacts global performance and construct an optimal deterministic topology among layer graphs.
Cite as

Jun Wan, Yu Xia, Liang Li, and Thomas Moscibroda. Information Cascades on Arbitrary Topologies. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 64:1-64:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{wan_et_al:LIPIcs.ICALP.2016.64,
  author =	{Wan, Jun and Xia, Yu and Li, Liang and Moscibroda, Thomas},
  title =	{{Information Cascades on Arbitrary Topologies}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{64:1--64:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.64},
  URN =		{urn:nbn:de:0030-drops-63417},
  doi =		{10.4230/LIPIcs.ICALP.2016.64},
  annote =	{Keywords: Information Cascades, Herding Effect, Random Graphs}
}
Document
DOI: 10.4230/DagSemProc.06131.4
On the Topologies Formed by Selfish Peers

Authors: Stefan Schmid, Thomas Moscibroda, and Roger Wattenhofer

Published in: Dagstuhl Seminar Proceedings, Volume 6131, Peer-to-Peer-Systems and -Applications (2006)

Abstract
Many P2P systems are only proven efficient for static environments. However, in practice, P2P systems are often very dynamic in the sense that peers can join and leave a system at any time and concurrently. In the first part of my talk, I will present a DHT we have developed recently in our group which maintains desirable properties under worst-case churn. In the second part of my talk, we will briefly look at another challenge of prime importance in P2P computing, namely selfishness. Concretely, some results are presented concerning the impact of selfish behavior on the performance of P2P topologies.
Cite as

Stefan Schmid, Thomas Moscibroda, and Roger Wattenhofer. On the Topologies Formed by Selfish Peers. In Peer-to-Peer-Systems and -Applications. Dagstuhl Seminar Proceedings, Volume 6131, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schmid_et_al:DagSemProc.06131.4,
  author =	{Schmid, Stefan and Moscibroda, Thomas and Wattenhofer, Roger},
  title =	{{On the Topologies Formed by Selfish Peers}},
  booktitle =	{Peer-to-Peer-Systems and -Applications},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6131},
  editor =	{Anthony D. Joseph and Ralf Steinmetz and Klaus Wehrle},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06131.4},
  URN =		{urn:nbn:de:0030-drops-6431},
  doi =		{10.4230/DagSemProc.06131.4},
  annote =	{Keywords: Churn, Selfishness, P2P Topologies}
}
Document
DOI: 10.4230/DagSemProc.06131.5
Taming Dynamic and Selfish Peers

Authors: Stefan Schmid, Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer

Published in: Dagstuhl Seminar Proceedings, Volume 6131, Peer-to-Peer-Systems and -Applications (2006)

Abstract
Peer-to-peer systems are often faced with the problem of frequent membership changes. However, many systems are only proven efficient or correct in static environments. In my talk, I will present techniques to maintain desirable properties of a distributed hash table (low peer degree, low network diameter) in spite of ongoing and concurrent dynamics. I will then go on and study the effect of peers not acting according to our protocols. Concretely, I assume that peers are selfish and choose the behavior which maximizes their utility. I will report on our results concerning the impact of selfishness on the peer-to-peer topology.
Cite as

Stefan Schmid, Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Taming Dynamic and Selfish Peers. In Peer-to-Peer-Systems and -Applications. Dagstuhl Seminar Proceedings, Volume 6131, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{schmid_et_al:DagSemProc.06131.5,
  author =	{Schmid, Stefan and Kuhn, Fabian and Moscibroda, Thomas and Wattenhofer, Roger},
  title =	{{Taming Dynamic and Selfish Peers}},
  booktitle =	{Peer-to-Peer-Systems and -Applications},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6131},
  editor =	{Anthony D. Joseph and Ralf Steinmetz and Klaus Wehrle},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06131.5},
  URN =		{urn:nbn:de:0030-drops-6477},
  doi =		{10.4230/DagSemProc.06131.5},
  annote =	{Keywords: Churn, Selfishness, P2P Topologies}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact