理论计算机科学电子笔记108（2004）3-9www.elsevier.com/locate/entcs交互系统扩展抽象Manfred Broy1IstitutfurInformatik，TechnischeUniversita t t tMunchenD-80290Munchen，Germany摘要我们研究离散模型的交互式分布式系统结构成组件和operating- erating同时在一个时间框架。对于这种交互系统中的数据或信号流模型，我们假设每个通信事件及其相关信息都有一个源和一个原因。 理解系统事件间的逻辑依赖关系是事件因果关系推理的关键问题。 由于对结构化模块化方法感兴趣，我们希望能够抽象出系统的所有内部方面，这些方面被用作系统架构中的组件。 我们谈论接口抽象。接口抽象是只保留与组件的使用和架构的接口抽象的构造相关的方面。如果一个架构的接口抽象是其所有组件的接口抽象组合的结果，那么我们就称之为模块化。特别是，我们讨论和研究因果关系，输入和输出，组合性和时间粒度之间的关系和依赖关系。关键词：交互系统，时间，组合，模块化，因果关系，输入/输出，抽象1基本面我们研究的是一个组件系统中的信息流。信息流是在一定的时间范围内在物理或技术系统有许多方法可以表示事件和信息（相反，1电子邮件：broy@in.tum.de1571-0661 © 2004由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2004.11.0034M. Broy/Electronic Notes in Theoretical Computer Science 108（2004）3将某些现象解释为携带信息的方法），这些方法在物理或技术系统中进化。事实上，看待这个问题的一种方式是将因果关系视为一种原则，适用于任何形式的信息处理系统，而与它们的技术或物理表示无关。当然，我们也可以为事件结构建模因果关系，这些事件结构通过并发跟踪来建模系统。因果关系是一个系统的事件和行为之间的逻辑关系我们研究一种特殊形式的因果关系的系统结构成家庭的组件。在这里，我们集中在输入和输出事件之间的因果关系。我们主张：• 在输入和输出之间有一个规范的因果关系概念因果关系与时间模型密切相关。一个基本问题涉及时间模型基本上有两种本质上不同的时间模型，离散（数字）时间和连续（模拟）时间。系统模型的第一个关键问题与时间有关• 是必须用连续时间还是离散时间就足够了？每当两个子系统在一个更大的系统中相互作用，从而相互联系时，我们可以将其解释为信息交换的一种形式信息往往是双向流动的。这就引出了一系列进一步的问题：• 我们是否可以将信息交换建模为一个有发送者和接收者的有向过程（将相互交换建模为有向信息交换的两个步骤）？• 我们是否需要一个信息交换模型，考虑两个或多个子系统的状态，并根据该状态计算系统的新状态？我们主要关心两个问题：• 因果关系的普遍规律是什么• 因果关系和时间有什么关系？具有输入和输出的组件的信息流中的因果关系的基本原理就是这么简单（这里我们假设系统不能预测其未来的输入，因此没有预期的门，可以预测其未来的输入）• 信息（输入）只能在收到后立即处理和转发。M. Broy/Electronic Notes in Theoretical Computer Science 108（2004）35我们讨论了强因果关系和弱因果关系的概念。在强因果关系中，时间模型严格地将所有可能对其他事件有因果关系的事件与那些对它们有因果关系的事件我们考虑一个系统在几个时间粒度。我们假设以下原则：• 如果我们选择的时间粒度足够细，如果输入的时间尺度足够精细，那么系统中就不会因为缺少关于输入时间的信息而留下不确定性/欠规范。如果时间尺度小于最小延迟，则行为函数是强因果的。每个系统行为都是弱因果的。过于粗糙的时间模型可能会把强有力的因果关系抽象• 每一个系统行为都隐含着强因果关系。这意味着存在强因果行为，使得系统行为是时间粗化。如果我们选择的时间粒度不够细，那么我们得到的系统行为只是弱因果的，但隐含着强因果的。2接口抽象对于输入/输出信息处理设备，存在因果关系的关键概念。一定的输出依赖于一定的输入。因果关系表示系统的信息交换动作之间的依赖关系。到目前为止，界面行为只不过是由集值函数表示的关系。在下文中，我们将介绍和讨论接口行为的因果关系的概念。界面行为在一定的时间范围内生成它们的输出并消耗它们的输入这一时间框架有助于描述投入和产出之间的因果关系。在接收到输入之前，不能生成因果依赖于特定输入的输出。然而，适当的定时允许瞬时反应[8]：时间t的输出可能取决于时间t的输入。如果我们考虑另外的无延迟反馈回路，这可能导致因果关系的问题。为了避免这些问题，我们在因果关系的概念之后加强了适当时间的概念。如果F是时间保护的，则第t个时间间隔中的输出不依赖于在第（t-1）个时间间隔之后接收的输入。然后F被适当地定时，并且另外对在第（t-1）次接收到的输入作出反应···6M. Broy/Electronic Notes in Theoretical Computer Science 108（2004）3时间间隔不早于第t个时间间隔。通过这种方式，输入和输出之间的因果关系得到了保证，并且根据精细的时间粒度显式可见。3构成因果关系在组成系统组件时，因果关系是至关重要的。每个组件都有作用和反作用。如果每个步骤都是主动的，并且独立于其他组件的步骤的存在而发生，并且仅响应于（“反应”）其他组件的步骤而发生，如果我们在组件的接口抽象中没有完整的因果关系概念，我们就无法确定哪些事件将确定发生，哪些事件将作为对这些事件的反应而发生，哪些事件将由于因果关系属性而不会发生。那么，就不可能排除代表所谓因果循环的行为，因此在操作上是不可能的。特别是，死锁属性不能从系统组件的接口抽象中正确推导出来。4粗化时间尺度为了使一个组件的时间尺度粗糙因子n是一种抽象形式。这种粗化可能会引入某种不确定性和由于较粗的时间尺度而导致的未充分规范化。特别是，我们感兴趣的问题，失去因果关系的信息，这样的时间粗化。一个特殊的情况是摆脱所有的时间信息。如果一个组件的输出依赖于输入的时间，那么由全时间抽象生成的行为就表现出很多不确定性。然而，如果产生的输出不依赖于输入消息的定时，而只依赖于它们的值和它们到达的顺序，那么由全时间抽象生成的行为然而，因果关系信息可能会以这种方式丢失。如果一个成分是弱因果的，那么它的时间抽象由一个有限的因子n也是弱因果的。然而，没有维持强有力的因果关系。5因果关系的形式化研究如上所述，我们假设对于每个真实的系统行为，都有一个足够精细的时间尺度来捕捉所有的时间差异，特别是对于M. Broy/Electronic Notes in Theoretical Computer Science 108（2004）37输入和输出之间的延迟。在这样的时间尺度上，行为是强因果关系的。对于一个反馈回路，如果所有的输出都是由某个输入引起的，那么这个反馈回路就是由一个组件组成的，一个非线性定点就是因果强因果关系有许多优点，因为它使系统的推理更加具体和简单。特别是，对于强因果行为，很容易通过定点来处理反馈回路，因为时间防护性保证了确定性函数的唯一定点。换句话说，对于强因果关系，所有定点都是因果的。时间保护的缺点是它有限的抽象性，这一点在顺序构图中可以通过延迟的积累来说明。因此，组合并不像需要的那样抽象。一个组合系统的时滞总是大于2。弱因果关系避免了这种困难。但随后，关于定点的推理变得更加复杂。存在着一些非因果关系的定点。这表明因果关系的假设导致了系统的证明原则。引用[1] M.阿巴迪湖兰波特再限定映射的存在性。数字系统研究中心，SRC报告29，1988年8月。[2] M.阿巴迪湖兰波特组成规格。数字系统研究中心，SRC报告66，1990年10月。[3] L. Aceto，M.轩尼诗Adding Action Refinement to a Finite Process Algebra InProc. ICALP 91，Lecture Notes in Computer Science 510，1991，506-519.[4] P·安德鲁斯数理逻辑与类型论导论：通过证明获得真理。计算机科学与应用数学。北京大学出版社1986.[5] R.J. R回来了精化演算，第一部分：顺序不确定性程序。REX工作室。In：J. W. deBakker，W.-P. deRoever，G. Rozenberg（eds）：分布式系统的逐步细化。计算机科学讲义430，1989，42-66。[6] R.J. R回来了精化演算，第二部分：并行和反应式程序。REX工作室。In：J.W. de Bakker，W.-P. de Roever，G.Rozenberg（eds）：分布式系统的逐步细化计算机科学讲义430，1989，67-93。[7] L. Bass，P. Clements，R.卡兹曼软件架构实践Reading，MA，Addison-Wesley 1998.[8] G. Berry，G.贡蒂尔同步程序设计语言：设计，语义，实现。INRIA，研究报告842，1988年。[9] G. Booch，J. Rumbaugh，I.雅各布森面向对象开发的统一建模语言。版本1.0。RATIONAL莱欣诺®软件合作[10] R.布鲁河 格罗苏湾 胡贝尔湾 Rumpe，W. 什未林 面向对象建模技术的精确语义。In：H.基洛夫湾Rumpe（编辑）：《面向对象建模技术的精确语义学研讨会论文集》，1997年，Also：TechnischeUniversit？tMu？nchn，Matittfu？nfmatik，TUM-I9725，1997年。8M. Broy/Electronic Notes in Theoretical Computer Science 108（2004）3[11] J. D.布鲁克，W. B.阿克曼Scenarios：一种不确定计算模型。 In：J. Diaz，I. Ramos（eds）：Lecture Notes in Computer Science 107，Springer 1981，225-259.[12] M.布洛伊作为软件工程基础的数学系统模型。 J. van Leeuwen（编辑）：计算机科学今天计算机科学讲义1000，1995，292-306。[13] M.布洛伊反应系统的代数规范。M.尼瓦特湾Wirsing（eds）：Algesthetics Methodology andSoftware Technology.第五届国际会议，AMAST 96，计算机科学1101讲义，海德堡，Springer1996，487-503。[14] M.布洛伊用状态转换图对系统组件进行规范。技术联合国系统信息技术中心，信息技术中心，TUM-I 9729，1997年5月。[15] M.布洛伊关于一个组件的数学概念及其应用。 1996年慕尼黑第一组件用户会议。修订版见：Software-Concepts and Tools 18，1997，137-148。[16] M.布洛伊时间的精炼。M. Bertran，Th. Rus（eds.）：基于转换的反应式系统开发。1997年马略卡艺术展。计算机科学讲义1231，1997，44-63，将出现在TCS。[17] M.布洛伊交互系统的组成细化。数字系统研究中心，SRC报告89，1992年7月，也在：ACM杂志，第44卷，第100期。6（11月1997），850-891.[18] M.布洛伊 从国家到历史 In：D. Bert，Ch. Choppy，P. Mosses（编辑）：最近的趋势代数发展技术WADT[19] M. Broy，M. Breitlingg，B. Schatz，K. SP IES：Focus中的CaseStudi ES汇总-PARTII。Techn ischeUniversit ？t ？ tMu？ n ch en ， In stittfu？ rIn for matik ， SFB-BerichtNr.342/40/97A，1997年。[20] M. Broy，F.德德里希斯角Dendorfer，M. Fuchs，T. F.格里茨纳河韦伯D istr ie d系统的设计-一种 针 对 Focus 的 方 法 。 Tecch nischeUniversit ？ t ？ t ？ t？ u？ r ？ nfor matik ，Sonderforschungsbereich342 ： MethodendWerkzeugefu？ dieNutz ungpa ralleler ArchitekturenTUM-19202，January 1992.[21] M. Broy，F.德德里希斯角Dendorfer，M. Fuchs，T. F.格里茨纳河韦伯在Focus中的CaseStudi es总结-一种用于Di s tri d系统的D esigMethod。Tecch nischeUniversitéatMunchen，Institt tfuérInformatik ， Sonder forschungsbereich342 ： MethodendWerkze ugefuér die Nutzung parallelerArchitekturen TUM-I 9203，1992年1月。[22] M.Broy ， B.Müoller ， P.Peper ， M.Wirsing.一 个 大 的BraiCImlememntationsPreserveProgramCorrectness.ScienceofComputerProgramming8（1986），1-19.[23] M. Broy，K.史卓伦注重系统开发。Springer 2001（即将出版）。[24] F.布施曼河Meunier，H.作者声明：Robert，M. Stal.面向模式的软件架构：模式系统。NewYork：Wiley 1996.[25] K. M. Chandy，J. Misra. 并行程序设计：基础。Addison Wesley 1988.[26] J. Coenen，W.P. deRoever，J. Zwiers.断言数据验证：调查和Per spective。CHRISTIA N-ALBR ECHTS-UNIVERSIT ？ TK IE L ， IN ST ITUTFUR ？ RIN FORMATIKUND PRAKTISCHEMATHEK，Bericht Nr. 9106，1991年2月。[27] E.伽马河赫尔姆河Johnson，J.设计模式，可重用面向对象软件的元素. Reading，MA：Addison-Wesley 1995.[28] C.A.R.霍尔数据表示的正确性证明。Acta Informatica 1，1972，271- 281.[29] C.A.R. 霍尔通信顺序进程。普伦蒂斯·霍尔1985年[30] F. Huber，B. Sch？atz，G. EIN ERT。 ConsitentGr a p i calSpec ationofDist rid S y stems。于：J. Fitzgerald，C. B. Jones，P. Lucas（ed.）：FMEM. Broy/Electronic Notes in Theoretical Computer Science 108（2004）39[31] G.卡恩并行处理的简单语言的语义。在：J.L. Rosenfeld（编辑）：74.第七十三章Proc. of theIFIP Congress 74，Amsterdam：North Holland 1974，471-475.[32] G.T. Leavens，M.西塔拉曼基于代理的系统的基础。 北京：北京大学出版社.[33] D. C. Luckham，J. J. Kenney，L. M. Augustin，J. Vera，D. Bryan，W.曼恩使用Rapide对系统架构进行规范和分析。IEEE Transactions on Software Engineering ，Special Issue onSoftware Architecture，21（4）：336-355，April 1995.[34] N. A. Lynch ， E. W. 斯 塔 克 输 入 输 出 自 动 机 Kahn 原 理 的 一 个 证 明 。 Information andComputation 82（1）：81-92（1989）.[35] M. Moriconi，X.钱河，巴西-地A.里门施奈德正确的架构改进。IEEE Transactions on SoftwareEngineering，Special Issue on Software Architecture，21（4）：356-372，April 1995.[36] R.米尔纳通信系统的微积分。计算机科学讲义92，Springer 1980。[37] B. 莫勒程序计算的一个简单的结构。 In：M. 布罗伊河 Steinbrügge n（eds. ）：计算系统设计。1998年，马克托伯多夫暑期学校。北约科学系列，F系列：计算机和系统科学173，IOS出版社：阿姆斯特丹1999年，25-100。[38] B. 朗普Formale Methodik des Entwurfs verteilter objektorientierter Systeme. 论文，TechnischeUniversit？r？n for matik1996. 出版社：HerbertUtzVerlag[39] M.作者声明：P.一个领域指南盒学：软件系统架构风格的初步分类。COMPSAC会议记录，华盛顿特区，1997年8[40] M. Shaw，D.加兰软件架构：新兴学科的视角。Englewood Cli Clans，NJ：Prentice Hall 1996.[41] 规范和描述语言（SDL），建议Z.100。技术报告，CCITT，1988年。[42] J. M.斯皮维理解Z - A规范语言及其形式语义。 《理论计算机科学》，剑桥大学出版社，1988年。[43] 克莱门斯·西佩斯基组件软件-超越面向对象编程。Addison-Wesley，ACM Press 1998.
我的内容管理
展开
