Institutional Repository
| 网络编程逻辑抽象 | |
| 汪芳 | |
| Major | 计算机软件与理论 |
| Supervisor | 林惠民 ; Stephane Grumbach |
| 2010-11-25 | |
| Degree Grantor | 中国科学院研究生院 |
| Degree Level | 博士 |
| Place of Degree Grantor | 北京 |
| Keyword | 网络编程抽象 递归逻辑查询 声明式网络 语义 复杂度 容错性 编译 局部性 |
| English Abstract | 近年来，无线通信技术的渗透和微型嵌入式计算设备的增加加速了泛在环境的发展。现在，泛在网络开发的一个基本障碍是缺乏编程抽象。本文围绕这一前沿领域，研究网络编程逻辑抽象。主要结果有： 1.研究了定义网络全局性质的递归查询的分布式计算。一阶逻辑及不动点逻辑可以抽象地描述网络全局性质，本文阐明它们的计算可以充分且有效地分布在网络上，并且具有合理的复杂度上限。本文证明在有限度的同步网络上，一阶逻辑查询的分布式计算具有对数的节点内计算复杂度和消息长度、线性的分布式计算复杂度以及多项式的单节点消息复杂度上界。不动点查询的分布式计算具有类似的复杂度，只是它具有多项式的分布式计算复杂度。 2. 研究了定义网络节点的本地行为的网络声明式语言。本文规定了递归的规则语言Netlog的语法。Netlog被用来声明式地描述网络环境下的分布式计算，特别是通讯协议和P2P系统等。Netlog语言以Datalog语言为基础，囊括了尽可能完备的网络应用所需要的原语，包括通讯原语、聚合函数、时效声明、间歇性触发、数据更新以及非确定性选择操作。本文定义了Netlog语言的分布式不动点语义，不仅定义了节点内的计算，而且明确的纳入了节点间的通信，解决了声明式网络语义不确定的问题。同时，本文定义了良好的Netlog程序和强良好的Netlog程序，并证明当良好的程序在同步系统上计算，或者强良好的程序在异步系统上计算，它们在三种复杂度衡量标准，即分布式计算复杂度、单节点消息复杂度和节点单回合计算复杂度下都具有多项式的上限。另外，还证明了强良好的程序的计算结果不受网络有限个数的消息丢失的影响。 Netquest小组开发了Netquest系统以支持Netlog语言并实现其分布式不动点语义。Netquest系统依赖于网络节点上的嵌入式DBMS，这不仅简化了系统的开发，也增强了它在多机种的网络上的可移植性，并且支持数据密集型的应用。此外，Netlog编译器还具备优化模块，可以进一步减轻开发者的负担。一些用Netlog程序编写的经典的分布式算法和网络应用程序已经在网络模拟平台和包含多种计算设备的平台上进行了实验。 3. 进一步考虑了以上两种层面的网络编程逻辑抽象语言的纵向编译。本文阐述了如何将在全局层面表达网络性质的一阶逻辑及不动点查询翻译为在本地层面描述节点行为的Netlog程序。本文设计了普适性的算法，将集中式的Datalog否定程序翻译为分布式的Netlog程序；再加上将一阶逻辑及不动点逻辑翻译为Datalog否定语言的经典结果，从而完成了纵向编译。 4.定义了以上两种网络编程逻辑抽象语言的片段，包括局部的一阶逻辑及不动点查询、节俭的以及强节俭的Netlog程序。它们在表达能力和分布式计算复杂度之间有良好的折中。它们尽可能地保留了分布式计算的局部特性，在定义网络功能上具有丰富的表达能力，并且具有更加紧致的复杂度上限，即具有常数的或者二次的消息复杂度、线性的或者二次的分布式计算复杂度和常数的节点单回合计算复杂度。 |
| Subject | 计算机科学技术基础学科 |
| Language | 中文 |
| Content Type | 学位论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/5554 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | 汪芳. 网络编程逻辑抽象[D]. 北京. 中国科学院研究生院,2010. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| wangfangthesis.pdf（1532KB） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment