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 -