[AG-TECH] LANL seminar series

[Cindy Sievers]

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 sievers at 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
sievers at lanl.gov        Group CCS-1 MS B287
tel:505.665.6602        Advanced Computing
fax:505.665.4939        Los Alamos, NM 87544
============================================