|
|
Stratis Ioannidis
I am currently a researcher at Technicolor (formerly known as Thomson), in Palo Alto, CA. My personal website can be found here.
I was born in Athens, Greece. I received a B.Sc. (2002) in Electrical and Computer Engineering from the National Technical University of Athens, Greece,and a M.Sc. (2004) and a Ph.D. (2009) in Computer Science from the University of Toronto, Canada. While in Toronto, I was a member of the Computer Systems & Networks Group, and my advisor was Peter Marbach. After my graduation, I worked for two years as a postdoctoral researcher in the Technicolor lab in Paris, France.
|
Awards
Research Interests
List of Publications
Talks
Research Interests
Peer-to-Peer Systems
Peer-Assisted Services
Content Delivery Over Mobile Social Networks
Surfing the Blogosphere
Summary
Peer-to-peer systems are computer networks allowing their participants-the peers-to
share their resources (e.g., bandwidth and storage capacity) in a distributed fashion. Such systems emerged in
the late '90s and have since become tremendously popular. Their users typically number in the millions and, by
some estimates, the traffic they generate constitutes more than 40% of the total data traffic transfered
over the Internet.
The focus of my Ph.D. dissertation
was on search mechanisms over unstructured peer-to-peer systems.
Ideally, a search mechanism should be scalable: the query traffic
imposed on peers through searching should not grow fast as the peer population increases. Moreover, it should
also be reliable: a search should be able to locate content that is present in the system with reasonable guarantees.
The first contribution of my dissertation was to prove that two previously proposed search mechanisms for
unstructured peer-to-peer systems (namely, the random walk and the expanding ring) are not scalable and reliable.
The second is to propose a novel search mechanism that indeed exhibits both of these two properties. These
results have considerable practical implications: they demonstrate how to build scalable and reliable peer-to-peer
systems entirely based on the unstructured paradigm.
Related Publications
A1. Absence of Evidence as Evidence of Absence: A Simple Mechanism for Scalable P2P Search.
Stratis Ioannidis and Peter
Marbach. In INFOCOM 2009, Rio de Janeiro, Brazil.
A2. Scalable and Reliable Searching in Unstructured Peer-to-Peer Systems.
Ph.D. Thesis, University of Toronto, Dept. of Computer Science, 2009.
A3. Absence of Evidence as Evidence of
Absence: A Simple Mechanism for Scalable P2P Search.
Stratis Ioannidis, Peter
Marbach. Technical Report, Computer Networks Research Lab, University
of Toronto, CNRL-08-001.
Summary
Peer-assisted services were introduced recently to reduce the traffic at a central server by
delegating a fraction of it to its own clients. In such systems, clients assist a service provider in the distribution
of content by uploading to other clients content they have already retrieved. The cost reductions achieved by such
peer-assistance are considerable: studies have shown that replacing monolithic data centers and serving traffic from
set-top boxes installed in residential locations can result in massive (60-80%) savings for the service provider in
terms of energy costs.
The mathematical model introduced in my dissertation can also be used to address
scalability questions in the context of peer-assisted services. The trade-off between scalability and reliability translates, in the peer-assisted case, to a trade-off between client and server traffic loads. In [B1], we propose search mechanisms under which both loads
remain bounded as the peer population grows. This is surprising, and has an important implication: one can
construct peer-assisted systems that can handle traffic generated by a large (unbounded) peer population, even
when both the server and client bandwidth capacities are limited.
A fundamental issue in such peer-assisted designs is incentivization. In [B3], we propose that clients that do
not share downloaded content pay a regular service fee to the service provider, whereas clients that share content
pay a reduced fee. The challenge in the above pricing scheme lies in evaluating the appropriate fee reduction. The
reduced fee should be low enough so that clients indeed have an incentive to share content. On the other hand,
if the fee is too low, the content provider's revenue losses will not be offset by the cost reduction achieved at its
server through peer-assistance, and the service will become unpro table for the provider. Our proposed method
computes a pricing scheme based on Shapley values that establishes a proper balance between the interests of
the service provider and client inventivization. In particular, it is individually rational and stable: it guarantees
that the service provider's revenues increase monotonically with the number of sharing clients, but also that every
non-sharing client will eventually opt to share its content and thus pay the reduced fee.
Related Publications
B1. On the Design of Hybrid Peer-to-Peer Systems.
Stratis Ioannidis and Peter
Marbach. In SIGMETRICS 2008, Annapolis, MD.
B2.
Incentivizing Peer-Assisted Services: A Fluid Shapley Value Approach.
Vishal Misra, Stratis Ioannidis, Augustin Chaintreau, and Laurent Massoulié. To appear in SIGMETRICS 2010, New York, NY.
B3. Scalable and Reliable Searching in Unstructured Peer-to-Peer Systems.
Ph.D. Thesis, University of Toronto, Dept. of Computer Science, 2009.
Summary
The main premise behind mobile delay-tolerant networks is the notion of opportunistic communication. Mobile users are equipped with, e.g., Bluetooth or WiFi enabled devices, which they an use to exchange data whenever they meet. Opportunities for such data exchanges depend crucially on a mobile user's social behavior: intuitively, a social user that interacts with many other people on a given day will have many opportunities to exchange data. This observation is very important for system designers that wish to build and deploy applications over such opportunistic mobile networks. In particular, it implies that their design should take into account the social behavior of users and how impacts the performance of their application.
In our work, we investigate the impact of the social behavior of mobile users on the dissemination of dynamic content among mobile devices. In this application, mobile users subscribe to a dynamic-content distribution service offered by their wireless provider. For example, users may subscribe to a news-feed, a blog, or a service that monitors stock prices, traffic congestion, etc. Subscribers to this service regularly receive updates from their provider and share these updates in an opportunistic fashion: whenever two of them meet, the one whose content is most recent pushes it (e.g., via Bluetooth) to the one whose content is outdated.
Our work characterizes a variety of different aspects of this application. In [C1], we propose a distributed algorithm for computing the optimal caching policy at each mobile device. In [C2], we focus on the rate with which the service provider should push updates to a given user, and again propose a distributed algorithm for computing the optimal rate allocation. The solutions to both problems highly depend on the social behavior of users.
In [C2], we further show that the above system is highly scalable when the social network formed by the mobile users is an expander. Under this condition, even if the bandwidth dedicated by the service provider remains fixed, the content age at each user grows slowly (as log(n)) with the user population size n.
We further illustrate [C4] that the above effect of the social network's expansion on the dissemination of content is
related to a phenomenon known in sociology as the "strength of weak ties".
Related Publications
C1.
Distributed Caching over Heterogeneous Mobile Networks.
Stratis Ioannidis, Laurent
Massoulié, and Augustin Chaintreau. To appear in SIGMETRICS 2010, New York, NY.
C2. Optimal and Scalable Distribution of Content Updates over a Mobile Social Network.
Stratis Ioannidis, Augustin Chaintreau and
Laurent Massoulié. In INFOCOM 2009, Rio de Janeiro, Brazil.
C3. On the
Distribution of Content Updates over a Mobile Social Network.
Stratis Ioannidis, Augustin Chaintreau and Laurent Massoulié. Poster, in Mobicom
2008, San Fransisco, CA.
(1st place in the Mobicom 2008 ACM
Student Research Competition)
(2nd place in the ACM
Student Research Competition Grand Finals)
[Grand Finals submission]
C4. On the Strength of Weak Ties in Mobile Social Networks.
Stratis Ioannidis, Augustin Chaintreau. In SNS 2009, Nuremberg, Germany.
C5. Optimal and Scalable Distribution of Content Updates over a Mobile Social Network.
Stratis Ioannidis, Augustin
Chaintreau and Laurent Massoulié. Technical Report, Thomson Research,
CR-PRL-2008-08-001.
Summary
The sheer volume, diversity and varying quality of content onthe web makes searching for current information a challenging task. As a
s a result, online recommendation engines (such as, e.g.,
Delicious, Digg, and Reddit)
giving daily suggestions to websurfers have recently proliferated.
The fundamental question the above recommendation engines are trying to answer is the following: on a given day, which websites should a websurfer visit in order to find content that she is interested in?
We propose a simple mechanism for determining which websites a surfer should visit, inspired by the recommendation engine StumbleUpon.
Our mechanism presents a sequence of websites to the surfer, and all a surfer needs to declare is whether she approves the websites shown to her.
The websurfer need not know---nor explicitly declare---what her interests are before actually being presented with a website she likes. Our mechanism is oblivious to the nature of the content shown to the websurfer by the websites she visits and does not require any centralized data collection or processing.
In spite of its simplicity, our mechanism computes an optimal surfing strategy, i.e., a strategy for visiting websites
that matches the websurfer's interests to the content presented by websites in an optimal way. More specifically, the surfing strategy produced by our mechanism minimizes the number of websites the websurfer views before finding interesting content.
We further show that the performance of our mechanism can be improved if feedback is aggregated among surfer communities. In particular, if surfers with similar interests share their feedback,
the accuracy of the mechanism and the rate of its convergence can be significantly improved.
Related Publications
D1. Surfing the Blogosphere: Optimal Personalized Strategies for Searching the Web.
Stratis Ioannidis, Laurent
Massoulié. To appear in INFOCOM 2010, San Diego, CA.
D2. Surfing the Blogosphere: Optimal Personalized Stategies For Searching the Web.
Stratis Ioannidis, Laurent Massoulié. Technical Report, Thomson, CR-PRL-2009-07-0001.