Toward a Programming Model for Building Reliable Systems with Distributed State

We present the preliminary design of a programming model for building reliable systems with distributed state from collections of potentially unreliable components. Our transactor model provides constructs for maintaining consistency among the states of distributed components. Our intention is that transactors should support key aspects of both traditional distributed transactions, e.g., for electronic commerce, and systems with weaker consistency requirements, e.g., peer-to-peer file- and process-sharing systems. In this paper, we motivate the need for language support for maintenance of distributed state, describe the design goals for the transactor model, provide an operational semantics for a simple transactor calculus, and provide several examples of applications of the transactor model in a higher-level language.The authors would like to thank James Leifer for detailed comments on previous drafts of this paper, and the anonymous FOCLASA referees for helpful feedback.     

Toward the Concept of Backtracking Computation

This article proposes a new mathematical definition of the execution of pure Prolog, in the form of axioms in a structural operational semantics. The main advantage of the model is its ease in representing backtracking, due to the functionality of the transition relation and its converse. Thus, forward and backward derivation steps are possible. A novel concept of stages is introduced, as a refinement of final states, which captures the evolution of a backtracking computation. An advantage over the traditional stack-of-stacks approaches is a modularity property. Finally, the model combines the intuition of the traditional ‘Byrd box’ metaphor with a compact representation of execution state, making it feasible to formulate and prove theorems about the model. In this paper we introduce the model and state some useful properties.     

Dynamic Ordering for Asynchronous Backtracking on DisCSPs

An algorithm that performs asynchronous backtracking on distributed , with dynamic ordering of agents is proposed, . Agents propose reorderings of lower priority agents and send these proposals whenever they send assignment messages. Changes of ordering triggers a different computation of . The dynamic ordered asynchronous backtracking algorithm uses polynomial space, similarly to standard . The algorithm with three different ordering heuristics is compared to standard on randomly generated . A Nogood-triggered heuristic, inspired by dynamic backtracking, is found to outperform static order by a large factor in run-time and improve the network load.     

基于进程代数的软件动态演化模型初探

许多软件系统由于需求和执行环境的变化,都需要在运行时动态的演化.因此确保软件在演化时以及演化后可以正确的执行变得十分重要.最近Zhang Ji提出一种基于状态的软件动态演化模型,论文尝试建立一种基于进程代数的动态演化模型,并主要以原文中的实例为基础,通过进程代数对其进行建模以及分析,为最终建立此模型积累一定的经验.     

Control Structure Abstractions of the Backtracking Programming Technique

Backtracking is a well-known technique for solving combinatorial problems. It is of interest to programming methodologists because 1) correctness of backtracking programs may be difficult to ascertain experimentally and 2) efficiency is often of paramount importance. This paper applies a programming methodology, which we call control structure abstraction, to the backtracking technique. The value of control structure abstraction in the context of correctness is that proofs of general properties of a class of programs with similar control structures are separated from proofs of specific properties of individual programs of the class. In the context of efficiency, it provides sufficient conditions for correctness of an initial program which may subsequently be improved for efficiency while preserving correctness.     

A Stronger Model of Dynamic Programming Algorithms

We define a formal model of dynamic programming algorithms which we call Prioritized Branching Programs (pBP). Our model is a generalization of the BT model of Alekhnovich et al. (IEEE Conference on Computational Complexity, pp. 308–322, 2005), which is in turn a generalization of the priority algorithms model of Borodin, Nielson and Rackoff. One of the distinguishing features of these models is that they not only capture large classes of algorithms generally considered to be greedy, backtracking or dynamic programming algorithms, but they also allow characterizations of their limitations. Hence they give meaning to the statement that a given problem can or cannot be solved by dynamic programming. After defining the model, we prove three main results: (i) that certain types of natural restrictions of our seemingly more powerful model can be simulated by the BT model; (ii) that in general our model is stronger than the BT model—a fact which is witnessed by the classical shortest paths problem; (iii) that our model has very real limitations, namely that bipartite matching cannot be efficiently computed in it, hence suggesting that there are problems that can be solved efficiently by network flow algorithms and by simple linear programming that cannot be solved by natural dynamic programming approaches.     

三峡工程船舶智能调度系统的动态规划建模与算法

本文讨论了多个并联船闸的智能调度问题，并使用动态规划理论建立了该问题的数学模型，提出了一种基于滑动窗口方法的算法。实践证明，该算法能快速得出较优解，很好地满足了自动编制船闸调度计划的需求。     

支持动态配置的分布式程序设计模型

分布式系统的动态配置问题近年来引起了各国研究者的广泛关注.该文对面向图结构的分布式程序设计模型GOM(graph-oriented model)进行了扩充和改进,提出了支持动态配置的程序设计模型ExGOM(extended graph-oriented model).ExGOM提供了多种基于图结构的配置操作.用户可在配置文件中描述系统结构的动态变化,也可在程序中利用配置操作进行动态配置.这一特性使得系统可支持不可预计的动态配置.文章还给出了以多Agent机制实现ExGOM的系统结构.     

基于动态规划的生产计划优化模型研究与应用

动态规划是运筹学的一个分支,是一种多阶段决策过程,可用于解决多目标决策问题,以使系统的总效果最优.以某企业生产计划的优化安排为实例,在该企业产品的生产能力、生产成本、库存成本等约束条件下,利用动态规划方法建立生产计划安排模型,通过模型求解解决了该企业产品生产计划的优化问题,同时以精练的C++代码实现了相应程序.     

一种基于图分割的动态回溯算法

动态回溯算法在进行回溯时保留所有已赋值变量的值,从而可能与后面赋值的变量产生冲突,其在解决不具有明显子问题结构的约束满足问题时效率较低。为此,将图分割技术应用于动态回溯,通过图分割将变量分为若干集合,当发生回溯时,不保留全部变量的值,舍弃那些与引起冲突的变量在同一集合变量中的值。实验结果表明,该算法在求解没有明显子问题结构的约束满足问题时具有较高的效率。     

简单0-1规划问题的动态DNA折纸计算模型

DNA折纸是一种全新的DNA自组装方法。将一个由DNA折纸卡槽、双态DNA机器、DNA行走机器人组装而成的动态折纸应用于求解0-1规划问题。其中DNA折纸卡槽由1条M13脚手架链和202条钉书钉链折叠而成。双态DNA机器分为不修饰和修饰金纳米颗粒两种情况,对应于0-1规划问题约束变量的取值为0或者1。DNA折纸卡槽和DNA双态机器组装成折纸基底。DNA行走机器人是7条单链折叠成的带有粘性末端的DNA折纸。在链的驱动下,DNA行走机器人在折纸基底上顺时针旋转行走,每步旋转120°。DNA行走机器人每走两步,与折纸基底上的DNA双态机器进行链置换,接收修饰的金纳米颗粒。当整个动态行走过程结束,根据透射电镜下DNA行走机器人接收的金纳米颗粒的大小和个数来判断约束变量的取值是否为可行解。该计算模型采用模块化结构,DNA折纸卡槽、双态DNA机器、DNA行走机器人等折纸均单独设计,且采用透射电镜读解,因而提高了模型实现的可行性。     

信息安全保障技术体系中的一种动态规划模型

在信息保障技术框架中引入了动态规划模型,用于构建信息安全保障体系的产品选型,利用动态规划的最优决策的求解来较为客观地选择产品。文中还引入了性价比系数和协同性矩阵,使动态规划模型更适合于信息安全体系的选择和建立.     

基于随机选择的返回式动态树形反碰撞算法

基于随机选择的返回式动态树形反碰撞算法在解决射频识别系统中碰撞问题时,通过随机选择碰撞位来影响返回式动态树的分支,让尽可能多的只有一位碰撞的一对标签被同时识别,从而提高识别效率,同时通过减少阅读器检测标签时发送给标签的参数,来提高信道利用率。基于该算法的标签设计逻辑简单,为射频识别技术的推广起到了推动作用。     

一种具有回溯机制的智能代理协商模型

近年来,智能代理技术被引入帮助人们处理互联网上的海量商务数据。然而在网上商务自动协商时,智能代理技术仍存在着一些问题。网上商务对话需要智能商务代理具备一套完善的交互模型以应付各种特殊情况。论文通过改进已有的交互模型使其具备协商回溯功能,以提高商务协商的成功率。此外,论文还将讨论如何提高该模型的效率。     

Approximate Dynamic Programming for Self-Learning Control

This paper introduces a self-learning control approach based on approximate dynamic programming. Dynamic programming was introduced by Bellman in the 1950’s for solving optimal control problems of nonlinear dynamical systems. Due to its high computational complexity, the applications of dynamic programming have been limited to simple and small problems. The key step in finding approximate solutions to dynamic programming is to estimate the performance index in dynamic programming. The optimal control signal can then be determined by minimizing (or maximizing) the performance index. Artificial neural networks are very efficient tools in representing the performance index in dynamic programming. This paper assumes the use of neural networks for estimating the performance index in dynamic programming and for generating optimal control signals, thus to achieve optimal control through self-learning.     

一种特征选择的动态规划方法

通过分析特征选择的机理,提出了一种特征选择性能指标和基于此指标的动态规划特征选择方法.使复杂的多类特征信息选择的全局满意解寻求过程,转变成一个简单的阶段性最优化问题.在一定条件下,由各阶段最优决策构成的整体策略等价于原问题的全局满意解.本文法较好地应用于水声信号特征分析.     

Dynamic Programming for Minimum Steiner Trees

We present a new dynamic programming algorithm that solves the minimum Steiner tree problem on graphs with k terminals in time O^*(c^k) for any c > 2. This improves the running time of the previously fastest parameterized algorithm by Dreyfus-Wagner of order O^*(3^k) and the so-called "full set dynamic programming" algorithm solving rectilinear instances in time O^*(2.38^k).     

Out-of-Core and Dynamic Programming for Data Distribution on a Volume Visualization Cluster

Ray directed volume-rendering algorithms are well suited for parallel implementation in a distributed cluster environment. For distributed ray casting, the scene must be partitioned between nodes for good load balancing, and a strict view-dependent priority order is required for image composition. In this paper, we define the load balanced network distribution (LBND) problem and map it to the NP-complete precedence constrained job-shop scheduling problem. We introduce a kd-tree solution and a dynamic programming solution. To process a massive data set, either a parallel or an out-of-core approach is required. Parallel preprocessing is performed by render nodes on data, which are allocated using a static data structure. Volumetric data sets often contain a large portion of voxels that will never be rendered, or empty space. Parallel preprocessing fails to take advantage of this. Our   slab-projection slice, introduced in this paper, tracks empty space across consecutive slices of data to reduce the amount of data distributed and rendered. It is used to facilitate out-of-core bricking and kd-tree partitioning. Load balancing using each of our approaches is compared with traditional methods using several segmented regions of the Visible Korean data set.     

支持动态可重构的软/硬件统一多线程编程模型

针对可重构系统中的数据流驱动应用,提出支持动态可重构的软/硬件统一多线程编程模型SHUMDR及其层次化实现.通过硬件线程接口设计、操作系统内核扩展,便于设计人员以统一的线程视图描述应用的软硬件划分.以数据加密/解密为例进行测试的结果表明,统一线程抽象带来的时间开销和空间资源占用率较小,该模型在探索编程灵活性的同时,能够有效地兼顾硬件的效率.