Séminaire REGAL
Roy Friedman - Practical Random Walks in Ad-Hoc Networks
Friday, November 23, 2007Roy Friedman
Ad-hoc networks are formed by a collection of computing devices (laptops, PDAs, mobile phones, sensors) with wireless communication capabilities. In such a setting, each device can communicate directly with other devices in its transmission range. Moreover, if some devices occasionally volunteer to forward messages on behalf of other devices, a multiple-hop network is formed. Yet, all networking decisions are done ad-hoc, in a fully decentralized manner, and without having to rely on any pre-existing infrastructure. Clearly, in such networks, relying on global information as well as applying multiple hop routing are major scalability bottlenecks. Random walks seem like a promising approach for ad-hoc networks, since they rely on single-hop steps based only on local information. However, applying random walks to implement useful services in ad-hoc networks and utilizing them in a way that can be formally analyzed is a challenging task. In this talk I will discuss our experience in applying random walks for implementing a few basic services in ad-hoc networks, the lessons we have learned, as well as a qualitative and quantitative comparison with other approaches.
Bio: Roy Friedman is an associate professor in the department of Computer Science at the Technion. He has published more than 70 technical papers on distributed systems, group communication, fault-tolerance, high availability, cluster computing, client/server middleware, and wireless mobile ad-hoc networks in major international journals and conferences. He also holds two patents. Prof. Friedman serves as the program co-chair for SRDS 2008, was program vice-chair of ICDCS 2007 and the program chair for the MiNEMA summer school 2005, and was a PC member of various international conferences such as DSN, ICDCS, SRDS, PODC, DISC, EDCC, LADC, SSS, HotDep, and MDM. Formerly, Roy Friedman has been an academic specialist at IRISA/INRIA (France) and a researcher at Cornell University (USA). He is one of the Founders of PolyServe Inc. (acquired by HP) and holds a Ph.D. (1994) and a B.Sc. (1990) in Computer Science from the Technion.