搜索
EstablishingGlobalPropertiesofMulti-AgentSystemsviaLocalLawsWenxuanZhang,ConstantinSerbanandNaftalyMinskyDepartmentofComputerScience,RutgersUniversity,Piscataway,NJ08854,USAwzhang,serban,minsky@cs.rutgers.eduAbstract.Thispaperispartofalongtermresearchprogramonmulti-agentsystems(MASs),basedonthepropositionthattheinteractionsamongthemembersofalargeandheterogeneoussystemofautonomousagentsneedtobegovernedbyaglobalandstrictlyenforcedlaw;andthatsuchlawsneedtobelocal,sothattheycanbecompliedwithatthelocusofeachagent|withouthavinganydirectinformationofthecoincidentalstateofothermembersoftheMAS.SuchconceptoflawhasbeenrealizedunderourLGIcoordinationandcontrolmechanism.ThispapershowshowlocallawsoveraMAScanbeusedtoestablishglobalandaggregatesystempropertiesinascalablemanner;whereby\aggregatepropertieswemeanpropertiesde nedoverthecoincidentalinteractionsamongseveral,possiblymany,membersofagivenmulti-agentsystem.1IntroductionThispaperispartofalongtermresearchprogramonmulti-agentsystems(MASs),basedonthepropositionthattheinteractionsamongthemembersofalargeandheterogeneoussystemofautonomousagents|whethersoftwareagentsorpeople|needtobegovernedbyaglobal,overarching,law;andonthepropositionthatsuchalawneedstobeenforced,andtheenforcementshouldbedoneinadecentralizedmanner,forscalability.Aswehaveshownin[1],decentralizedenforcementofalawofadistributedMASrequiresthelawtobeformulatedinalocalmanner,sothatitcanbecompliedwithatthelocusofeachagent|withouthavinganydirectinformationofthecoincidentalstateofothermembersoftheMAS.GiventhatthelawofaMASistobeuniformlyenforcedoverallthemembersoftheMAS,itobviouslyhasglobalconsequences,despiteitslocalnature.Thisisanalogoustothelocal(di erential)lawsofphysics,whichhaveglobalconsequencessuchasconservationofenergy.Butcanalocallawbeusedtoestablishaggregatesystemproperties,de nedoverthecoincidentalinteractionsamongseveral,possiblymany,membersofagivenmulti-agentsystem.Thisisthequestionaddressedinthispaper.Theoretically,theanswertothisquestionisarmative.Infact,wehaveshownin[2]thatthelocalformulationoflawsdoesnotreducetheirexpressivepower.ButthisresulthasbeenderivedviaaconstructionthataddsanextraagenttoagivenMAS,whichisemployedasacentralizedreferencemonitorthatmediatesallinteractionsbetweenthemembersoftheMAS,andcanthusenforcearbitraryaggregateproperties.Unfortunately,whileformallylocal,theresultinglawwouldnotbescalable,defeatingthepurposeoflocalization.Thismakesthetheoreticalprovedgeneralityoflocallawslessthansatisfying.Thispaperisamorepracticalstudyofthee ectiveexpressivepoweroflocallaws.Wewilldemonstrateherethatatleastsome|andwebelievemany,ifnotmost|aggregatepropertiesofaMAScanbeimplementedviastrictlylocallaws,involvingonlyaminordegreeofcentralization,whosee ectonthescalabilityoflawenforcementisnegligible.Wecouchourdiscussionofthisissueintermsofthecoordinationandcontrolmechanismformulti-agentsystemscalledlaw-governedinteraction(LGI),whichhasbeendesignedaccordingtotheabovestatedpropositions.Thismechanismhasbeenintroducedin1991[1],implementedexperimentallyin1995[3];andafterseveralextensions,suchasin[2],ithasbeenreleasedforpublicusein[4].Therestofthispaperisorganizedasfollows.WestartinSect.2withamotivatingexampleofapolicythatinvolvesaggregateproperties.InSect.3weprovideanoverviewoftheLGImechanism.InSect.4weshowhowtheaggregatepropertiesofourexamplecanbeestablishedbymeansofanLGIlaw.ThisisfollowedwithbriefdiscussionofrelatedworksinSect.5,andwithconclusioninSect.6.2AnExampleConsideralargedistributedenterpriseE,whichspansalargegeographicalarea.Supposethatthemanagementofthisenterprisedecidedtoprovideitsemploy-eeswiththeabilitytoconductcon dentialandorderlydiscussionsamongthem-selves,freefromanydangerofinterventionoreavesdroppingbythemanagement.Forthispurpose,apolicycalledCD(for\con dentialdiscussion)hasbeende- ned,whichistogovernallsuchdiscussiongroups,tobecalledCD-communities.ThepolicyCDisstatedinformallybelow:1.OnlyemployeesofenterpriseEwhodonotbelongtomanagementareper-mittedtobemembersofaCD-community.2.ThemembersofagivenCD-communityaddresseachotherviatheirself-chosenaliases,andmemberscannotinfertheeNameofitspeers,ortheirLGI-addresses,fromtheiraliases.3.ThealiaschosenbyamemberofaCD-communitymustbeunique,inthefollowingsenses:(a)notwocommunitymemberscanhavethesamealias;and(b)eachemployeecanchoosejustonealias,preventingasingleemployeefromparticipatingundertwodi erentaliases.4.Eachcommunitymembershouldhaveaccesstotheentiremembershipofhiscommunity(thatis,totheentirelistofaliases)atanygivenmomentintime.Points1ofthispolicyensuresthatpeoplenotemployedbythegivenenterprise,orpeopleemployedbytheenterpriseasmanagers,cannotparticipateinanyCD-community,norcantheyeavesdroponanydiscussionwithinsuchacommunity.Notethatthispointinvolvesasubtlesensitivitytotheenvironmentinwhichthiscommunityoperates,sensitivityofthegeneralkindadvocatedin[5](wewillsupportthisparticularsensitivitybymeansofdigitalcerti cation).Point2ensuresanonymityoftheparticipantsinanygivenCD-community,andthuspersonalcon dentiality.Finally,Points3and4,ensureareasona