LANL Advanced computing Lab seminar series http://public.ds.lanl.gov/ccs1-seminar
TITLE: Secure Algorithms and Data Structures for Massive Networks SPEAKER: Jared Saia, University of New Mexico http://www.cs.unm.edu/~saia WHEN: Monday, June 12, 1:00-2:00pm (Mountain Standard Time) WHERE: Platinum Venue (off of the NCSA venue server) https://agschedule.ncsa.uiuc.edu/meetingdetails.asp?MID=15646 ABSTRACT: In this talk, we will present two new results on designing algorithms and data structures which are distributed, scalable and robust to adversarial attack. The first part of the talk will describe a robust distributed hash table(DHT), based on the popular DHT, Chord. This new DHT, is robust with high probability for any time period during which: 1) there are always at least z total peers in the network for some integer z; 2) there are never more than (1/4-epsilon)z bad peers in the network for a fixed \epsilon>0; and 3) the number of peer insertion and deletion events is no more than z^k for some tunable parameter k. We assume there is a computationally-unbounded adversary controlling the bad peers and that the IP-addresses of all the bad peers and the locations where they join the network are carefully selected by this adversary. In comparison to Chord, the resources required by our new DHT are only a polylogarithmic factor greater in communication, messaging, and linking costs. The second part of the talk will describe a new scalable algorithm for the leader election problem. In the leader election problem, there are n processors of which (1- b) n are good for some b>0. Our goal is to design a distributed protocol which elects a good leader from the set of all processors. I will describe a new, leader election protocol that is scalable in the sense that each good processor sends and processes a number of bits which is only polylogarithmic in n. For b < 1/3, our protocol elects a good leader with constant probability and ensures that a 1-o(1) fraction of the good processors know this leader. To the best of our knowledge, this is the first leader election algorithm which ensures that each good processor sends and processes a sublinear number of bits. This result can be used to provide scalable algorithms for Byzantine agreement, global coin toss, and other problems. These results are joint with Amos Fiat (U. Tel Aviv), Valerie King (U. Victoria), Vishal Sanwalani (U. Waterloo), Erik Vee (IBM Labs), and Maxwell Young (U. New Mexico) and are previously published in Principles of Distributed Computing (PODC), Symposium of Discrete Algorithms (SODA), and the European Symposium on Algorithms (ESA). All remote sites welcome, please RSVP to siev...@lanl.gov if your site is planning on attending. Remote sites are asked to arrive in the venue at least 30 minutes early for testing. ============================================ Cindy Sievers Los Alamos National Laboratory siev...@lanl.gov Group CCS-1 MS B287 tel:505.665.6602 Advanced Computing fax:505.665.4939 Los Alamos, NM 87544 ============================================
