Sonja Buchegger

Deutsche Telekom Laboratories
Berlin, Germany

TITLE

Fair Division and Collective Welfare in Self-Organized Networks

ABSTRACT

Networks that rely on little or no infrastructure, such as mobile ad-hoc, peer-to-peer, wireless mesh or vehicular networks, have to cooperate to communicate and share ressources and workloads in a distributed way. Ideally, this division of benefits and chores is fair - for a definition of fairness appropriate for a given scenario - for individual nodes while yielding a high performance for the overall network. To improve network design in terms of both individual and collective performance, we first need means for evaluation. To that end, we can take tools already available in other disciplines. For example, it turns out that in self-organized networks, the performance a node perceives often depends on its position within the network topology. Social network analysis provides graph-theoretical metrics that allow us to quantify the position of an individual node as well as the distribution in the whole network. Economics gives us metrics and methods for equity. Combining such metrics, we can understand better how choices of mechanisms and topologies impact the total performance as well as its distribution over the network nodes.

BIOGRAPHY

Sonja Buchegger is a senior research scientist at the Deutsche Telekom Laboratories, Berlin. In 2005 and 2006, she was a post-doctoral scholar at the School of Information, University of California at Berkeley. She received her Ph.D. in Communication Systems from EPFL, Switzerland, in 2004, a graduate degree in Computer Science in 1999, and undergraduate degrees in Computer Science in 1996 and in Business Administration in 1995 from the University of Klagenfurt, Austria. In 2003 and 2004 she was a research and teaching assistant at EPFL and from 1999 to 2003 she worked at the IBM Zurich Research Laboratory in the Network Technologies Group. Her current research interests are in economics and security of self-organized networks.

Devavrat Shah

Massachusetts Institute of Technology
Cambridge, MA, USA

TITLE

Network gossip algorithms

ABSTRACT

Algorithms are key operational building block of networks such as the Internet, a peer-to-peer network or a sensor network. A network demands a lot out of these algorithms: they need to utilize network resources efficiently while being simple-to-implement and distributed.

In this talk, we will describe gossip or randomized message-passing based frame-work for designing implementable high-performance network algorithms. In the first part of the talk, a distributed counting algorithm built upon property of exponential distribution is described. The running time of the algorithm is related spectral property of the underlying netowrk graph in a natural manner. In the second part of the talk, we describe the use of the counting algorithm as a sub-routine for a class of network problems including scheduling and resource allocation.

BIOGRAPHY

Devavrat Shah is currently an assistant professor with the department of EECS, MIT and a member of Laboratory for Information and Decision Systems (LIDS) as well as Operations Research Center (ORC). His research interests are in the network algorithms & stochastic networks, network information theory and message-passing algorithms.

He received his BTech degree in Computer Science & Engg. from IIT-Bombay in 1999 with the honor of the President of India Gold Medal. He received his Ph.D. from the Computer Science at Stanford University in 2004. He was a post-doc in the Statistics department at Stanford in 2004-05. He also spent time at MSRI, Berkeley while he was a post-doc.

He was co-awarded the IEE INFOCOM best paper award in 2004 and the ACM SIGMETRIC/Performance best paper award in 2006. He received the 2005 George B. Dantzig best disseration award from INFORMS. He received NSF CAREER award in 2006.