Abstract:
In the first part of the tutorial we learn the fundamentals of
distributed algorithms, also known as message passing algorithms, or the
"local" model. A distributed system is represented by a graph. We would
like to solve classic combinatorial optimization problems by having the
nodes of the graph just talk to their neighbors in the graph. As a
running example throughout the first part of the tutorial we will use
the so-called Maximal Independent Set (MIS) problem. Together, we figure
out and discuss simple deterministic and randomized algorithms to solve
the MIS problem in a distributed context. We will discuss applications
of the MIS problem, such as coloring. Then we look at some of the state
of the art results of the MIS problem and discuss the lower bound
technique by Linial, the upper bound technique by Cole and Vishkin, and
finally the lower bound by Kuhn et al. In the remainder of the first
part of the tutorial we will also look at related problems, and the most
important open questions in this area.
In the second part of the tutorial we will look at how to apply the
lessons learned from the first part in the context of wireless multihop
networks, i.e. ad hoc, sensor, or mesh networks. In particular we
discuss in what sense the physical reality is different from the pure
local model learned in the first part. Towards this end we will discuss
models for connectivity in wireless multihop networks, various
interference models, and finally communication models. Again, we will
discuss some of the most important open problems.
Speaker's Bio:
Roger Wattenhofer is a full professor at the
Information Technology and Electrical Engineering
Department, ETH Zurich, Switzerland. He received
his doctorate in Computer Science in 1998 from
ETH Zurich. From 1999 to 2001 he was in the USA,
first at Brown University in Providence, RI, then
at Microsoft Research in Redmond, WA. He then
returned to ETH Zurich, originally as an assistant
professor at the Computer Science Department.
Roger Wattenhofer's research interests are a
variety of algorithmic and systems aspects in
computer science and information technology,
currently in particular wireless networks,
multi-core systems, peer-to-peer computing, and
social networking. He publishes in different
communities: distributed computing (e.g., PODC,
SPAA, DISC), networking (e.g., MobiCom, MobiHoc,
SenSys, IPSN, HotNets), or theory (e.g., STOC,
FOCS, SODA, ICALP).
Abstract: Radio spectrum has traditionally been allocated in a static manner. However,
recent studies have shown that parts of the radio spectrum are over-utilized while some
parts are under-utilized. In order to break away from the inflexibilities and
inefficiencies of long-term static allocations, the concept of dynamic spectrum access
and management using cognitive radios is being investigated and is expected to be a
significant component in next generation wireless systems. It is currently of big
interest to radio engineers, policy makers and economists involved in the design,
analysis, and optimization of next generation wireless access systems and networks.
In this tutorial, we will first motivate the concept and use of dynamic spectrum access.
We will then see how this new paradigm can be made viable through the use of cognitive
radios. Our main focus will be Spectrum Management i.e., dynamic spectrum allocation and
sharing among primary and secondary users. We will discuss issues related to MAC and
distributed/centralized channel access. After a brief introduction to game theory, we will
should how game theory can be used as an effective tool to model the competition and
cooperation among various cognitive networks. We will also show how different auction models
can be used to find the equilibrium price for spectrum trading. We will conclude with IEEE
802.22 which is a cognitive radio based wireless regional area network technology.
Speaker's Bio:
Mainak Chatterjee is an Associate Professor in the department of Electrical Engineering and Computer Science, University of Central Florida, Orlando. He received the BSc degree in physics (Hons.) from the University of Calcutta, the ME degree in electrical communication engineering from the Indian Institute of Science, Bangalore, and the PhD degree from the Department of Computer Science and Engineering from the University of Texas at Arlington. His research interests include economic issues in wireless networks, applied game theory, cognitive radio networks, and mobile video delivery. He has published over 100 conferences and journal papers. He got the Best Paper Award in IEEE Globecom 2008. He is the recipient of the AFOSR sponsored Young Investigator Program (YIP) Award. He co-founded the IEEE Workshop on Mobile Video Delivery (MoViD). He serves on the editorial board of Elsevier's Computer Communications and Pervasive and Mobile Computing Journals. He has served as the TPC Co-Chair of several conferences including IEEE WoWMoM 2011, WONS 2010, IEEE MoViD 2009, Cognitive Radio Networks Track of IEEE Globecom 2009 and ICCCN 2008. He also serves on the executive and technical program committee of several international conferences.
Abstract: Directional and omnidirectional are the two types of antennae
being used in sensor networking. The former emit greater power
in one direction thus achieving increased transmission range
and performance as well as reduced interference from unwanted
sources. On the contrary, omnidirectional antennae radiate
power uniformly in all directions. Regardless of
the type of antenna being used the transmission cost of each
antenna is proportional to the coverage area of the antenna.
By providing a comparative analysis of directional vs omnidirectional
antennae the purpose of the tutorial is to understand how the use of
directional antennae can improve energy consumption, security, and
topology control. In the first part of the tutorial we introduce
basic concepts and ideas for 2D and 3D antennae and look at
how directional antennae reduce energy consumption and improve
security of a sensor network. In the second part, we look specifically
at topology control issues, in particular connectivity, neighbor
discovery, coverage, routing, and stretch factor, In both parts
of the tutorial we discuss and analyze several recent algorithms
and study trade-offs on the beam width, range and number of antennae
being used per sensor. We also provide directions for future research
and give several challenging recent open problems.
Speaker's Bio:
Evangelos Kranakis received his B.Sc. in Mathematics from the University of Athens, Greece, and a Ph.D. in Mathematics from the University of Minnesota, USA. He has been in the Mathematics Department of Purdue University, USA, Mathematisches Institut of the University of Heidelberg, Germany, the Computer Science Department of Yale University, USA, at the Computer Science Department of the Universiteit van Amsterdam, and at the Centrum voor Wiskunde en Informatica (CWI) in Amsterdam, The Netherlands. He joined the faculty of the School of Computer Science of Carleton University in the Fall of 1991. He has published in the analysis of algorithms, bioinformatics, communication and data (ad hoc and wireless) networks, computational and combinatorial geometry, distributed computing, and network security. He was director of the School of Computer Science from 1994 to 2000 and has been in the Research Management Committee of MITACS (Mathematics of Information Technology and Complex Systems) since 1998.
Abstract: The rapid growth of the Internet, particularly fuelled by social media and Web 2.0 applications - has necessitated new, scalable mechanisms for data management and storage. These techniques have subsequently organically become the key enabling technologies for the cloud infrastructure. In particular, distributed file systems, primarily based on distributed key-value stores have emerged as a key ingredient facilitating the core data management needs in many such systems - such as Amazon's Dynamo, Facebook's Cassandra, Yahoo's PNUTS!, Google's BigTable, etc. to name a few prominent ones, while abstractions such as map-reduce (and Hadoop framework) and NoSQL systems have emerged for manipulation and querying such stored information. The first half of the tutorial will introduce these state-of-the art data-management mechanisms, and the associated open challenges.
Redundancy is essential for fault-tolerance, however the overheads of storing the huge volume of data involved - in terms of storage space, as well as bandwidth and computational needs, to create and then maintain the redundancy over time, in presence of faults that can occur randomly and continuously, can be huge. Traditional erasure coding techniques, which were originally developed for communication centric applications, help reduce the storage overhead, but do not perform well in terms of repair traffic or necessary computational overheads. New coding techniques tailor made for storage centric applications - some based on network coding concepts (regenerating codes), as well as others (such as Pyramid and self-repairing codes) are emerging - and are posed to play a vital role in providing scalable solutions for storing huge volume of data. The second part of the tutorial will provide a summary of these emerging mechanisms.
Speakers' Bio:
Anwitaman Datta did his PhD at EPFL Lausanne before moving to NTU Singapore in 2006, where he is currently an Assistant Professor in the School of Computer Engineering. He is interested in large scale networked distributed information systems and social collaboration networks, self-organization and algorithmic issues of these systems and networks and their scalability, resilience, security and performance. He won the best paper awards at IWSOS 2006, ICDCS 2007 and ICDCN 2011, and is one of the recipients of HP Labs Innovation Research Program award 2008.
Frederique Oggier received her degree Diplome in Mathematics and Computer Science in 2000 from
the University of Geneva, Switzerland. She then joined the Swiss Federal Institute of Technology,
Lausanne (EPFL), where she graduated from the Doctoral School in Communication Systems (2001),
and completed her Ph.D. thesis in Mathematics (2005). She was a postdoctoral visitor at the
California Institute of Technology (CalTech) from 2005 till 2007, and at the Research Center for
Information Security (RCIS) in Tokyo, Japan, from 2007 to 2008. She is currently an Assistant
Professor at the School of Physical and Mathematical Sciences, Nanyang Technological University
(NTU), Singapore. She is a recipient of the Singapore NRF Fellowship. Her main research interests are
in applied algebra to coding problems arising in wireless communications, distributed networked
storage as well as information theoretic security.
