Self-managing information systems
Márk Jelasity, Spring Semester, 2005, Bologna
May 16,
May 19,
May 23,
May 26,
May 30,
June 1,
June 6,
June 9,
June 13,
June 16
Workshops, conferences
Abstract
Information technology is becoming more and more important,
widespread, and complex. Information systems applied in
environments ranging from private homes to international computer networks
are more and more difficult to install and manage.
This is why IT needs to become self-managing. Most of the functions
related to the installation and normal operation of information systems
(such as configuration, error detection and repair, and adaptation
to changing conditions) need to become transparent to users.
This has been the normal evolutionary path of other fields of technology.
Soon after their introduction, mechanical clocks, cars, electricity,
etc, all shipped with complicated manuals and required the skills of an
engineer to operate normally. Nowadays they are accessible to anyone
with trivial and intuitive user interfaces.
The purpose of this course is to explore the currently developing field
of self-* (self-managing, self-healing, self-configuring, etc)
information systems. We will put a special
emphasis on self-organization and emergence, a currently quickly
developing approach based on ideas borrowed from natural
self-managing systems such as living organisms or societies.
Apart from attempting to provide a coherent and informative birds eye
view of the known diverse and multidisciplinary approaches, the course will
cover selected topics that represent the key ideas of the field.
We put the problem of systems complexity and self-management in a
wider historical context, and we overview the current state of IT from
this point of view. We identify the desirable properties (the goals)
information systems should have and elaborate a bit more on the approaches
towards these properties, comparing the self-aware approach and the
self-organization approach. Finally we present the outline of the course
with some sidenotes.
Reading material
Lecture slides
Even in self-managing systems users and administrators will be in the loop.
We will overview the proposals for high level user control based on policy
based approaches: rule based, goal based and utility based policies.
Reading material
- Tomasz Nowicki,
Mark S. Squillante, and Chai Wah Wu.
Fundamentals of dynamic decentralized
optimization in autonomic computing systems.
In Ozalp Babaoglu, Márk Jelasity, Alberto Montresor, Christof Fetzer,
Stefano Leonardi, Aad van Moorsel, and Maarten van Steen, editors,
Self-Star Properties in Complex Information Systems, volume 3460
of Lecture Notes in Computer Science, Hot Topics.
Springer-Verlag, 2005.
- Jeffrey O. Kephart
and William E. Walsh.
An artificial intelligence perspective on autonomic computing policies.
In Proceedings of the Fifth IEEE International Workshop on Policies for
Distributed Systems and Networks, pages 3–12, 2004.
- Biplav
Srivastava, Joseph P. Bigus, and Donald A. Schlosnagle.
Bringing planning to autonomic applications with ABLE.
In Proceedings of the International Conference on Autonomic Computing
(ICAC'04), pages 154–161. IEEE Computer Society, 2004.
- William E. Walsh,
Gerald Tesauro, Jeffrey O. Kephart, and Rajarshi Das.
Utility functions in autonomic systems.
In Proceedings of the International Conference on Autonomic Computing
(ICAC'04), pages 70–77. IEEE Computer Society, 2004.
Lecture slides
Self-configuration is about automatically connecting system components with
each other so that the system as a whole can perform its function.
This first class aut of the two devoted to this topic is dealing with the
classification of approaches to self-configuration.
The T-Man protocol for building peer-to-peer topologies quickly from scratch
is discussed in detail.
Guest speaker on the topic of configuring a Chord network from scratch
using T-Man: Alberto Montresor.
Reading material
- Márk Jelasity
and Ozalp Babaoglu.
T-Man: Gossip-based overlay topology
management.
In Proceedings of Engineering Self-Organising Applications
(ESOA'05), 2005.
to appear.
- Alberto Montresor,
Márk Jelasity, and Ozalp Babaoglu.
Chord on demand.
In Proceedings of the Fifth IEEE International Conference on Peer-to-Peer
Computing (P2P2005), 2005.
to appear.
- Melanie Mitchell,
James P. Crutchfield, and Rajarshi Das.
Evolving cellular
automata to perform computations.
In Thomas Bäck, David B. Fogel, and Zbigniew Michalewicz, editors,
Handbook of Evolutionary Computation, page G1.15. Institute of
Physics Publishing Ltd, Bristol and Oxford University Press, New York,
1997.
Lecture slides
Continuing the theme of the previous class, and staying with self-organizing
systems, we will look at proposals
for methodologies for creating a local implementation of a global plan.
These will mostly belong the field of amorphous computing.
We will also take a look at a totaly different solution for a similar problem
from the field of Grid computing.
Reading material
- Kasper Støy.
Controlling
self-reconfiguration using cellular automata and gradients.
In Proceedings of the 8th international conference on intelligent
autonomous systems (IAS-8), pages 693–702, Amsterdam, The
Netherlands, 2004.
Selected to appear in Journal of Robotics and Autonomous Systems, special issue
on the best of IAS-8.
- Manish
Agarwal and Manish Parashar.
Enabling autonomic compositions in grid environments.
In Proceedings of the 4th International Workshop on Grid Computing (Grid
2003), pages 34–41, Phoenix, AZ, USA, 2003. IEEE Computer Society.
- Radhika Nagpal.
Programmable self-assembly using biologically-inspired multiagent control.
In International Joint Conference on Autonomous Agents and Multi-Agent
Systems (AAMAS), Bologna, Italy, 2002.
- Harold Abelson, Don
Allen, Daniel Coore, Chris Hanson, George Homsy, Jr. Thomas F. Knight,
Radhika Nagpal, Erik Rauch, Gerald Jay Sussman, and Ron Weiss.
Amorphous
computing.
Communications of the ACM, 43(5), May 2000.
Lecture slides
Reading material
- George Candea,
James Cutler, and Armando Fox.
Improving
availability with recursive microreboots: A soft-state system case study.
Performance Evaluation, 56(1-4):213–248, March 2004.
- Mike Chen, Emre
Kiciman, Eugene Fratkin, Eric Brewer, and Armando Fox.
Pinpoint:
Problem determination in large, dynamic, internet services.
In Proceedings of the International Conference on Dependable Systems and
Networks (IPDS Track), Washington D.C., 2002.
- David Patterson, Aaron
Brown, Pete Broadwell, George Candea, Mike Chen, James Cutler, Patricia
Enriquez, Armando Fox, Emre Kiciman, Matthew Merzbacher, David Oppenheimer,
Naveen Sastry, William Tetzlaff, and Noah Treuhaft.
Recovery oriented
computing (ROC): Motivation, definition, techniques, and case studies.
Technical Report UCB/CSD-02-1175, UC Berkeley Computer Science Department,
March 2002.
Lecture slides
Sociology is rich in examples of self-protection, self-healing and
self-organization. We can use ideas and functional models from sociology to implement
self-managing properties. During this class we explore some of the most interesting
topics: market-inspired optimization and the emergence of cooperation.
Guest speaker on the topic of evolving cooperation: David Hales.
Reading material
- David Hales.
From selfish nodes to cooperative networks:
Emergent link-based incentives in peer-to-peer networks.
In Proceedings of The Fourth IEEE International Conference on
Peer-to-Peer Computing (P2P2004), pages 25–27, Zurich, Switzerland,
August 2004. IEEE Computer Society.
- Andrew Byde, Mathias
Sallé, and Claudio Bartolini.
Market-based
resource allocation for utility data centers.
Technical Report HPL-2003-188, HP Laboratories Bristol, September 2003.
- Robert Axelrod.
The
Evolution of Cooperation.
Basic Books, NY, 1984.
- Garrett Hardin.
The tragedy of
the commons.
Science, 162:1243–1248, 1968.
- Journal of Artificial
Societies and Social Simulation (JASSS).
Lecture slides
- Short intro in ppt
and pdf
- Talk of David Hales in ppt
and pdf
Reinforcement learning is a general paradigm for unsupervised learning
for agents in complex environments where the reward is possibly delayed,
and where the agent does not necessarily have a model of the environment.
Self-managing systems benefit from these features, and indeed, many applications
have been proposed: we discuss routing, self-repair and diagnosis, and
learning strategies in simple profit maximization games.
Reading material
- Michael L. Littman,
Nishkam Ravi, Eitan Fenson, and Rich Howard.
An
instance-based state representation for network repair.
In Proceedings of the Nineteenth National Conference on Artificial
Intelligence (AAAI), pages 287–292, 2004.
- Jeffrey O.
Kephart, James E. Hanson, and Amy R. Greenwald.
Dynamic pricing
by software agents.
Computer Networks, 32(6):731–752, May 2000.
- Gerald Tesauro.
Pricing in agent economies using neural networks and multi-agent Q-learning.
In R. Sun and C.L. Giles, editors, Sequence Learning, volume 1828
of LNAI, pages 288–307. Springer-Verlag, 2000.
- Leslie Pack
Kaelbling, Michael L. Littman, and Andrew W. Moore.
Reinforcement learning: A survey.
Journal of Artificial Intelligence Research, 4:237–285, 1996.
- Justin A. Boyan
and Michael L. Littman.
Packet
routing in dynamically changing networks: A reinforcement learning
approach.
In Advances in Neural Information Processing Systems (NIPS) 6,
pages 671–678, San Mateo, CA, 1994. Morgan Kaufmann.
Lecture slides
Large and distributed self-managing systems inevitably involve complex
networks, either explicitly designed, or unexpected (emergent),
if the system is not centrally controlled.
We review some of the basic models of complex networks and their main
properties.
Reading material
- Sergei N.
Dorogovtsev and J. F. F. Mendes.
Evolution of networks: From Biological Nets to the Internet and WWW.
Oxford University Press, 2003.
- Réka Albert and Albert-László Barabási.
Statistical mechanics of
complex networks.
Reviews of Modern Physics, 74(1):47–97, January 2002.
- R. Milo,
S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U Alon.
Network motifs: Simple building blocks of complex networks.
Science, 298:824–827, 2002.
- Mark E. J. Newman.
Random graphs as models of
networks.
In Stefan Bornholdt and Heinz G. Schuster, editors, Handbook of Graphs
and Networks: From the Genome to the Internet, chapter 2. John Wiley,
New York, NY, 2002.
Lecture slides
Gossip-based protocols are based on periodic random interactions of
participants, which involves exchanging and updating local information.
Due to the extremely weak assumptions they need for efficient operation,
gossip protocols are scalable and robust. Besides, they can implement
a range of services very efficiently, such as information dissemination or
aggregation, which makes them invaluable for implementing self-management
functions in large scale, dynamic environments.
Reading material
- Márk Jelasity,
Alberto Montresor, and Ozalp Babaoglu.
Gossip-based aggregation in large dynamic
networks.
ACM Transactions on Computer Systems, 2005.
to appear.
- Patrick Th.
Eugster, Rachid Guerraoui, Anne-Marie Kermarrec, and Laurent Massoulié.
Epidemic information dissemination in distributed systems.
IEEE Computer, 37(5):60–67, May 2004.
- Robbert van
Renesse, Kenneth P. Birman, and Werner Vogels.
Astrolabe: A robust and scalable technology for distributed system monitoring,
management, and data mining.
ACM Transactions on Computer Systems, 21(2):164–206, May 2003.
(doi:10.1145/762483.762485)
- Alan Demers, Dan
Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis,
Dan Swinehart, and Doug Terry.
Epidemic algorithms for
replicated database maintenance.
In Proceedings of the 6th Annual ACM Symposium on Principles of
Distributed Computing (PODC'87), pages 1–12, Vancouver, British
Columbia, Canada, August 1987. ACM Press.
Presented papers
- Jim Dowling,
Raymond Cunningham, Anthony Harrington, Eoin Curran, and Vinny Cahill.
Emergent consensus in decentralised systems using collaborative reinforcement
learning.
In Ozalp Babaoglu, Márk Jelasity, Alberto Montresor, Christof Fetzer,
Stefano Leonardi, Aad van Moorsel, and Maarten van Steen, editors,
Self-Star Properties in Complex Information Systems, volume 3460
of Lecture Notes in Computer Science, Hot Topics, pages 63–80.
Springer-Verlag, 2005.
(doi:10.1007/11428589_5)
- Paul Robertson
and Robert Laddaga.
Model based diagnosis and contexts in self adaptive software.
In Ozalp Babaoglu, Márk Jelasity, Alberto Montresor, Christof Fetzer,
Stefano Leonardi, Aad van Moorsel, and Maarten van Steen, editors,
Self-Star Properties in Complex Information Systems, volume 3460
of Lecture Notes in Computer Science, Hot Topics, pages
112–127. Springer-Verlag, 2005.
(doi:10.1007/11428589_8)
- Adriana
Iamnitchi and Ian Foster.
A
peer-to-peer approach to resource location in grid environments.
In J. Weglarz, J. Nabrzyski, J. Schopf, and M. Stroinski, editors, Grid
Resource Management. Kluwer Publishing, 2003.
- Romualdo Pastor-Satorras and Alessandro Vespignani.
Epidemics and immunization in
scale-free networks.
In Stefan Bornholdt and Heinz G. Schuster, editors, Handbook of Graphs
and Networks: From the Genome to the Internet, chapter 5. John Wiley,
2002.
- SelfMan 2005 - Home
- 2nd IEEE International Conference on Autonomic Computing (ICAC 2005)
- ESOA'05 Workshop
- WAC 2005: Home
- EASe 2005 :: Engineering of Autonomic Systems
- SELF-STAR: Self-* Properties in Complex Information Systems
- ECCS'05
- IEEE ECBS Engineering of Autonomic Systems :: EASe 2004
- ams,Autonomic Computing Workshop Fifth Annual International Workshop on Active Middleware Services (AMS'03)
- icac,International Conference on Autonomic Computing (ICAC'04)
- 2004 Workshop on Self-Managing Systems (WOSS04) Home Page
- 2002 Workshop on Self-Healing Systems (WOSS02) Home Page
- RCDS: International Workshop on Self-Repairing and Self-Configurable Distributed Systems
- 1st Workshop on the Design of Self-Managing Systems
- NIDISC Workshop
- Bio-ADIT-homepage
- First ACM Workshop on Survivable and Self-Regenerative Systems
Jelasity Márk
Wed Jun 1 15:12:52 CEST 2005