Recent News

Computer science student chosen for Churchill Scholarship
January 11, 2023

Leaving a legacy: Computer science professor’s research honored with Test of Time Award
December 9, 2022

Virtual workshop on climate-driven extreme events planned Nov. 10
October 25, 2022

MathWorks gives $2 million to UNM to create endowed chair for Department of Computer Science
October 18, 2022

News Archives

• 2023
  • January 2023
• 2022
  • January 2022
  • March 2022
  • April 2022
  • May 2022
  • June 2022
  • August 2022
  • September 2022
  • October 2022
  • December 2022
• 2021
  • January 2021
  • March 2021
  • October 2021
• 2020
  • February 2020
  • March 2020
  • May 2020
  • October 2020
  • November 2020
• 2019
  • January 2019
  • February 2019
  • March 2019
  • April 2019
  • May 2019
  • June 2019
  • July 2019
  • August 2019
  • September 2019
  • October 2019
  • November 2019
• 2018
  • January 2018
  • March 2018
  • April 2018
  • July 2018
  • August 2018
  • September 2018
  • October 2018
  • November 2018
• 2017
  • February 2017
  • April 2017
  • October 2017
  • November 2017
  • December 2017
• 2016
  • March 2016
  • April 2016
  • July 2016
• 2015
  • January 2015
  • February 2015
  • March 2015
  • April 2015
  • May 2015
  • June 2015
  • August 2015
• 2014
  • January 2014
  • February 2014
  • March 2014
  • April 2014
  • May 2014
  • July 2014
  • August 2014
  • September 2014
  • October 2014
  • November 2014
  • December 2014
• 2013
  • January 2013
  • February 2013
  • March 2013
  • April 2013
  • May 2013
  • August 2013
  • September 2013
  • October 2013
  • November 2013
  • December 2013
• 2012
  • January 2012
  • February 2012
  • March 2012
  • April 2012
  • May 2012
  • August 2012
  • September 2012
  • October 2012
  • November 2012
  • December 2012
• 2011
  • January 2011
  • February 2011
  • March 2011
  • April 2011
  • May 2011
  • August 2011
  • September 2011
  • October 2011
  • November 2011
  • December 2011
• 2010
  • January 2010
  • February 2010
  • March 2010
  • April 2010
  • May 2010
  • June 2010
  • August 2010
  • September 2010
  • October 2010
  • November 2010
  • December 2010
• 2009
  • January 2009
  • February 2009
  • March 2009
  • April 2009
  • May 2009
  • June 2009
  • August 2009
  • September 2009
  • October 2009
  • November 2009
  • December 2009
• 2008
  • January 2008
  • February 2008
  • March 2008
  • April 2008
  • May 2008
  • July 2008
  • August 2008
  • September 2008
  • October 2008
  • November 2008
  • December 2008
• 2007
  • January 2007
  • February 2007
  • March 2007
  • April 2007
  • May 2007
  • July 2007
  • August 2007
  • September 2007
  • October 2007
  • November 2007
  • December 2007
• 2006
  • January 2006
  • February 2006
  • March 2006
  • April 2006
  • May 2006
  • September 2006
  • October 2006
  • November 2006
  • December 2006
• 2005
  • January 2005
  • February 2005
  • March 2005
  • April 2005
  • May 2005
  • June 2005
  • August 2005
  • September 2005
  • October 2005
  • November 2005
  • December 2005
• 2004
  • January 2004
  • February 2004
  • March 2004
  • April 2004
  • May 2004
  • July 2004
  • August 2004
  • September 2004
  • October 2004
  • November 2004
  • December 2004
• 2003
  • November 2003
  • December 2003

September 9, 2004

Date: Thursday September 9, 2004
Time: 11am-12:15pm
Location: Woodward 149

Jared Saia <saia@cs.unm.edu>
Department of Computer Science University of New Mexico

Abstract: We present the first fully distributed algorithm which chooses a peer uniformly at random from the set of all peers in a distributed hash table (DHT). Our algorithm has latency $O(\log n)$ and sends $O(\logn)$ messages in expectation for a DHT like Chord. Our motivation for studying this problem is threefold: to enable data collection by statistically rigorous sampling methods; to provide support for randomized, distributed algorithms over peer-to-peer networks; and to support the creation and maintenance of random links, and thereby offer a simple means of improving fault-tolerance. This is joint work with Valerie King which appeared in PODC 2004.