Informationsverteilung in realitätsnahen Netzwerken

• Applicants: Professor Dr. Robert Elsässer; Professor Dr. Christian Schindelhauer
• Subject Area: Theoretical Computer Science
• Term: from 2008 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 96929240

• Final Report Year: 2010

Final Report Abstract

Die Informationsausbreitung in selbstorganisierenden Netzwerken (wie z. B. Peer-to- Peer Netzwerke, soziale Netzwerke und drahtlose Sensor-Netzwerke) war Gegenstand der Untersuchung in diesem Projekt. Wir haben den Zusammenhang von Push-Algorithmen und Random-Walks in allgemeinen Netzwerken untersucht. Dabei stellte sich heraus, dass Graphen mit einer guten Mixing-Zeit bzw. Cover-Time in der Regel eine schnelle Informationsverteilung gewährleisten. Und genau diese Graphen mit guter Mixing-Zeit bzw. Cover-Time treten häufig in der Praxis als realitätsnahe Netzwerke auf. Ebenfalls haben wir modifizierte Push&Pull-Algorithmen zum Broadcasting in Power- Law Zufallsgraphen untersucht. Dabei konnten wir die Laufzeit und den Kommunikationsaufwand exakt berechnen. Daraufhin haben wir die Push&Pull-Algorithmen weiter angepasst, um in Graphen mit guter Expansionseigenschaft Informationsverteilung in optimaler Zeit und optimalem Kommunikationsaufwand garantieren zu können. Des Weiteren haben wir Push&Pull-Gossiping in vollständigen Graphen betrachtet und signifikante Unterschiede zwischen der Güte von Broadcasting und Gossiping festgestellt. Ausgehend vom BitTorrent-Protokoll, welches sehr populär und weit verbreitet ist, haben wir den Fall betrachtet, wo wenige Peers online sind und dadurch die Verbreitung von Informationen ins Stocken gerät. Dieses kann durch Netzwerkkodierung zwar gelöst werden, ist aber sehr ineffektiv weil die dabei anfallenden Lese- /Schreiboperationen auf Festplatten wesentlich langsamer sind als im Speicher. Hierfür haben wir zwei neue Ansätze vorgestellt: zum einen Pair-Coding und zum anderen Tree-Coding, welche genauso effizient oder der höchstens einen logarithmischen Faktor langsamer als BitTorrent sind, dafür aber in sehr vielen Situationen genauso effektiv wie Netzwerkkodierung arbeiten. Für eine genauere Untersuchung der Ausbreitung von Krankheiten haben wir die Mobilität der Individuen in Ballungszentren betrachtet. Dabei haben wir zwei Fälle analysiert: einerseits haben wir angenommen, dass keine Gegenmaßnahmen ergriffen werden um die Ausbreitung einzuschränken. In einem zweiten Szenario haben wir dann den Einfluss der Medien auf die Ausbreitung von Krankheiten untersucht.

Publications

• Classifying Peer-to-Peer Networking Coding Schemes. The 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2009), pages 310-318, 2009
  C. Ortolf, C. Schindelhauer, A. Vater
  
• Cover Time and Broadcast Time. Proc. of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pages 373-384, 2009
  R. Elsässer, T. Sauerwald
  
• Tight Bounds for the Cover Time of Multiple Random Walks. Proc. of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), pages 415-426, 2009
  R. Elsässer, T. Sauerwald
  
• Efficient Information Exchange in the Random Phone-Call Model. Proc. of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), pages 127-138, 2010
  P. Berenbrink, J. Czyzowicz, R. Elsässer, L. Gasieniec
  
• Tree Network Coding for Peer-to- Peer Networks. The 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010), pages 114-123, 2010
  C. Ortolf, C. Schindelhauer, A. Vater