Title: How well do we know the physical model?
Date: Thursday, May 30, 2019
Speaker: Prof. Magnus M. Halldorsson
Abstract:
-
Fading channels have long been understood as more accurate models of wireless
reception than graph-based models. The downside are the significant challenges that
they pose for analytic studies. For one, interference is now a complex relation,
with contributions from faraway nodes. Also, just whether two nodes can communicate
at all depends very much on other ongoing transmissions. This is particularly
challenging for distributed algorithms that have no prior notion of other nodes, or
ability to determine locations or distances.
But the physical model also comes with opportunities, even when ignoring possible
physical layer coding tricks. The capture effect yields certain indirect
information, involving relative signal strengths. We describe recent work that
leverages this feature systematically to deduce enough information to simulate
carrier sense in silico. This can then be used to construct a sparse backbone
spanner, which leads to near optimal algorithms for the most fundamental
information dissemination problems: (multi-message) broadcast, node coloring, local
broadcast, maximal independent sets.
The conclusion is that the physical model is considerably more amenable to efficient
algorithms than previously thought. Where are the true limits of what can be done
with the model?
|
Short Bio:
-
Magnus M. Halldorsson is a professor in the School of Computer Science of
Reykjavik University, where he is the Director of Icelandic Center of
Excellence in Theoretical Computer Science (ICE-TCS). He received his Ph.D.
in 1991 from Rutgers University and worked at Tokyo Institute of Technology,
Japan Advanced Institute of Science and Technology, University of Iceland,
and Iceland Genomics. For the last decade, he has focused on foundational
algorithms research for wireless networking. Prof. Halldorsson has authored
over 70 journal papers and 100 refereed papers in competitive conferences.
He received the first research award of Reykjavik University in 2010, and
has received awards from the Icelandic Research Council and best-paper
awards at conferences and from journals.
|
Title: The What and What Not of Intermittent Computing
Date: Wednesday, May 29, 2019
Speaker: Prof. Luca Mottola
Abstract:
-
Energy harvesting and wireless energy transfer are laying the foundations
for a battery-less Internet of Things (IoT). These forms of energy
provisioning are generally erratic across space and time. Executions
become intermittent, as they consist of intervals of active computation
interleaved by periods of recharging energy buffers and no computation.
This trait challenges established practices at designing, implementing,
and testing IoT systems, requiring a conceptual as well as practical leap
in both hardware and software. Fundamental computing concepts such as
consistency of data and progression of time, need to be revisited. In this
talk, I will elicit the key features of intermittent computing systems,
discuss the current state of the art in the field, and outline open
problems and long-term challenges still to be tackled.
|
Short Bio:
-
Luca Mottola is an Associate Professor at Politecnico di Milano (Italy) and
a Senior Researcher at RI.Se SICS Sweden. He completed my Ph.D. at
Politecnico di Milano (Italy) in 2008. His research interests focus on
modern networked embedded systems. Out of this research, he obtained the
Google Faculty Award, was listed twice amongst Postscapes "Internet of
Things Top 100 Thinkers”, and received the ACM SigMobile Research Highlight,
the ERCIM Cor Baayen Award, the Best Paper Award at ACM MOBISYS 2016, the
Best Paper Award at ACM/IEEE IPSN 2011 and 2009, the EWSN/CONET European
Best Ph.D. Thesis Award, and the MIT TR Italia Young Innovator Award. He
was General Chair for ACM/IEEE IPSN 2018, and PC co-chair for IEEE DCOSS
2015, ACM EWSN 2017, ACM SENSYS 2017, and ACM/IEEE IPSN19. He is an
Associate Editor for ACM Transactions on Sensor Networks.
|
|
