Lecture Notes in Computer Science 6269 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison,UK TakeoKanade,USA JosefKittler,UK JonM.Kleinberg,USA AlfredKobsa,USA FriedemannMattern,Switzerland JohnC.Mitchell,USA MoniNaor,Israel OscarNierstrasz,Switzerland C.PanduRangan,India BernhardSteffen,Germany MadhuSudan,USA DemetriTerzopoulos,USA DougTygar,USA GerhardWeikum,Germany Advanced Research in Computing and Software Science SublineofLecturesNotesinComputerScience SublineSeriesEditors GiorgioAusiello,UniversityofRome‘LaSapienza’,Italy VladimiroSassone,UniversityofSouthampton,UK SublineAdvisoryBoard SusanneAlbers,UniversityofFreiburg,Germany BenjaminC.Pierce,UniversityofPennsylvania,USA BernhardSteffen,UniversityofDortmund,Germany MadhuSudan,MicrosoftResearch,Cambridge,MA,USA DengXiaotie,CityUniversityofHongKong JeannetteM.Wing,CarnegieMellonUniversity,Pittsburgh,PA,USA Paul Gastin François Laroussinie (Eds.) CONCUR 2010 – Concurrency Theory 21st International Conference, CONCUR 2010 Paris, France, August 31 - September 3, 2010 Proceedings 1 3 VolumeEditors PaulGastin LaboratoireSpécificationetVérification(LSV) ENSdeCachan&CNRS 94235Cachancedex,France E-mail:[email protected] FrançoisLaroussinie LIAFA,UniversitéParisDiderot 75205Pariscedex13,France E-mail:[email protected] LibraryofCongressControlNumber:2010933357 CRSubjectClassification(1998):D.2,F.3,C.2,D.3,H.4,D.2.4 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ISSN 0302-9743 ISBN-10 3-642-15374-7SpringerBerlinHeidelbergNewYork ISBN-13 978-3-642-15374-7SpringerBerlinHeidelbergNewYork Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. springer.com ©Springer-VerlagBerlinHeidelberg2010 PrintedinGermany Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SPIN: 06/3180 543210 Preface This volume contains the proceedings of the 21st Conference on Con- currency Theory (CONCUR 2010), held in Paris, at Universit´e Denis Diderot, August31–September 3, 2010. CONCUR2010 was organized by CNRS, INRIA, ENS Cachan and the Universit´e Denis Diderot. The purpose of the CONCUR conference is to bring together researchers, developers, and students in order to advance the theory of concurrency and promote its applications. The principal topics include basic models of concurrency such as abstract machines, domain theoretic models, game theoretic models, process algebras, and Petri nets; logics for concurrency such as modal logics, probabilistic and stochastic logics, temporallogics, andresource logics; models of specialized systems such as biology-inspired systems, circuits, hybrid systems, mobile and collabora- tive systems, multi-core processors, probabilistic systems, real-time sys- tems, service-oriented computing, and synchronous systems; verification and analysis techniques for concurrent systems such as abstract inter- pretation, atomicity checking, model checking, race detection, pre-order and equivalence checking, run-time verification, state–space exploration, static analysis, synthesis, testing, theorem proving, and type systems; re- lated programming models such as distributed, component-based, object- oriented, and Web services. This edition of the conference attracted 107 submissions. We wish to thank all their authors for their interest in CONCUR 2010. After careful discussions, the Program Committee selected 35 papers for presentation at the conference. Each submission was refereed by three reviewers, who delivered detailed and insightful comments and suggestions. The confer- ence Chairs warmly thank all the members of the Program Committee and all their referees for the excellent support they gave, as well as for the friendly and constructive discussions. We would also like to thank the authors for having revised the papers to address the comments and suggestions by the referees. Theconference program was enriched by the outstandinginvited talks by: – Frank S. de Boer (CWI, Amsterdam, The Netherlands) – Maurice Herlihy (Brown University, Providence, USA) – Holger Hermanns (Saarland University, Saarbru¨cken, Germany) VI Preface – Anca Muscholl (LaBRI, University Bordeaux 1, France) – Vladimiro Sassone (ECS, University of Southampton, UK) The conference this year was co-located with the 17th International Symposium on Temporal Representation and Reasoning (TIME 2010). Additionally, CONCUR 21010 included the following satellite workshops: – Structural Operational Semantics (SOS 2010) – Expressiveness in Concurrency (EXPRESS 2010) – Security in Concurrency (SecCo 2010) – Foundations of Interface Technologies (FIT 2010) – GASICS Workshop on Games for Design, Verification and Synthesis – Foundations of Coordination Languages and Software Architectures (FOCLASA 2010) – International Workshop on Distributed Open and Timed Systems (DOTS 2010) – YoungResearchersWorkshoponConcurrencyTheory(YR-CONCUR) We would like to thank all the people who contributed to the success of CONCUR 2010, in particular the Organizing Committee and the ad- ministrative staff. We gratefully acknowledge the generous support from Digiteo, R´egionˆIledeFrance, CNRS,INRIA,ENSCachan, theMinist`ere de l’enseignement sup´erieur et de la recherche, and the Universit´e Denis Diderot-Paris7.WearealsogratefultoAndreiVoronkovforhisexcellent EasyChair conference system, which we used for the eletronic submission of papers, the refereeing process, and the Program Committee work. June 2010 Paul Gastin Franc¸ois Laroussinie Conference Organization Program Chairs Paul Gastin LSV, ENS Cachan, France Franc¸ois Laroussinie LIAFA, Universit´e Denis Diderot - Paris 7, France Program Committee Mart´ın Abadi UC Santa Cruz and Microsoft Research, CA, USA Parosh Abdulla Uppsala University, Sweden Jos Baeten Eindhoven University of Technology, The Netherlands Steffen van Bakel Imperial College London, UK Julian Bradfield University of Edinburgh, UK Lu´ıs Caires Universidade Nova de Lisboa, Portugal Luca Cardelli Microsoft Research Cambridge, UK Vincent Danos University of Edinburgh, UK Daniele Gorla Universit`a di Roma “La Sapienza”, Italy Anna Ingo´lfsdo´ttir Reykjavik University, Iceland Petr Janˇcar Technical University of Ostrava, Czech Republic Joost-Pieter Katoen RWTH Aachen University, Germany and University of Twente, The Netherlands Kim Larsen Aalborg University, Denmark Nancy Lynch Massachusetts Institute of Technology, USA Ugo Montanari Universita` di Pisa, Italy Markus Mu¨ller-Olm Mu¨nster University, Germany K. Narayan Kumar Chennai Mathematical Institute, India Catuscia Palamidessi LIX, INRIA, France Prakash Panangaden McGill School of Computer Science, Canada Wojciech Penczek IPI PAN, University of Podlasie, Poland Shaz Qadeer Microsoft Research Redmond, WA, USA Jan Rutten CWI, The Netherlands Roberto Segala Universita` di Verona, Italy P.S. Thiagarajan National University of Singapore Walter Vogler University of Augsburg, Germany VIII Conference Organization Steering Committee Roberto Amadio PPS, Universit´e Paris Diderot - Paris 7, France Jos Baeten Eindhoven University of Technology, The Netherlands Eike Best Carl von Ossietzky Universit¨at Oldenburg, Germany Kim Larsen Aalborg University, Denmark Ugo Montanari Universita` di Pisa, Italy Scott Smolka SUNY, Stony Brook University, USA Organizing Committee Benedikt Bollig LSV, CNRS, France Stefan Haar LSV, INRIA, France Florian Horn LIAFA, CNRS, France Stefan Schwoon LSV, INRIA, France Olivier Serre LIAFA, CNRS, France Mihaela Sighireanu LIAFA, Universit´e Denis Diderot - Paris 7, France External Reviewers Roberto M. Amadio Filippo Bonchi Suzana Andova Tom´aˇs Br´azdil Tadashi Araragi Franck van Breugel Farhad Arbab V´aclav Broˇzek Mohamed Faouzi Atig Roberto Bruni Franco Barbanera Marco Carbone Massimo Bartoletti Pietro Cenciarelli Emmanuel Beffara Taolue Chen Nick Benton Yu-Fang Chen Josh Berdine Corina Cˆırstea Marco Bernardo Dave Clarke Nathalie Bertrand Thomas Colcombet Dietmar Berwanger Alejandro Cornejo Chiara Bodei Flavio Corradini Frank S. de Boer Pedro R. D’Argenio Bernard Boigelot Ugo de’Liguoro Benedikt Bollig St´ephane Demri Conference Organization IX Yuxin Deng Agata Janowska Rocco De Nicola Mariusz Jarocki Mariangiola Dezani Christophe Joubert Maria Rita Di Berardini Bartek Klin Alessandro D’Innocenzo Micha(cid:3)l Knapik Lucas Dixon Alexander Knapp Laurent Doyen Sophia Knight Deepak D’Souza Natallia Kokash J´er´emy Dubreil Barbara Ko¨nig Ross Duncan Beata Konikowska Tayfun Elmas Martin Kot Javier Esparza Christian Krause Yuan Feng Jean Krivine J´erˆome Feret Dietrich Kuske Bernd Finkbeiner Akash Lal Cormac Flanagan Peter Lammich Vojtˇech Forejt Mikkel Larsen Pedersen Martin Fra¨nzle J´erˆome Leroux Carsten Fritz Jean-Jacques L´evy Fabio Gadducci Xinxin Liu Philippa Gardner Kamal Lodaya Simon Gay Michele Loreti Blaise Genest E´tienne Lozes Nargess Ghahremani Bas Luttik Marco Giunti Pasquale Malacaria Stefan Go¨ller Radu Mardare Alexey Gotsman Nicolas Markey Carlos Gregorio-Rodr´ıguez Jasen Markovski Marcus Groesser Tom´aˇs Masopust Julian Gutierrez Mieke Massink Peter Habermehl Richard Mayr Serge Haddad Antoni Mazurkiewicz Fr´ed´eric Haziza Damiano Mazza Thomas Hildebrandt Frank McSherry Peter H¨ofner Alexandru Mereacre Espen Højsgaard Massimo Merro Luk´aˇs Hol´ık Roland Meyer Chih-Duo Hong Marino Miculan Hans Hu¨ttel R´emi Morin Radha Jagadeesan Madan Musuvathi X Conference Organization Wojtek Nabial(cid:3)ek Anu Singh Sebastian Nanz Satnam Singh Daniel Neider Pawe(cid:3)l Sobocin´ski Calvin Newport Ana Sokolova Dejan Niˇckovi´c Monika Solanki Artur Niewiadomski Jeremy Sproston Thomas Noll Jiˇr´ı Srba Gethin Norman Christian Stahl Jan Obdrˇz´alek Jan Strejˇcek Petur Olsen Georg Struth Rotem Oshman Rong Su Luca Padovani Kohei Suenaga David Parker Jun Sun Jorge A. Perez S.P. Suresh Iain Phillips Maciej Szreter Sophie Pinchinat Andrzej Tarlecki Nir Piterman Claus Thrane Sanjiva Prasad Francesco Tiezzi Rosario Pugliese Frank Valencia Paola Quaglia Bjo¨rn Victor Sriram Rajamani Hugo Vieira R. Ramanujam Saleem Vighio Anto´nio Ravara Maria Grazia Vigliotti Ahmed Rezine Erik de Vink Pau Ruet Marc Voorhoeve Joshua Sack Igor Walukiewicz Arnaud Sangnier Alexander Wenner Ivano Salvo Jo´zef Winkowski Davide Sangiorgi Verena Wolf Zdenˇek Sawa Weng-Fai Wong Jens-Wolfhard Schicke Boz˙ena Wo´zna-Szcze´sniak Alan Schmitt Tobias Wrigstad Sven Schneider Alex Yakovlev Stefan Schwoon Nobuko Yoshida Anil Seth Kenneth Yrke Jørgensen Jaroslav Sˇevˇc´ık Gianluigi Zavattaro Ali Sezgin Marc Zeitoun Mihaela Sighireanu Lijun Zhang Alexandra Silva Robert Simmons