没有合适的资源?快使用搜索试试~ 我知道了~
移动广播系统原理及应用研究进展
理论计算机科学电子笔记162(2006)295-300www.elsevier.com/locate/entcs移动广播系统简介K. V. S.普拉萨德1瑞典哥德堡查尔姆斯理工大学计算机科学系摘要计算机消息通常通过以太网广播,并在它们之间点对点发送:全局异步,本地同步(GALS)。这个范例在这里被一个原始的演算MBS(移动广播系统)捕获。 MBS处理通过本地广播在房间内通话,并在房间之间走动以未知的速度。名称就像π演算中的对象名称,但它是在MBS中变成了发言人等待出发的进程,谁是分组的目的地,和步行者只能进入安静的房间。 这些规则,和一个原始的,使一个房间等待一个从给定房间出来的步行者,似乎适合编程。关键词:进程演算,广播通信,进程移动性,以太网,GALS。1背景及相关工作广播是一种常见而自然的通信原语;见证语音,无线电和以太网。用[10,13]编程也很有趣,对于并发和并行算法,以及优先级[10]和时间[11]的简单处理。演算CBS [10,6]抓住了它的主要特征,并且很容易放在编程语言之上[10]:数据依赖的,可执行的并发CBS程序(不仅仅是模型)已经被正式证明是正确的[4,5,1]。但CBS至少在一个方面失败了:它甚至不切实际地将全球广播建模为同步。克服实际广播范围有限的实用方法包括ad-hoc网络中的多跳(由CBS的最新变体[7,8]建模),以及广播之间的异步点对点跳,如互联网的部分。本文报告了第一个实验与符号的移动广播系统(MBS)的灵感来自后者:1电子邮件地址:prasad@cs.chalmers.se1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.12.096296KVS Prasad/Electronic Notes in Theoretical Computer Science 162(2006)295⟨≥⟩⇑他们谈话是自治的,以太网风格的单信道广播(如[10])。每一次广播都能被房间里的其他人听到,而外面的人却听不到。进程一次只说一个,仲裁解决争用。Walking是一种异步的进程移动,速度未知;要只发送消息a,就发送进程a!0的情况。这些设计选择构成了MBS的基本模型本文的其余部分将开发MBS,但需要顺便提及之前开发的CBS的前两个扩展。HOBS [9]对广播之间的异步缓冲器进行建模,因此可以被视为捕获另一个GALS模型,但它需要高阶微积分的复杂性。π-b演算[3]是用广播代替握手的π-演算。 因此,它可以被看作是CBS与链接移动-的能力(而MBS模型处理移动性),但π-b演算并不直接模拟实际的方法来扩展广播范围。2MBS中的编程为了支持编程,基本模型必须通过同步行走和说话的方式来补充。通过实例提出了要求(SR)为了找到一组数字中最大的一个,让每个数字都尝试宣布自己,直到它成功,或者它听到一个更大的数字:p(n)d=efx?ifxnthen0elsep(n)+n!0的情况。然后,p(n)的并行组合将广播一个递增的数字序列,最后一个是最大值。但是如何检测终止?SR 1:步行者只能进入安静的房间(或者更确切地说,稳定的房间;见SR 3)。那么行尸就可以离开房间再进来宣布终止快速排序:选择两个新的名字x和y,把数字放在一个房间里,让每一个尝试宣布自己。旋转成功,所有较小的数字都转到房间x,其余的转到房间y。继续递归。在一次步行之后组装进程是很麻烦的,所以SR2:所有在同一时间离开同一个房间的人必须一起步行(因此到达)。如果需要,很容易避免分组。为了收集已排序的列表,报告者沿着最小的列表遍历(虚拟)树的房间。为了防止掉队者,比如记者,加入一个仍在整理自己的群体,SR3:退出优先于发言。快速排序说明了MBS的两个优点:房间x和y可以独立进行,并且在精心选择的房间中,大多数广播对房间中的大多数人都很感兴趣(浪费的带宽较少)。在编程中,房间通常是逻辑的,而不是物理的。子程序。一个关键的需求是在广播之间的私人房间中执行子例程,因此MBS具有直到一个进程从A返回。3减少和减少设N是一个可数的名字集合。进程集P和房间集R是由下面的BNF语法归纳定义的集合。设a,b,x,y∈N,而KVS Prasad/Electronic Notes in Theoretical Computer Science 162(2006)295297↑s::=0。亚洲开发银行:p.vx.s. S|t. c?a[p]↓|⊥∈∪↑ ⇑ ↑↑⟨ ⟩∗∈ <${<$} ∈ {} ∈∈CN,hT ,F,p,qP和s,tR. a,b,c(非约束性)和x,y(约束性)是暗示性的,而不是正式的。房间具有唯一的名称,并且不嵌套。p= 0。 x?p. 艾利克斯?p+a!q。 一个小矮人。 a↑hp. Vx. p. p|Q进程0默默地听到一切,x?p用它听到的任何名字替换p中的x,x?p+a!q可以说a并变成q,但它像x?p在听觉中,p复制p(听到a是触发器),Tp写作p(见上文),Fp(写作p)是p加入一个前往a的团体。 设l,m,nPR. 然后vx.m创造了一个新的名字x的作用域为m,m n是m与n平行。 房间?a [p](写作a[p])是p在房间A,而B?a[p]是p,在等候室a中等待来自b的步行者,房间0是空系统,并且adb:p是p从a步行到b。在下面的结构一致性表中,x是新的(即重命名以避免冲突)。α-等价m|0毫米|恩河|ML|(米)|n)(l|米)的|n vx. 010vx. 是的。我也是。vx. mνx. (米)|n)n(νx. 米)的|n如果x∈/fn n上面是熟悉的法律。接下来是明显的变体,再下面是MBS特有的定律:vx.y?你好vx. pv x. 你说什么?p+a!是吗?vx.p+a!v x.q vx. (a↑hp)a↑hνx.p(x ↑ p)|(x ↑ q)x↑(p|q)c?a[v x.p] vx.c?a[p]最后,局部函数 /b,其中p/b是p在听到名字b时的变化。0/b0(x?p)/bp [b/x]x?p+a!q/bp [b/x](a p)/a p|a p(a p)/b a p如果a/= b(a ↑ hp)/b(v x.p)/b v x. (p/b)(p|q)/b(如果p/b或q/b则,否则p/b|q/b)所以p拒绝听,最后一条定律说,如果任何一个成分听,平行合成都拒绝听。拒绝倾听意味着没有人可以说话(公理1)。接下来,p和s上的谓词,通过归纳法定义:p(“p是稳定的”,需要SR1),pab(“p想要加入一个绑定到b的组“,需要SR2),和b s(“s中没有房间b“,创建房间)。X是新鲜的。“Implies”, “and” and “or”0↓(x?p)↓(ap)↓(b↑p)ab b0b(aJda:p)b(a[p])ifab p ↓<$(ν x.p)↓pab <$(ν x.p)ab b s<$b(νx.s)p↓ q↓ |q)↓pab <$qab <$(p|q)ab b s b t b(s|t)的范围内298KVS Prasad/Electronic Notes in Theoretical Computer Science 162(2006)295[]。↑−→−→∧ −→⇒|−→|∗ ↑ ⇑ †† †† ⟨⟩⇑ † ↑ |∗ ↑|最后,y,s−→sJ定义如下,即空间s可以简化为sJ。附注pqa[p]阿q1 .一、 b[X]?p+a!q|r]−→b[q|(r/a)]如果r/a二、 a[q|b↑p]−→a[q]|adb:pif<$qab3. adb:p|b[q]−→b[p|q]i fq↓四、 a[q|bp]−→b?a[q]|adb:p5。 adb:p|是吗?b[q]−→b[p|q]6. vx. (个|adx:p)−→νx。(个|x[p])ifx s7. s−→sJs|t−→sJ|t8. s−→sjvx。s−→νx。SJ9 .第九条。sts−→sJsjtjt−→tJ因为p拒绝倾听,公理1强制执行SR 3。它还说,言语是自动的(即使它必须等待离开的过程);公理b[p]b[p/a]的缺失(其中a必须从稀薄的空气中拔出)说听觉不是。公理2直接执行SR2,公理3执行SR1。 公理4和公理5处理保持出口和房间。公理6说,每个名字都有一个唯一的空间。 第7、8、9条很简单。 规则sSJ不TJS tsJtJmay 可以添加,但无法检测实际并行度4编码许多编码可以像π演算一样完成,但使用房间而不是通道。要把b调到a频道,请到a房间去听b。设apd=efx?0+a!p. 为了实现递归定义A(x)d=efp,设一个房间A [Ao?x?op],并且来自房间o的呼叫者将A(v)替换为A A o v0。然后一个!q,它会说a并变成q,忽略它听到的所有内容,可以通过X d=e fx来实现?X+a!q。让一个??p的定义是a?p/ap和a??p/b=0,如果a b。 可能很简单-在房间o由vm.x?m(x o0a o p). 如果x=a,则p0返回以释放所持有的房间o,否则仅返回0。分组是必不可少的,否则0可能会首先返回,而p可能会丢失广播。房间m内有复制器,使用一次后可以进行垃圾收集。触发复制因子实际上允许编码完整的case结构。λ-演算也已经在遵循米尔纳的π -演算编码的MBS中被编码,如同在表示信道的房间中遵循简单协议的握手(即π -演算的要素)一样5正在探索的新配方优先级隐含在SR它们可以显式地包含在演算中-扩展[10]中的思想,进程具有其最高优先级的自主动作(讲话或退出)的优先级,并且将拒绝听取较低优先级的讲话。进程始终可以进入房间。目前看来,KVS Prasad/Electronic Notes in Theoretical Computer Science 162(2006)295299在这样一个优先考虑的演算中,SR可以在很大程度上作为给程序员的建议而不是强加的另一个正在探索的变化是将逻辑房间映射到物理位置(不能随意创建)。如果在同一位置的房间之间移动,则移动是瞬时的,但如果在不同位置的房间之间移动,则需要时间。位于同一位置的房间交错执行其操作(同一位置一次只能执行一个操作)。在这样的演算中,不需要冻结房间;子程序房间仅仅起作用。比呼叫房间的优先级更高 因此,似乎只有优先事项 来同步行走和说话。一个代价是快速排序算法现在没有并行性,因为它是在一个位置执行6结论本文介绍了在这样一个早期阶段的工作,因为它似乎捕捉到一个有趣的模型,它是可能的,甚至有趣的程序。MBS需要通过实例进行更多的探索,并就制定(优先事项,地点等)作出决定, 才能尝试一个观测理论 等问题至于MBS是否可以从π-演算推导出来,答案甚至更晚(答案是可以建立在[2,12]上)。确认MBS被提交给同事在查默斯和帝国,玛丽女王,和剑桥大学。我感谢他们的详细评论和鼓励。我主要要感谢Ulf Norell,他在Haskell中实现了MBS。我们正在一起工作的编码,通过它,我们看到了需要的引用[1] 约根·H Andersen,Ed Harcourt,and K. V. S. 普拉萨德一种机器验证的分布式排序算法。技术报告RS-96-4,金砖国家,1996年2月[2] 克里斯蒂安·埃内和特拉扬·蒙泰安 点对点通信与广播通信的表达性。计算理论基础,LNCS 1684,1999。[3] 克里斯蒂安·埃内和特拉扬·蒙泰安一种基于广播的通信系统演算。在IPDPS,第149页。IEEE计算机学会,2001年。[4] E. 我的儿子。共感应类型在交替位保护的编码验证中的应用。《证明和程序类型》,LNCS 1158。Springer,1995年。[5] 艾德·哈考特帕维尔·帕茨科夫斯基和KVS普拉萨德表示参数化过程的框架。技术报告,查默斯大学,部计算机科学,一九九五年[6] 马修·亨尼西和朱利安·拉特克广播系统演算的互模拟。Theor. Comput. Sci. ,200(1-2):225[7] 塞巴斯蒂安·南兹和克里斯·汉金ad-hoc网络的形式化安全分析。 2004年[8] 塞巴斯蒂安 南斯 和 克里斯 汉金ad-hoc网络路由协议的静态分析。在SIGPLAN,IFIP WG 1.7 Issues in the Theory of Security(WITS),2004。[9] Karol Ostrovsky,K. V. S.普拉萨德和瓦利德·塔哈关于广播系统的原始高阶微积分。见公私伙伴关系,第2ACM,2002年。300KVS Prasad/Electronic Notes in Theoretical Computer Science 162(2006)295[10] K. 诉S. 普拉萨德广播系统的演算Sci. Comput. 程序. ,25,1995。[11] K. V. S.普拉萨德 及时播报。 在协调,LNCS 1061。Springer,1996年。[12] K. V. S.普拉萨德在CCS中解释广播演算直到互模拟。电子笔记理论 Comput. Sci. ,52(1),2001.[13] D. Sands和M. Weichert从Gamma到CBS:用广播过程细化多集变换。在1931年。IEEE Computer SocietyPress,1997.
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 李兴华Java基础教程:从入门到精通
- U盘与硬盘启动安装教程:从菜鸟到专家
- C++面试宝典:动态内存管理与继承解析
- C++ STL源码深度解析:专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手:数据管理与企业增值的战略
- Eclipse IDE基础教程:从入门到精通
- Shell脚本专家宝典:全面学习与资源指南
- Tomcat安装指南:附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华:必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功