Roy Friedman - Practical Random Walks in Ad-Hoc Networks
Speaker(s) : Roy FriedmanAd-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.
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.