Maude中协调技术的模拟和评估

理论计算机科学电子笔记175（2007）59-80www.elsevier.com/locate/entcs在Maude中模拟配位的突现性质：集体排序情形Matteo Casadei1 Luca Gardelli2 Mirko Viroli3DEIS，ALMAMATERSTUDIORUM-Universita`diBologna，viaVenezia 52，47023切塞纳，意大利摘要最近的协调语言和模型正在走向应用的技术来自复杂系统的研究背景：自适应性和自组织利用，以解决当今的分布式系统的开放性，动态性和不可预测性 在这一领域，系统是用随机模型来描述的，仿真是分析和设计的一个有价值的工具。因此，在这项工作中，我们专注于建模和模拟协调技术的紧急属性。我们首先开发了一个框架，作为一个通用的引擎，模拟随机过渡系统，作为一个库的MAUDE长期重写系统。然后，我们评估这个工具的协调问题，称为集体排序，自治代理移动元组在不同的元组空间根据当地的标准，并导致出现的完整的聚类属性。保留字：随机变迁系统，自组织，模拟，协调，集体排序。1介绍一些研究相互作用基础演算中的时间、概率和随机性问题的著作-例如[18，10，11]-最近受到越来越多的关注。这些研究的长期目标是为软件系统的定量分析和建模奠定坚实的基础。这不仅有助于解决性能问题[11]，正如过去几年通常考虑的那样，而且在设计动态和开放应用程序时也变得非常重要。自组织以适应环境中不可预测的变化的系统通常需要将适应性作为一种紧急属性。由于这一观察是1电子邮件：m. unibo.it2电子邮件：luca. unibo.it3电子邮件：mirko. unibo.it1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2007.05.02260M. Casadei等人理论计算机科学电子笔记175（2007）59它最初是在自然系统的背景下提出的，很快就被认为是对人工系统的一个鼓舞人心的隐喻[3]。然而，突现属性的一个主要方面是，根据它们的定义，它们不能通过系统设计实现：它们的动态和结果不能完全预测。在这方面提供一些设计支持仍然是可能的。感兴趣的整个系统，即应用程序和环境，可以被建模为随机系统，即，其动态和持续时间方面是概率的系统。在这种情况下，可以运行模拟并将其用作预测系统行为的某些方面的有效工具，并在实际实现手头的应用程序之前支持正确的设计[6]。对于协调模型和语言来说，这种场景特别有趣。一些作品，如TOTA中间件[12]，SwarmLinda [13]和Stochastic KLAIM [14]，虽然从不同的角度出发，但都是在这个想法上发展起来的扩展标准协调模型，具有自适应性和自组织特性。它们共享例如这样的想法，即元组空间中的元组最终以非确定性的方式传播到其他元组空间，这取决于定时和概率。因此，我们的目标是分析模拟工具在这种情况下可能发挥的潜在作用，以确定系统设计的一些方法。许多仿真工具都可以用于这一目的，尽管它们都必须迫使设计人员利用给定的规范语言，因此更好地适用于某些场景，而不是其他场景-例如SPIM [16]，SWARM”[2]，“一”。我们没有依赖其中的一个，而是寻求一种通用的方法。我们评估了MAUDE规范工具的适用性，用于运行模拟的通用引擎[4]。MAUDE允许建模语法和动态方面的一个系统在一个相当灵活的方式，支持例如进程代数，自动机，和网状规范-所有这些都可以看到作为MAUDE 因此，我们开发了一个一个库，用于允许系统设计者以定制的方式根据随机转换系统来指定系统模型，随机转换系统是一个标记的转换系统，其中动作与（发生的）速率相关联。然后，该工具利用其中一个规范来执行系统行为的模拟，从而可以观察某些（可能是意外的）属性的出现这个框架在一个称为集体排序的元组空间场景中进行了测试，集体排序是群体智能社区中称为育雏排序的问题的推广[3]。该应用程序的特点是自治代理管理一组分布式元组空间，目标是将元组从一个空间移动到另一个空间，直到完全我们评估这个问题的解决方案的基础上，一个完全分布式的算法，每个代理移动元组根据当地的标准，排序出现从初始的混沌配置。本文的其余部分如下：第2节提供了一些背景协调技术的适应性和正式框架的随机模型，M. Casadei等人理论计算机科学电子笔记175（2007）5961elling，第3节介绍了我们的随机系统在莫德模拟库，第4节描述了集体排序的情况下，其模拟结果，最后第5节总结提供未来工作的前景。2背景2.1复杂系统与协调在改进软件系统的设计过程中， 弥合 设计和实现之间的差距--不仅要考虑功能和体系结构要求，还要考虑时间和概率等定量方面，这已经成为非常普遍的做法。当处理复杂系统时，经常出现的情况是，系统动力学中的偶然性可能导致出现有趣的特性，因此在设计系统时不能抽象掉协调模型和语言领域正在见证许多朝着这个方向发展的作品，其中大多数都受到自然现象的启发。第一个例子是用于普适计算应用的TOTA（Tuples On The Air）中间件[12]，其灵感来自物理学中的场概念，例如引力场或磁场。这个中间件支持“空间分布元组”的概念为此，当注入元组空间时，每个元组可以配备一些应用程序相关的规则，定义它应该如何在网络中传播，元组的内容应该如何相应地被复制，等等。TOTA主要针对支持环境开放，动态和不可预测的多代理系统，例如。让移动代理在动态网络中相遇。另一个示例架构是SwarmLinda协调模型[13]，虽然与TOTA类似，但更受群体智能和stigmergy的启发[3，8，9]。在SwarmLinda中，使用类似蚂蚁的算法来检索分布式系统中的元组。SwarmLinda中自我技术的使用源于在处理开放性和用户交互的不可预测性时实现自适应的必要性。最后，“群机器人”领域应用受社会昆虫启发的通常，这些系统建立在ad-hoc软件中间件之上[3]，并使用分布式算法解决问题，尽管每个机器人带来非常简单的目标，但整个系统可以用来解决相当复杂的问题-例如在地面上收集物品。这些例子都证明了这样一个事实，即在开放、动态和不可预测的系统中，数量方面发挥着非常重要的作用。这就需要分析和设计工具来支持从正式规范到模拟的各个级别的系统开发。62M. Casadei等人理论计算机科学电子笔记175（2007）592.2随机方面特别是，在相互作用的基础演算工作之后，我们将随机维度确定为系统建模中的关键维度[18]。一个随机系统是一个在时间上的演化是偶然的系统。一方面，这可以用来抽象出特定于实现的问题，只需说明一个过程将需要一些时间来执行。另一方面，通过将执行时间视为根据特定概率分布分布的偶然变量，跟踪时间的进展，并考虑其可变性研究随机建模问题的第一个例子是Priami在[18]中对随机π-演算的研究。在该模型中，每个通信渠道都与一个速率相关联：通过一个渠道进行交互的持续时间是一个随机变量，根据该速率定义的指数分布进行分布。因此，非确定性选择的语义发生了变化，因为动作的概率是所涉及的通道的速率的函数。对于这种语言，SPiM工具已经被引入使用Gillespie算法[16，17，7]运行模拟-运行化学反应模拟的基本算法。该工具主要用于探索生物化学系统的动力学[17]，但它也可以应用于软件系统[6]。在协调的背景下，KLAIM（用于代理交互和移动性的内核语言）[14]是一种用于建模和编程由通过元组空间异步交互的组件组成的分布式系统的从而延长了琳达的寿命KLAIM在哲学上类似于π-微积分，主要是例外的是进程通过元组空间中元组的插入和移除以异步方式通信特别有趣的是KLAIM的随机扩展，称为S到cKLAIM，它基本上遵循与Priami的π -微积分扩展相同的方法S到CK的语义由一个标记的转换系统给出，该转换系统被转换为连续时间马尔可夫链：执行这种转换以允许定量分析和模型检查[14]。KLAIM的概率扩展也存在，称为pKLAIM [5]，它用显式概率取代非确定性，并且时间是离散的。由于存在许多其他随机过程代数的例子，我们在这里感兴趣的是找到一个通用框架，一个在元级别上的框架，它不会促进特定语言，但允许在语法和语义方面的规范中具有很大的灵活性。为此，MAUDE元编程语言似乎很有希望。MAUDE是一种支持等式和重写逻辑规范的高性能响应语言，用于指定广泛的应用[4]。MAUDE程序的基础是模块，它本质上是一组确定代数的定义：模块可以是函数类或系统类。函数模块包含（语法）类型和操作声明，以及实际上是定义抽象数据类型的等式重写规则的等式-因此这对于声明计算系统的算法方面很有用。系统模块也可以有重写规则，即。转换规则-通常用于实现并发M. Casadei等人理论计算机科学电子笔记175（2007）5963重写语义，然后能够处理与交互和系统演化相关的方面。在为随机系统寻找通用模拟工具的过程中，我们认为Maude是一个特别有吸引力的框架，因为它允许直接根据转换规则对系统进行建模，或者原型化一种新的域相关语言，以具有更多的表达能力和紧凑的规范。这是一个自然的出发点，为解决模拟的随机方面的协调：其他语言要求设计师建模系统的现成抽象-例如通道和进程的π演算-这可能不适合在一般情况下。此外，Maude还提供了分析系统性质的工具，包括定理证明和模型检验，这为该研究开辟了有趣的未来工作。3Maude中的一个随机模拟框架在这一节中，我们描述了一个基本的和一般的随机系统模拟框架实现为一个莫德库。为了简洁起见，我们将忽略对MAUDE的完整描述-感兴趣的读者可以参考官方MAUDE文档[4]-尽管它的一些主要方面贯穿始终。我们库的想法是通过标记转换来建模随机系统系统说明，如果重新输入的字符串是S−r−→中的一个字符串：aSJ，我知道你有这个系统状态S可以通过动作a移动到状态SJ，其中r是状态S中动作a的（全局）速率。 给定状态下的动作速率可以理解为动作a在一个时间单位内可能发生的次数（如果系统处于状态S），即它的发生频率。这个想法受到随机π-演算的活动机制的启发[18]，其中每个通道都被赋予固定的本地速率，并且交互的全局速率被计算为通道速率乘以愿意发送消息的进程数量和愿意接收消息的进程数量因此，我们的模型是这种方法的推广，因为计算全局速率的给定一个这样的过渡系统和一个初始状态，一个模拟可以简单地执行：（i）每次检查可用的动作和它们的速率;（ii）概率性地选择其中一个（速率越高，动作发生的可能性越大）;（iii）相应地改变系统状态;最后（iv）按照指数分布推进时间计数器，使得平均频率是动作速率的总和。该技术也是SPiM [16]中采用的技术的推广框架实现由五个Maude模块组成：（i）随机选择包含处理概率和随机性的函数的定义;（ii）标准载体提供了特定系统必须实现的所有定义，以便通过该工具进行模拟;（iii）随机轨迹类型包含随机引擎的数据结构的定义;（iv）随机轨迹功能提供了定义64M. Casadei等人理论计算机科学电子笔记175（2007）59mod随机选择是pr计数器。pr随机。pr转换。prLIST{Float}。sort事件。op@：[Nat] [Float] -> Event [ctor]. opnext：List{Float}-> Event.* 内部定义和实现...op $rand：-> [Float].eq $rand = float（random（counter）/4294967295）....恩德姆Fig. 1. 随机选择模块中的定义。实现随机引擎的一些基本功能;（v）随机跟踪引擎包含随机引擎的实际定义每一个模块都被简单地依次描述。3.1随机选择模块如图1所示，STOCHASTIC-SELECTION模块从子句开始，从其他系统模块导入定义，即COUNTER用于使用递增计数器，RANDOM用于生成随机数，CONVERSION用于将整数转换为浮点数，以及finallyList{Float}用于处理浮点数列表Asort（即 a“ty p e”）事件被定义，具有用于生成其值（[ctor]）的“@“运算符。其思想是，项@（N，F）表示由自然数N表示的动作引起的模拟事件，并且其中，随机数F表示相应的经过时间。下一个函数是模块中最重要的函数，因为它使用随机选择策略从费率列表开始生成事件。例如，当要模拟的系统可以执行以下三种类型之一时，动作，特点是速率2、3、5，有序。它评估为事件@（N，F），其中N可以是0，概率为20%，1的概率为30%，2的概率为50%。F是根据指数分布计算的，平均值为0。1-对于利率的总和是10。一个可能的结果获得的莫德命令“重写next（2.0 3.0 5.0）。“是例如事件@（1，7.330813624033139e-2）。当然，动作和时间的选择是随机的，并利用函数$rand产生一个0到1之间的数字-它本身使用内置函数random，如图中的等式（eq）所示。 为了简洁起见，没有报告函数next的实现的全部细节。3.2标准载波模块当用户提供一个随机系统规范时，该规范必须实现许多定义，这些定义代表了模拟过程中使用的不同概念。图2所示的模块STANDARD-CARRIER提供了定义和必要的约束-它大致扮演了OO语言中抽象类的角色，将在M. Casadei等人理论计算机科学电子笔记175（2007）5965mod STANDARD-CARRIER为prFLOAT。PRBOOL。对状态操作状态进行排序。subsortState<状态。op：StatesStates -> States [ctorasynchronous].排序效果效果。op_#_->[_]：Action Float States-> Effect [ctor].subsort Effect<效果。OP NIL：->效果[ctor]。op_;_：Effects Effects-> Effects [ctor aspherid：nil].* 待执行排序观察。opobs：Nat State Float-> Observation.op_==>：状态->效果。optemp：State-> Bool.op quit：Nat State Float -> Bool. 恩图二、STANDARD-CARRIER模块中的定义手首先，必须提供一个系统状态（State）、一个动作（Action）和一组状态（States）的排序。引入构造器操作符，使两个状态的并置具有排序状态。然后将该运算符声明为交换（transactional）和结合（associative）：这用于声明一个State表示一个（非空）State排序元素的多集。然后定义类型Effect和Effects。操作符#->[ ]用于构造一个Effect。A #F->[Ss]类的项意味着在某个系统状态中，动作A可以以速率F施加，它将系统移动到多状态集合Ss中的任何状态。然后指定一个操作符;来声明sort Effects表示一个由sortEffect元素组成的列表（[assum]），由分号分隔，常量nil表示空列表。SortObservation为用户提供了可观察性的概念：操作符obs获取系统状态并产生部分视图，即sortObservation的元素。模拟的输出将是观察的轨迹：当用户不打算跟踪整个系统动态而是只对少数参数感兴趣时，则要仔细设计函数obs，这是典型的案子最重要的是，用户必须提供operator==>的实现，它接受一个系统状态并产生一个结果列表，即描述了r：aJ系统S−−→ S。最后，用户必须实现谓词temp和quit。温度预测是在状态上定义的，以便将给定状态标记为临时状态，从而防止引擎将其添加到模拟跟踪中。quit谓词用于检查是否/何时必须停止模拟，因为系统似乎达到了最终状态。这两个谓词带有默认实现，都产生false。具体地说，正如我们将在3.6节的例子中所展示的，对于一个用户来说，66M. Casadei等人理论计算机科学电子笔记175（2007）59modSTOCHASTIC-TRACES-TYPES{X：：CARRIER}是prSTOCHASTIC-SELECTION。sort步骤观测跟踪步骤事件事件。子排序步骤<步骤。op[_：_@_]：Nat X$State Float-> Step [ctor format（ni d d d d d d d）].op nil：->步骤。op_+_：Steps Steps-> Steps [ctor aslogid：nil].subsort X$Observation观察。op_，_：Observations Observations-> Observations [ctorasynchronid：empty].opempty：-> Observations [ctor].op_<_>：Step Observations-> Trace [ctor format（d d ni nid）]. op<_>_：Observations Step -> Trace [ctor format（d nid d）].恩德姆图三. STOCHASTIC-TRACES-TYPES模块中的定义。系统仿真他/她必须定义排序Action，State和Observation，以及operators==>和obs的实现。3.3随机跟踪类型模块如图3所示，STOCHASTIC-TRACES-TYPES模块包含所需类型的定义到实施的随机恩，gine。STOCHASTIC-TRACES-TYPES在实现STANDARD-CARRIER的模块X中是参数化的，并且表示要模拟的实际系统;因此，例如，sortX$State和X$Observation用于表示系统的状态和观测的种类首先介绍了（i）步骤、（ii）步骤和（iii）观察的概念的类型和构造器。Step表示模拟步骤，其结构为[N：S@F]，其中N是模拟的倒计时计数器，S是当前系统状态，并且倒计时F是从开始起经过的时间Steps元素是由逗号分隔的步骤列表，而Observations元素是由逗号分隔的观察列表。然后，定义了sortTrace。轨迹表示模拟STn< OB1，OB2，.的结果，OBn>，其中：STn是表示模拟系统的当前状态的步长，OB1，OB2，.，OBn是一个观察列表，提供了对系统演化的看法。3.4随机跟踪函数模块STOCHASTIC-TRACES-FUNCTIONS模块包含随机引擎所需函数的定义。 图4 示出的随机迹函数中最重要的函数的定义。在实现STANDARD-CARRIER的模块X中，随机跟踪函数是参数化的，它代表要模拟的系统：因此，X$State类型和X$Effects类型都是该系统的专用类型首先，定义活动功能。给定一个Effect列表作为输入，activities函数将生成一个Float数字列表，这些数字是M. Casadei等人理论计算机科学电子笔记175（2007）5967mod随机轨迹函数{X：：载体}是pr随机选择。pr随机轨迹类型{X}。操作活动：X$Effects->List{Float}。当量活动（无）=无。eq活性（（A # F ->[LS]）; Es）= F活性（Es）。opnewState：Nat X$Effects-> X$State。等式newState（0，（A # F ->[LS]））= one（LS）。eqnewState（0，E; Es）= newState（0，E）。等式newState（s N，（E; Es））= newState（N，Es）[owise]。恩德姆见图4。 随机跟踪函数模块中的定义。每个效果的作用。然后定义newState函数。给定一个Effect列表和一个Nat数N作为输入，该函数生成一个State，表示新系统新系统下面的3.5节说明了如何使用所描述的函数来定义随机引擎。3.5随机跟踪引擎模块如图5所示，随机跟踪引擎模块提供了以下定义和实现 的 随机发动机 同样随机-痕迹-类型和随机跟踪函数，随机跟踪引擎在模块X中也是参数化的，模块X必须实现标准载波，并且代表要模拟的实际系统;因此，类型X$State和X$Action例如用于表示这种类型。系统模块开始定义一些变量，例如F的类型为Float，FF和FF模块中的函数move实现了仿真引擎的单步行为。 它采取了一个步骤，并产生下一个，随机地，通过适当地使用在随机选择和随机跟踪函数中定义的函数。具体地，当从当前可用速率计算事件@（NN，FF）时，模拟计数器减小（从（SN）到Peano符号中的N），FF的经过时间增加，并且最终通过应用NNth动作（借助于newState函数）获得新状态SS。请注意，如果模拟计数器未达到零，则移动功能有效跟踪功能是利用用户谁想要获得一个完整的跟踪观察结果，他们的模拟系统。该函数由三个等式定义：第一个等式适用于当前状态是临时的，在这种情况下，新的步长由函数move计算，而不更新倒计时，也不添加新的观测值。68M. Casadei等人理论计算机科学电子笔记175（2007）59mod随机轨迹{X：：载体}是保护随机选择。**var O：X$观察。var OO：[X$Observation]. varSS ' S 1 S2 ： X $ 状 态。 var P：步骤。var SS SS1：[X$State]. var Es：[X$Effects].vars N N1 N '：Nat. vars NN：[Nat].变量F F1 F2：浮点型。vars FF FF 'FF 1：[Float]. 变量L：观察结果。op move：Step -> Step.ceqmove（[（sN）：S@F]）=[ N：SS @FF]ifEs：= evalEffects（S==>）/\@（NN， FFFF：= F +FFSS：= newState（NN，Es）.eqmove（[（sN）：S @ F]）=[（sN）：S @ F][owise].操作trace：Trace -> Trace。ceqtrace（[N：S@F] L >）=trace（[N：SS@FF] L >）iftemp（S）/\[（N）：SS @ FF]：= move（[（sN）：S @ F]）.如果不是temp（S），则ceqtrace（[sN：S @F] L>）=trace（[N：SS @FF] L， O>）/\not quit（N，S，F）/|O：= obs（s N，S，F）/\[（N）：SS @ FF]：= move（[（sN）：S @ F]）.如果不是temp（S），则ceq trace（[sN： S @F] L>）=trace（[0： S @F] L， O >）/\quit（N，S，F）/|O：= obs（s N，S，F）.ceq trace（[0：S @F] L>） = L， O >[0： S @F]如果不是temp（S）/|O：= obs（0，S，F）.op last：Trace -> Evt.ceqlast（[N：S @ F]< L >）=last（[N：SS @ FF]）如果温度（S）/\[（N）：SS @ FF]：= move（[（sN）：S @ F]）.ceqlast（[sN：S @F] L >）=last（[N：SS@FF] O >）如果不是temp（S）/\not quit（N，S，F）/|O：= obs（s N，S，F）/\[（N）：SS @ FF]：= move（[（s N）：S @ F]）.ceqlast（[sN：S@F]L>）=evt（N，O，F）ifnot temp（S）/\quit（N，S，F）/|O：= obs（s N，S，F）.ceqlast（[0：S @F] L>） =evt（0，O， F）如果不是temp（S）/|O：= obs（0，S，F）.恩德姆图五. 随机轨迹引擎模块中的定义。模拟的当前跟踪;第二个定义当前状态不是临时状态时引擎的行为，向跟踪添加新的观察最后，当当前状态是最终状态时，第三个步骤适用，在这种情况下，将新的观察添加到当前轨迹，并且终止模拟。例如，制作100个模拟 步骤从状态S0开始， 的M. Casadei等人理论计算机科学电子笔记175（2007）5969M AUDE命令<“rewrite trace（[100：S0@0.0] empty >）。“<，产生如下类型的输出：Obs1 Obs2. Obs100 >，其中Obs1、Obs2. Obs100是显示模拟系统演变的观察结果。最后一个功能是由用户使用的，他们只想看到他们模拟系统的最终观察结果。同样地，最后一个函数通过三个等式来定义：第一个等式适用于当前状态是临时的，在这种情况下，新的步长由函数move计算，而不更新倒计数，也不向模拟的当前迹线添加新的观察;第二个定义当前状态不是临时的时引擎的行为，计算新的模拟步骤并且不产生观测;第三个适用于当前状态是最终状态时，在这种情况下，模拟被终止，并且表示最终状态上的用户定义视图的观测被作为模拟的结果。因此，与trace不同的是，最后一个函数为用户提供了一个仅包含与fi相关的观察结果的结果模拟系统的最终状态要使用last生成100步模拟，MAUDE命令为<结果输出的类型为：，表示对与第100个（最后一个）模拟步骤相关联的状态的观察3.6一个例子：Na− Cl规范我们现在考虑在SPiM文档4中提供的Na−Cl化学反应动力学的标准示例，以便简要解释创建要模拟的系统规范的过程。实现此规范的模块如图6所示。 该系统的特征在于的状态，其中Na是钠原子的数目，Na+是钠离子的数目，Cl是氯原子的数目，Cl-是氯离子的数目。然后定义了两种恒定作用：电离作用代表电离，去电离作用代表去电离。这样，跃迁系统就可以用一个方程来表示，任何状态都有两个可能的结果：一个是电离使Na和Cl减少（通过前置前驱函数p），使Na+和Cl-增加（通过前置后继函数s），另一个则相反。注意，例如，根据Gillespie选择算法在[7]中，电离和去电离的速率在这里与两个反应物的产物成比例，乘以一个恒定值：我们在这里例如。强制去离子因子为电离因子的两倍最后，一个Observation由用户定义的运算<符>@表示。下面关于obs谓词的等式定义了观察的实际含义<，>@。特别是，定义表达了观察的兴趣：（i）Na原子的数量，（ii）Cl原子的数量，（iii）模拟步骤的数量。MAUDE命令：<<4http://www.doc.ic.ac.uk/~anp/spim/Chemical.pdf70M. Casadei等人理论计算机科学电子笔记175（2007）59mod NA-CL是pr FLOAT。内部打印pr转换。pr标准载波。排序NaCl状态。subsort NaCl State：Nat Nat Nat -> State. 操作电 离 去 离 子： ->动 作。 Na Na+ ClCl-：Nat.EQ ==>为（电离）#（浮动（Na * Cl）* 1.0）->[p Na，s Na+，p Cl，s Cl->]）;（去离子#（float（Na+ * Cl-）* 2.0）-> []）。op<_，_>@_：Nat Nat Nat -> Observation.eq obs（Count：Nat，，F：Float）=< Na，Cl>@ Count：Nat.恩德姆<（<100，100>@300），（< 99,99 >@ 299），（< 98,98 >@ 298），（< 97,97 >@ 297），...（<61,61 >@ 7），（< 60,60 >@ 6），（< 59,59 >@ 5），（< 58,58 >@ 4），（< 57,57 >@ 3），（< 58,58 >@ （2），（< 59,59 >@ 1），（<>60,60 >@ 0个）见图6。 基于我们的随机库定义Na−Cl生成图6中报告的轨迹，显示系统在<60，60>附近达到稳定状态。4集体排序为了评估我们的库作为协调机制的模拟引擎的适用性，我们考虑了Swarm智能育雏排序问题[3]的一般情况，适当地移动到元组空间上下文。4.1一般场景和应用我们考虑了一个多智能体系统，其中的环境是结构化的，并与不同种类的项目populated：代理的目标是收集和移动项目的环境，以便根据一个共享的标准来订购它们。这个问题基本上等同于聚类：同质的项目应该被分组在一起，并应该从不同的项目中分离出来。移动到协调模型和语言的典型上下文，我们考虑固定数量的元组空间托管已知元组类型集合的元组的情况。 代理的目标是将元组从一个元组空间移动到另一个元组空间，直到元组根据它们的元组类型聚集在不同的元组空间M. Casadei等人理论计算机科学电子笔记175（2007）5971在几种情况下，对元组进行排序可以提高整个系统的效率。例如，它可以使智能体更容易根据其先前的经验找到感兴趣的信息：在发现先前和相关信息的地方找到信息的概率很高。此外，当元组空间仅包含一种元组时，可以应用聚合技术来提高其性能，并且通常更容易管理和实现负载平衡。然而，增加系统订单是以计算为代价的。实现排序是一项通常应该在线和后台执行的任务即，当系统正在运行时，并且不向主要系统功能添加显著的开销。事实上，寻找能够保证一定程度的时间排序的次优算法可能是有趣的大自然是简单而强大的策略的丰富来源：我们正在寻找的行为已经在社会昆虫领域进行了探索。蚂蚁在组织幼虫和幼虫时执行类似的任务：这类协调策略通常被称为集体排序或集体聚类。虽然蚂蚁的实际行为还没有完全被理解，但有几个模型能够模拟系统的动态。蚂蚁随机游荡，它们的行为由两个概率来模拟，分别是拾取物品的概率Pp和丢弃物品的概率PdPp=.Σ2K1k1+f，Pd=.Σ2Fk2+f、（1）其中k1和k2是常数参数，f是蚂蚁在其邻域中感知到的项目的数量：可以相对于最近遇到的项目来评估f为了评估系统动力学，除了将其可视化之外，提供系统阶次的测量也是有用的。 这样的估计可以通过测量空间熵来获得，如例如在[8]中所做的。基本上，环境被细分为节点，Pi是节点内项目的分数，因此局部熵为Hi=−PilogPi。具有Pi>0的Hi的和给出了整个系统的阶的估计，其应该随时间减小，希望达到零。4.2一种实现集体排序我们设想了一个多智能体系统作为一个集合的代理/通过元组空间进行交互：代理被允许读取，插入和删除元组中的元组空间。此外，对于代理透明地，基础设施提供排序服务，以便在元组空间中保持元组的一定程度的顺序。此服务由一类代理实现，这些代理将负责排序任务。因此，每个元组空间与代理池相关联，如图7所示，其任务是将本地元组空间的内容与环境中的另一元组空间的内容进行比较，并且可能移动某个元组。由于我们希望在线和后台执行此任务，并且使用完全分布式的群集算法，因此我们无法计算公式1中的概率来决定是否移动元组：该方法不会72M. Casadei等人理论计算机科学电子笔记175（2007）59见图7。 实现集体排序的基本架构。可伸缩性，因为它需要对每个元组空间的所有元组进行计数，这可能是不实际的。我们设计了一个基于元组采样的策略，并假设元组空间提供了一个我们称之为urd的读原语，即uniform read。这是标准rd原语的一个变体，它接受一个元组模板并产生任何与模板匹配的元组：原语urd在所有可能返回的元组中以概率的方式选择元组。例如，如果一个元组空间有10个元组t（1）和元组t（2）的20个副本，则操作urd（t（X））返回t（2）的概率是t（1）的两倍。由于标准的Linda-like元组空间通常不实现这种变体，因此它可以例如由一些更具表达力的模型支持，如ReSpecT元组中心[15]。当决定移动元组时，在元组空间TSS上工作的代理遵循以下议程：(i) 它绘制与源元组空间TSS不同的目的元组空间TSD;(ii) 它画出一种k元组;(iii) 它（一致地）从TSS读取元组T1;(iv) 它（一致地）从TSD读取元组T2;(v) 如果T2的类型是k，并且它不同于T1的类型，则它将类型k的元组从TSS移动到TSD。最后一个任务的要点是，如果这些条件成立，则TSD中的元组k的数量更可能高于TSS中的元组k的数量，因此元组可以/应该被移动。重要的是，所有的选择都是根据均匀的概率分布来执行的：在步骤1和2中，它保证了公平性，在步骤3和4中，它保证了所获得的排序是适当的。值得注意的是，这种分布式算法的成功是一个新兴的属性，由概率和时间方面的一个例外。从一个完全混乱的情况开始，是否会达到如果达到了有序化这些问题可以在设计的早期阶段解决，这要归功于仿真工具。M. Casadei等人理论计算机科学电子笔记175（2007）5973modCS-TYPES为prQID。排序元组元组MSet空间QList任务DataSpace。[*]阿斯托里亚酒店op _[_]：Qid Nat -> Tuple [ctor].子排序元组<元组MSet。opempty：-> TupleMSet [ctor].操作_|_：TupleMSet TupleMSet-> TupleMSet [ctor asynchronid：empty].* 元组空间op<_@_>：Nat TupleMSet-> Space [ctor].* 代理任务操作初始化：->任务[ctor]。op[_]：Nat-> Task [ctor].op[_]：Qid->任务[ctor]。op_;_：任务任务->任务[ctor asktop]。[*]subsort任务空间QList<数据空间。opempty：-> DataSpace[ctor].操作_|_：DataSpace DataSpace-> DataSpace [ctor asynchronous]....恩德姆见图8。 模块CS-TYPES。4.3集合排序在MAUDE中的建模与仿真在本节中，我们简要描述了我们对集体排序问题的解决方案的MAUDE规范，并展示了模拟结果。我们的模型坚持存在4元组空间的情况，用自然标识符0，1，2和3标记。 元组表示为MAUDE引用标识符，可以是任何类型，尽管我们在这里考虑的模拟具有四种元组类型此外，我们假设代理以相同的速率访问元组空间-更细粒度可以考虑负载平衡问题，为了简单起见，在本文中没有考虑负载平衡问题。4.3.1MAUDE中的集体排序模型集合排序系统的MAUDE规范在4.2中描述，分为三个模块，分别定义系统状态的结构图8显示了第一个模块中的定义。 SortTuple用于对元组空间中元组的出现进行建模： 例如，出现10个元组类型“a”的元组。排序空间用于表示元组空间：<0@（'a [10]）|（'b [10]）|（'c [10]）|（'d[10]）>表示标识符为0的元组空间具有每个元组类型的10个副本。 任务是一个术语序列，保存当前负责评估元组移动的代理的状态。的序 列 随 着 代 理 做 出 决 定 而 递 增 地 增 长 ： 在 协 议 的 结 尾 ， 它 是[N1];[N2];[Q];[Q1];[Q2]，其中N1是源元组空间标识符，N2是目标元组空间标识符，Q是可能移动的元组类型，Q1是从源读取的元组，Q2是从目标读取的元组 QList是引用标识符的列表，表示要排序的元组类型。菲-74M. Casadei等人理论计算机科学电子笔记175（2007）59通常，DataSpace是Space为简洁起见，未报告模块CS-FUNCTIONS。它基本上定义了三个函数：choose获取一个元组类型标识符列表，并返回一个非确定性选择的;occurringTuples获取元组空间的内容，并返回其中出现的元组类型列表;quantities获取元组空间的内容和元组类型列表，并返回它们每个的基数CS模块，如图9所示，可以看作是集体选择性排序模型的核心。首先，我们定义了六种作用：前者是一类源（0），。. . ，source（3），用于启动在某个