Distributed Information Processing

Doctoral school WS 2002-03
Lecture Team
Prof. Karl ABERER (Lecture) karl.aberer@epfl.ch 693 4679 PSE A 1.32
 

Boi Faltings (Lecture)

boi.faltings@epfl.ch

 693-2738 INR 211
Zoran Despotovic (Seminar) zoran.despotovic@epfl.ch 693-5260 PSE A 1.52
Time and Place

Lecture: Thursday 10-12 INR 219

Description
  In the context of distributed information processing fields of information systems and artificial intelligence have a substantial potential for converging

Fundamental common problem
autonomy of distributed (information processing agents)

Distributed information systems have to deal with the consequences of autonomy
heterogeneity, inconsistency, inefficiency
Artificial Intelligence has developed in the area of agents methods to deal with autonomy
planning, coordination, negotiation

In order to successfully take advantage of the convergence of the areas one needs to know the fundamentals of both of them
Exam
 

Written: review of a paper. Two papers will be provided, the students are allowed to choose one of them.

Allowed material:Scripts, Papers, Personal Notes

Time and place: 11. Feb, 14:15, room INR219. Duration: 3 hours.

 
Grade consists 40% of seminar presentation and 60% of exam

Lecture schedule
22.10.2002
Introduction Distributed Information Systems (pdf)
29.10.2002
Introduction Agents
05.11.2002
XML/RDF (pdf)
12.11.2002
XML storage/filtering (pdf)
19.11.2002
Graph databases (pdf)
26.11.2002
Planning (ps)
03.12.2002
Coordination (ps)
10.12.2002
Constraint Satisfaction (ps)
17.12.2002
Mobile data management (pdf)
24.12.2002
 
31.12.2002
 
07.01.2003
Scalable distributed index structures (pdf)
14.01.2003
P2P Systems (pdf)
21.01.2003
Game theory (pdf)
28.01.2003
Negotiation (pdf)
04.02.2003
Auctions and markets (pdf)
Seminar papers

07.11.2002
XML/RDF
Horrocks, D. Fensel, J. Broekstra, S. Decker, M. Erdmann, C. Goble, F. van Harmelen, M. Klein, S. Staab, R. Studer, and E. Motta, The Ontology Inference Layer OIL, http://www.ontoknowledge.org/oil, 2000. (pdf)
 Presentation:

Zoryana Snovida (pdf)

14.11.2002
XML storage/filtering
Chee Yong Chan, Pascal Felber, Minos N. Garofalakis, Rajeev Rastogi: Efficient Filtering of XML Documents with XPath Expressions. ICDE 2002 (pdf)
 Presentation:

Lam-Son Le (pdf)

21.11.2002
Graph databases
Yaron Kanza, Werner Nutt, Yehoshua Sagiv: Querying Incomplete Information in Semistructured Data. JCSS 64(3): 655-693 (2002) (pdf)
 Presentation:  

Arindam Chakraborty (pdf)

28.11.2002
Planning
Eithan Ephrati and Jeffrey S. Rosenschein: Divide and Conquer in Multi-agent Planning. Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, Washington, August 1994, pages 375-380. (ps)
 Presentation:

Denis Sheynikhovich (pdf)

05.12.2002
Coordination
Tuomas Sandholm:  An Implementation of the Contract Net Protocol Based on Marginal Cost Calculations. Eleventh National Conference on Artificial Intelligence (AAAI-93), Washington DC, pp. 256-262., 1993 (World's first use of combinatorial bidding to allocate trucking tasks; built 1990-92) (ps)
 Presentation:

Sarunas Girdzijauskas (pdf)

12.12.2002
Constraint Satisfaction
Katsutoshi Hirayama, Makoto Yokoo:  An Approach to Over-constrained Distributed Constraint Satisfaction Problems: Distributed Hierarchical Constraint Satisfaction, Proceedings of the Fourth International Conference on Multiagent Systems (ICMAS-2000), 2000. (pdf)
 Presentation:

Viet Nguyen (html)

 
 
Pragnesh Jay Modi, Wei-Min Shen,Milind Tambe, Makoto Yokoo: An Asynchronous Complete Method for General Distributed Constraint Optimization, Proceedings of Autonomous Agents and Multi-Agent Systems Workshop on Distributed Constraint Reasoning, 2002. (pdf)
 Presentation:

Adrian Petcu (pdf)

19.12.2002
Mobile data management
Narayanan Shivakumar, Suresh Venkatasubramanian: Efficient Indexing for Broadcast Based Wireless Systems. MONET 1(4): 433-446 (1996) (pdf)
 Presentation:

Ramprasad Torati (pdf)

09.01.2003
Scalable distributed index structures
Brigitte Kröll, Peter Widmayer: Balanced Distributed Search Trees Do Not Exist. WADS 1995: 50-61 (pdf)
 Presentation:

Paolo Viappiani (sxi)

16.01.2003
P2P Systems
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard M. Karp, Scott Schenker: A scalable content-addressable network. SIGCOMM 2001: 161-172, (pdf)

Presentation:

Fabius Klemm (pdf)

 
 
Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker: Search and replication in unstructured peer-to-peer networks. ICS 2002: 84-95 (pdf)
 Presentation:

Slavisa Markovic (pdf)

23.01.2003
Game theory
G. Zlotkin and J.S. Rosenschein: A domain theory for task oriented negotiation. In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, 416-422, 1993 (ps)

Presentation:

Vinh-Toan Luu (pdf)

30.01.2003
Negotiation
E. Ephrati and J. S. Rosenschein: The clarke tax as a consensus mechanism among automated  agents. In Proceedings of the 9th National Conference on Artificial Intelligence, pages 173-178, San Jose, California, July 1991. (pdf)
 Presentation:

Martin Vesely

06.02.2003
Auctions and markets
Makoto Yokoo, Yuko Sakurai, and Kenji Terada: Price-oriented, Rationing-free Protocol: Guideline for Designing Strategy/False-name Proof Auction Protocols, AAAI-2002 Game-thoretic and Decision-theoretic Agent Workshop, 2002. (pdf)
 Presentation:

Trung Bui  (pdf)

 
 
William E. Walsh, Makoto Yokoo, Katsutoshi Hirayama, and Michael P. Wellman: On Market-Inspired Approaches to Propositional Satisfiability, 17th International Joint Conference on Artificial Intelligence (IJCAI-2001), 2001. (pdf)
 Presentation:

Gleb Skobeltsyn (pdf)

23.01.02003

   Michael Stonebraker, Paul M. Aoki, Witold Litwin, Avi Pfeffer, Adam Sah,
Jeff Sidell, Carl Staelin, Andrew Yu: Mariposa: A Wide-Area Distributed
Database System. VLDB Journal 5(1): 48-63 (1996).  (pdf)		 Presentation

Aoife Hegarty (pdf)

to be determined

   Mustafa Jarrar, Robert Meersman: An Architedcture and Toolset for Practical   Ontology Engineering and Deployment: the DOGMA Aproach. In Proceedings of the International Conference on Ontologies, Databases and Applications of Semantics (ODBase'02), 2002.   Presentation

Dmitry Nikitov (pdf)

to be determined

   David Parkes, Jayant Kalagnanam, Marta Eso: "Achieving Budget-balance with     Vickrey-Based Payment Schemes in Exchanges," Proceedings of the 17th IJCAI, pp. 1161-1168. (pdf) Presentation

Quang Huy Nguyen  (pdf)

to be determined

   Sheila McIlraith, Tran Cao Son, Honglei Zeng: "Mobilizing the Semantic
Web with DAML-Enabled Web Services," Proceedings of the 2001 World Wide
Web Conference.  (pdf)		 still available
Literature
Books
M. Tamer Özsu, Patrick Valduriez: Principles of Distributed Database Systems, Second Edition, Prentice Hall, ISBN 0-13-659707-6, 1999.
S. Abiteboul, P. Bunemann, D. Suciu: Data on the Web: From Relations to Semistructured Data and XML, Morgan Kaufman, 2000.
Ricardo Baeza-Yates, Berthier Ribeiro-Neto, Modern Information Retrieval (Acm Press Series), Addison Wesley, 1999.
Jiawei Han, Data Mining: concepts and techniques, Morgan Kaufman, 2000, ISBN 1-55860-489-8
 
Papers
Daniel Barbará: Mobile Computing and Databases - A Survey. TKDE 11(1): 108-117 (1999)
Swarup Acharya, Rafael Alonso, Michael J. Franklin, Stanley B. Zdonik: Broadcast Disks: Data Management for Asymmetric Communications Environments. SIGMOD Conference 1995: 199-210
Sohail Hameed, Nitin H. Vaidya: Log-Time Algorithms for Scheduling Single and Multiple Channel Data Broadcast. MOBICOM 1997: 90-99
Tomasz Imielinski, S. Viswanathan, B. R. Badrinath: Data on Air: Organization and Access. TKDE 9(3): 353-372 (1997)
Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, Hari Balakrishnan. Chord: A Scalable Peer-To-Peer Lookup Service for Internet Applications. Proceedings of the ACM SIGCOMM, 2001.
Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker. A Scalable Content-Addressable Network. Proceedings of the ACM SIGCOMM, 2001.
M.A. Jovanovic, F.S. Annexstein, and K.A.Berman. Scalability Issues in Large Peer-to-Peer Networks - A Case Study of Gnutella. University of Cincinnati, Laboratory for Networks and Applied Graph Theory, 2001. http://www.ececs.uc.edu/~mjovanov/Research/paper.ps
Frank Dabek, Emma Brunskill, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica, Hari Balakrishnan. Building Peer-to-Peer Systems With Chord, a Distributed Lookup Service. Proceedings of the 8th Workshop on Hot Topics in Operating Systems (HotOS-VIII), 2001. http://www.pdos.lcs.mit.edu/papers/chord:hotos01/hotos8.pdf
Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore W. Hong. Freenet: A Distributed Anonymous Information Storage and Retrieval System. Designing Privacy Enhancing Technologies: International Workshop on Design Issues in Anonymity and Unobservability. LLNCS 2009. Springer Verlag 2001. http://www.freenetproject.org/index.php?page=icsi-revised
Karl Aberer. P-Grid:A self-organizing access structure for P2P information systems. Proceedings of the Sixth International Conference on Cooperative Information Systems (CoopIS 2001), 2001. http://lsirwww.epfl.ch/publications/tr/TR2001-016.pdf
MICHAEL W. BERRY, SUSAN T. DUMAIS, GAVIN W. O'BRIEN. USING LINEAR ALGEBRA FOR INTELLIGENT INFORMATION RETRIEVAL. Department of Computer Science, University of Tennessee, Knoxville, Dec. 1994.
 >