Establishing Global Properties of Multi-Agent Syst

EstablishingGlobalPropertiesofMulti-AgentSystemsviaLocalLawsWenxuanZhang,ConstantinSerbanandNaftalyMinskyDepartmentofComputerScience,RutgersUniversity,Piscataway,NJ08854,USAwzhang,serban,[e-mail]rmresearchprogramonmulti-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(dierential)lawsofphysics,whichhaveglobalconsequencessuchasconservationofenergy.Butcanalocallawbeusedtoestablishaggregatesystemproperties,denedoverthecoincidentalinteractionsamongseveral,possiblymany,membersofagivenmulti-agentsystem.Thisisthequestionaddressedinthispaper.Theoretically,theanswertothisquestionisarmative.Infact,wehaveshownin[2]thatthelocalformulationoflawsdoesnotreducetheirexpressivepower.ButthisresulthasbeenderivedviaaconstructionthataddsanextraagenttoagivenMAS,whichisemployedasacentralizedreferencemonitorthatmediatesallinteractionsbetweenthemembersoftheMAS,andcanthusenforcearbitraryaggregateproperties.Unfortunately,whileformallylocal,theresultinglawwouldnotbescalable,defeatingthepurposeoflocalization.Thismakesthetheoreticalprovedgeneralityoflocallawslessthansatisfying.Thispaperisamorepracticalstudyoftheeectiveexpressivepoweroflocallaws.Wewilldemonstrateherethatatleastsome|andwebelievemany,ifnotmost|aggregatepropertiesofaMAScanbeimplementedviastrictlylocallaws,involvingonlyaminordegreeofcentralization,whoseeectonthescalabilityoflawenforcementisnegligible.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,preventingasingleemployeefromparticipatingundertwodierentaliases.4.Eachcommunitymembershouldhaveaccesstotheentiremembershipofhiscommunity(thatis,totheentirelistofaliases)atanygivenmomentintime.Points1ofthispolicyensuresthatpeoplenotemployedbythegivenenterprise,orpeopleemployedbytheenterpriseasmanagers,cannotparticipateinanyCD-community,norcantheyeavesdroponanydiscussionwithinsuchacommunity.Notethatthispointinvolvesasubtlesensitivitytotheenvironmentinwhichthiscommunityoperates,sensitivityofthegeneralkindadvocatedin[5](wewillsupportthisparticularsensitivitybymeansofdigitalcertication).Point2ensuresanonymityoftheparticipantsinanygivenCD-community,andthuspersonalcondentiality.Finally,Points3and4,ensureareasona