Preliminary Proceedings of the Workshop on Geometr

BRICSNS-00-3Cousotetal.(eds.):GETCO’00PreliminaryProceedingsBRICSBasicResearchinComputerSciencePreliminaryProceedingsoftheWorkshoponGeometryandTopologyinConcurrencyTheoryGETCO’00StateCollege,USA,August21,2000PatrickCousotEricGoubaultJeremyGunawardenaMauriceHerlihyMartinRaussenVladimiroSassone(editors)BRICSNotesSeriesNS-00-3ISSN0909-3206August2000Copyrightc2000,PatrickCousot&EricGoubault&JeremyGunawardena&MauriceHerlihy&MartinRaussen&VladimiroSassone(editors).BRICS,DepartmentofComputerScienceUniversityofAarhus.Allrightsreserved.Reproductionofallorpartofthisworkispermittedforeducationalorresearchuseonconditionthatthiscopyrightnoticeisincludedinanycopy.SeebackinnerpageforalistofrecentBRICSNotesSeriespublications.Copiesmaybeobtainedbycontacting:BRICSDepartmentofComputerScienceUniversityofAarhusNyMunkegade,building540DK–8000AarhusCDenmarkTelephone:[phone]Telefax:[phone]Internet:[e-mail]generalaccessiblethroughtheWorldWideWebandanonymousFTPthroughtheseURLs:’2000SatelliteWorkshopofConcur’2000PennState,USA,August21,2000PatrickCousotEricGoubaultJeremyGunawardenaMauriceHerlihyMartinRaussenVladimiroSassonePreliminaryprintunderthepatronageofBRICS:BasicResearchinComputerScienceCentreoftheNationalDanishResearchFoundation.GEometryandTopologyinCOncurrencytheoryForewordThemainmathematicaldisciplinesthathavebeenusedintheoreticalcom-putersciencearediscretemathematics(especially,graphtheoryandorderedstructures),logics(mostlyprooftheoryforallkindsoflogics,classical,intu-itionistic,modaletc.)andcategorytheory(cartesianclosedcategories,topoietc.).GeneralTopologyhasalsobeenusedforinstanceindenotationalseman-tics,withrelationstoorderedstructuresinparticular.Recently,ideasandnotionsfrommainstream\geometrictopologyandal-gebraictopologyhaveenteredthesceneinConcurrencyTheoryandDistributedSystemsTheory(someofthembasedonolderideas).Theyhavebeenappliedinparticulartoproblemsdealingwithcoordinationofmulti-processoranddis-tributedsystems.Amongthosearetechniquesborrowedfromalgebraicandgeometrictopology:Simplicialtechniqueshaveledtonewtheoreticalboundsforcoordinationproblems.Higherdimensionalautomatahavebeenmodelledascubicalcomplexeswithapartialorderreectingthetimeows,andtheirhomotopypropertiesallowtoreasonaboutasystem’sglobalbehaviour.Thisworkshopaimsatbringingtogetherresearchersfromboththemath-ematical(geometry,topology,algebraictopologyetc.)andcomputerscienticside(concurrencytheorists,semanticians,researchersindistributedsystemsetc.)withanactiveinterestintheseorrelateddevelopments.Itfollowstherstworkshoponthesubject\GeometricandTopologicalMethodsinConcurrencyTheorywhichhasbeenheldinAalborg,Denmark,inJune1999.TheWorkshophasbeennanciallysupportedbyHewlettPackard’sBasicResearchInstituteintheMathematicalSciences(Bristol,England)andtheBasicResearchInstituteinComputerScience(Aarhus,Denmark),andIthanktheseinstitutionsforthis,andmorespecicallyJeremyGunawardenaandUeEngberg.Ialsowishtothankthereferees,theauthorsandtheprogrammecommitteemembersfortheirverypreciseandtimelyjob.ManythanksarealsoduetoMichaelMislovewhokindlysupportedtheworkshopbylettingussubmitthepapersthroughtheElectronicNotesinTheoreticalComputerScience.Lastbutnotleast,IwishtothanktheConcurorganizers,CatusciaPalamidessiandDaleMiller,andtheWorkshopcoordinator,UweNestmann,formakingthispossible.EricGoubault,the28thofJuly2000.ProgrammeMonday21August8:45-09:00Opening9:00-10:00Tutorial:TopologyandDirectedTopologybyMartinRaussen10:00-10:15Coeebreak10:15-11:15Tutorial:GeometryofFault-TolerantDistributedSystemsbyMauriceHerlihy11:15-11:30Coeebreak11:30-12:00ConcurrentProcesseswithLoopsfromaGeometricViewpointbyLisbethFajstrupandStefanSokolowski12:00-12:30FirstInformalDiscussion12:30-14:00Lunch14:00-14:30AStudyonSemi-SheavesAssociatedtoTransitionSystemsbyAnaIsabeldeAzevedoSpinolaandEdwardHermannHaeusler14:30-15:00SynchronousMessage-PassingandTopologybyMauriceHerlihy,MarkTuttleandSergioRajsbaum15:00-15:15Coeebreak15:15-15:45FromConcurrencytoAlgebraicTopologybyPhilippeGaucher15:45-16:15OccurrenceCountingAnalysisforthe-calculusbyJeromeFeret16:15-16:30Coeebreak16:30-17:10Conclusion:Results,PerspectivesandOpenProblemsbyEricGoubault17:10-17:30SecondInformalDiscussionContentsp1{22\(Di)topologywithapplicationstoconcurrency.Atutorial,byMartinRaussen(AalborgUniversity,Denmark).p23{43\Innitelyrunningconcurrentprocesseswithloopsfromageometricview-point,byLisbethFajstrup(AalborgUniversity,Denmark)andStefanSokolowski(PolishAcademyofSciences,Gdansk,Poland).p45{61\AStudyonSemi-SheavesAssociatedtoTransitionSystemsRepresentingReactiveSystems,byAnaIsabeldeAzevedoSpinola(UniversidadeFederalFluminense,Niteroi,Brazil)andEdwardHermannHaeusler(PontifciaUniversidadeCatolica,RiodeJaneiro,Brazil).p63{79\SynchronousMessage-PassingandTopology,byMauriceHerlihy(BrownUniversity,USA),SergioRajsbaumandMarkR.Tuttle(CompaqComputerCorporation,Cambr