TY - CONF AU - Jacob, Riko AU - Ritscher, Stephan AU - Scheideler, Christian AU - Schmid, Stefan ID - 1930 T2 - Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings TI - A Self-stabilizing and Local Delaunay Graph Construction VL - 5878 ER - TY - CONF AU - Jacob, Riko AU - W. Richa, Andrea AU - Scheideler, Christian AU - Schmid, Stefan AU - Täubig, Hanjo ID - 1932 SN - 978-1-60558-396-9 T2 - Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, PODC 2009, Calgary, Alberta, Canada, August 10-12, 2009 TI - A distributed polylogarithmic time algorithm for self-stabilizing skip graphs ER - TY - CONF AU - Baumgart, Matthias AU - Scheideler, Christian AU - Schmid, Stefan ID - 1933 SN - 978-1-60558-606-9 T2 - SPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, Calgary, Alberta, Canada, August 11-13, 2009 TI - A DoS-resilient information system for dynamic data management ER - TY - CONF AU - Gall, Dominik AU - Jacob, Riko AU - W. Richa, Andrea AU - Scheideler, Christian AU - Schmid, Stefan AU - Täubig, Hanjo ID - 1934 SN - 978-3-642-05117-3 T2 - Stabilization, Safety, and Security of Distributed Systems, 11th International Symposium, SSS 2009, Lyon, France, November 3-6, 2009. Proceedings TI - Brief Announcement: On the Time Complexity of Distributed Topological Self-stabilization VL - 5873 ER - TY - CONF AU - Doerr, Benjamin AU - Ann Goldberg, Leslie AU - Minder, Lorenz AU - Sauerwald, Thomas AU - Scheideler, Christian ID - 1935 T2 - Algorithmic Methods for Distributed Cooperative Systems, 06.09. - 11.09.2009 TI - Stabilizing Consensus with the Power of Two Choices VL - 09371 ER - TY - JOUR AU - Meyer auf der Heide, Friedhelm AU - Scheideler, Christian ID - 1903 IS - 5 JF - Informatik Spektrum TI - Algorithmische Grundlagen verteilter Speichersysteme ER - TY - JOUR AU - Gavoille, Cyril AU - Patt-Shamir, Boaz AU - Scheideler, Christian ID - 1904 IS - 4 JF - Theory of Computing Systems TI - Foreword ER - TY - CONF AU - Gall, Dominik AU - Jacob, Riko AU - W. Richa, Andrea AU - Scheideler, Christian AU - Schmid, Stefan AU - Täubig, Hanjo ID - 1905 SN - 978-3-642-12199-9 T2 - LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010. Proceedings TI - Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization VL - 6034 ER - TY - CONF AU - Richa, Andrea W. AU - Zhang, Jin AU - Scheideler, Christian AU - Schmid, Stefan ID - 1906 SN - 978-1-60558-888-9 T2 - Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC 2010, Zurich, Switzerland, July 25-28, 2010 TI - Brief announcement: towards robust medium access in multi-hop networks ER - TY - CONF AU - Richa, Andrea W. AU - Scheideler, Christian AU - Schmid, Stefan AU - Zhang, Jin ID - 1907 SN - 978-3-642-15762-2 T2 - Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings TI - A Jamming-Resistant MAC Protocol for Multi-Hop Wireless Networks VL - 6343 ER - TY - CONF AU - Doerr, Benjamin AU - Ann Goldberg, Leslie AU - Minder, Lorenz AU - Sauerwald, Thomas AU - Scheideler, Christian ID - 1908 T2 - Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings TI - Brief Announcement: Stabilizing Consensus with the Power of Two Choices VL - 6343 ER - TY - CONF AU - W. Richa, Andrea AU - Scheideler, Christian AU - Schmid, Stefan AU - Zhang, Jin ID - 1891 SN - 978-0-7695-4364-2 T2 - 2011 International Conference on Distributed Computing Systems, ICDCS 2011, Minneapolis, Minnesota, USA, June 20-24, 2011 TI - Competitive and Fair Medium Access Despite Reactive Jamming ER - TY - CONF AU - W. Richa, Andrea AU - Scheideler, Christian AU - Schmid, Stefan AU - Zhang, Jin ID - 1892 SN - 978-1-4503-0868-7 T2 - Proceedings of the 3rd ACM workshop on Wireless of the students, by the students, for the students, S3@MOBICOM 2011, Las Vegas, NV, USA, September 19 - 23, 2011 TI - Towards jamming-resistant and competitive medium access in the SINR model ER - TY - CONF AU - W. Richa, Andrea AU - Scheideler, Christian AU - Schmid, Stefan AU - Zhang, Jin ID - 1893 SN - 978-1-4503-0722-2 T2 - Proceedings of the 12th ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2011, Paris, France, May 16-20, 2011 TI - Self-stabilizing leader election for single-hop wireless networks despite jamming ER - TY - CONF AU - Kniesburges, Sebastian AU - Koutsopoulos, Andreas AU - Scheideler, Christian ID - 1895 SN - 978-1-4503-0743-7 T2 - SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4-6, 2011 (Co-located with FCRC 2011) TI - Re-Chord: a self-stabilizing chord overlay network ER - TY - CONF AU - Kniesburges, Sebastian AU - Scheideler, Christian ID - 1899 SN - 978-3-642-19093-3 T2 - WALCOM: Algorithms and Computation - 5th International Workshop, WALCOM 2011, New Delhi, India, February 18-20, 2011. Proceedings TI - Hashed Patricia Trie: Efficient Longest Prefix Matching in Peer-to-Peer Systems VL - 6552 ER - TY - CHAP AU - Scheideler, Christian AU - Graffi, Kalman ID - 1900 SN - 978-1-4614-1167-3 T2 - Computer Science, The Hardware, Software and Heart of It TI - Programming for Distributed Computing: From Physical to Logical Networks ER - TY - CHAP AU - Scheideler, Christian ID - 1901 SN - 978-3-642-15327-3 T2 - Algorithms Unplugged TI - Broadcasting - How Can I Quickly Disseminate Information? ER - TY - CONF AU - Kolman, Petr AU - Scheideler, Christian ID - 1924 T2 - 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany TI - Towards Duality of Multicommodity Multiroute Cuts and Flows: Multilevel Ball-Growing ER - TY - CONF AB - In the standard consensus problem there are n processes with possibly di®erent input values and the goal is to eventually reach a point at which all processes commit to exactly one of these values. We are studying a slight variant of the consensus problem called the stabilizing consensus problem [2]. In this problem, we do not require that each process commits to a ¯nal value at some point, but that eventually they arrive at a common, stable value without necessarily being aware of that. This should work irrespective of the states in which the processes are starting. Our main result is a simple randomized algorithm called median rule that, with high probability, just needs O(logmlog log n + log n) time and work per process to arrive at an almost stable consensus for any set of m legal values as long as an adversary can corrupt the states of at most p n processes at any time. Without adversarial involvement, just O(log n) time and work is needed for a stable consensus, with high probability. As a by-product, we obtain a simple distributed algorithm for approximating the median of n numbers in time O(logmlog log n + log n) under adversarial presence. AU - Doerr, Benjamin AU - Goldberg, Leslie Ann AU - Minder, Lorenz AU - Sauerwald, Thomas AU - Scheideler, Christian ID - 645 T2 - Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) TI - Stabilizing consensus with the power of two choices ER -