Control of inconsistency and redundancy in PROLOG-type knowledge bases

Because of the incremental and piecemeal nature of its construction, logical inconsistency and redundancy can be built inadvertently into a knowledge base. This paper discusses a methodology for analyzing the contents of a PROLOG-type knowledge base and for eliminating inconsistent and redundant logical elements. It introduces a graphical representation, the goal-fact network, of the logic required to infer a goal and describes the identification of inconsistency in that network. Three increasingly general alternatives, Boolean algebra, the Karnaugh map, and the Quine-McCluskey algorithm, are presented as tools to identify and to eliminate redundancy.     

Analysis and reduction of data spikes in thin client computing

While various optimization techniques have been used in existing thin client systems to reduce network traffic, the screen updates triggered by many user operations will still result in long interactive latencies in many contemporary network environments. Long interactive latencies have an unfavorable effect on users’ perception of graphical interfaces and visual contents. The long latencies arise when data spikes need to be transferred over a network while the available bandwidth is limited. These data spikes are composed of a large amount of screen update data produced in a very short time. In this paper, we propose a model to analyze the packet-level redundancy in screen update streams caused by repainting of graphical objects. Using this model we analyzed the data spikes in screen update streams. Based on the analysis result we designed a hybrid cache-compression scheme. This scheme caches the screen updates in data spikes on both server and client sides, and uses the cached data as history to better compress the recurrent screen updates in possible data spikes. We empirically studied the effectiveness of our cache scheme on some screen updates generated by one of the most bandwidth-efficient thin client system, Microsoft Terminal Service. The experiment results showed that this cache scheme with a cache of 2M bytes can reduce 26.7%–42.2% data spike count and 9.9%–21.2% network traffic for the tested data, and can reduce 25.8%–38.5% noticeable long latencies for different types of applications. This scheme costs only a little additional computation time and the cache size can be negotiated between the client and server.     

The Design of a Generic Intrusion-Tolerant Architecture for Web Servers

Nowadays, more and more information systems are connected to the Internet and offer Web interfaces to the general public or to a restricted set of users. Such openness makes them likely targets for intruders, and conventional protection techniques have been shown insufficient to prevent all intrusions in such open systems. This paper proposes a generic architecture to implement intrusion-tolerant Web servers. This architecture is based on redundancy and diversification principles, in order to increase the system resilience to attacks: usually, an attack targets a particular software, running on a particular platform, and fails on others. The architecture is composed of redundant proxies that mediate client requests to a redundant bank of diversified COTSfootnote{Commercial Off The Shelf.} application servers. The redundancy is deployed here to increase system availability and integrity. To improve performance, adaptive redundancy is applied: the redundancy level is selected according to the current alert level. The architecture can be used for static servers, i.e., for Web distribution of stable information (updated off-line), as well as for fully dynamic systems where information updates are executed immediately on an on-line database. The feasibility of this architecture has been demonstrated by implementing an example of a travel agency Web server.     

基于密度网格的分布式数据流聚类算法

提出一种适用于分布式数据流环境的、基于密度网格的聚类算法。利用局部站点快速更新数据流信息,使网格空间反映当前数据流的变化。中心站点负责在接收及合并局部网格结构后,对全局网格结构进行密度网格聚类以及噪声网格优化,形成全局聚类结果。实验结果表明,该算法能减少网络通信量,提高全局聚类精度。     

Online Approach for Spatio-Temporal Trajectory Data Reduction for Portable Devices

As location data are widely available to portable devices, trajectory tracking of moving objects has become an essential technology for most location-based services. To maintain such streaming data of location updates from mobile clients, conventional approaches such as time-based regular location updating and distance-based location updating have been used. However, these methods suffer from the large amount of data, redundant location updates, and large trajectory estimation errors due to the varying speed of moving objects. In this paper, we propose a simple but effcient online trajectory data reduction method for portable devices. To solve the problems of redundancy and large estimation errors, the proposed algorithm computes trajectory errors and finds a recent location update that should be sent to the server to satisfy the user requirements. We evaluate the proposed algorithm with real GPS trajectory data consisting of 17201 trajectories. The intensive simulation results prove that the proposed algorithm always meets the given user requirements and exhibits a data reduction ratio of greater than 87% when the acceptable trajectory error is greater than or equal to 10 meters.     

The design and implementation of a road safety relational database

Road safety can be measured by the rate of road traffic accidents that occur periodically. In developing countries, one major problem confronting researchers in the area of road safety is that the sources of data collection are not centrally controlled. The proliferation of the sources of data collection leads to data incompatibility, incorrectness, inconsistency and redundancy. These, in turn, lead to inaccurate and conflicting statistics generated and published by different research groups. In this paper, a relational database to support road safety system and a technique for its implementation are presented. It is shown how the database can be processed and accurate statistics about road safety generated and analysed to support planning, decision making and control of operations by the authorities involved in road safety.     

Parallel and distributed trajectory generation of redundantmanipulators through cooperation and competition among subsystems

Autonomous distributed control (ADC) is one of the most attractive approaches for more versatile and autonomous robot systems. The paper proposes a parallel and distributed trajectory generation method for redundant manipulators through cooperative and competitive interactions among subsystems composing the ADC that is based on a concept of virtual arms. The virtual arm has the same kinematic structure as the manipulator except that its end point is located on a joint or link of the manipulator. Then the redundant manipulator can be represented by a set of the virtual arms. Trajectory generation and point to point control of the redundant manipulator are discussed, and it is shown that the kinematic redundancy of the manipulator can be utilized positively in the generated trajectories by using the virtual arms.     

Towards autonomous updating of world models in location-aware spaces

Location-aware systems are systems where location information is used as a rich source of context to enable computers to interact and react to their environment. To date, research involving such systems in the indoor environment has concentrated on the development of cheap, realisable, accurate location systems rather than the continued maintenance of the associated world model needed to derive context. This paper characterises the problems relating to world models that have been observed in a real deployment of a location-aware system. It develops a framework that separates the task of synchronising the real and virtual worlds into two—first monitoring to identify coarse regions of inconsistency, and the second accurate updating of these regions. The paper details methods by which the monitoring can be achieved without the cost of deploying specialised sensors, but rather through collating and analysing human movement patterns and raw location data. It presents an overview of the framework for monitoring, an in-depth case study with experimental results from a deployed system, and a discussion of how accurate updates could be achieved once inconsistent regions are identified.     

New approach to the application of redundant robots

The problem of a heavy robot performing highly accelerated motion is discussed. Since the original six degree of freedom configuration could not solve the task, a suitable redundancy was added to improve the acceleration capabilities. This redundant configuration equipped with the DPS (distributed positioning system) software was able to perform the motion required. The theoretical background and simulation results are presented.     

Detection of Mutual Inconsistency in Distributed Systems

Many distributed systems are now being developed to provide users with convenient access to data via some kind of communications network. In many cases it is desirable to keep the system functioning even when it is partitioned by network failures. A serious problem in this context is how one can support redundant copies of resources such as files (for the sake of reliability) while simultaneously monitoring their mutual consistency (the equality of multiple copies). This is difficult since network faiures can lead to inconsistency, and disrupt attempts at maintaining consistency. In fact, even the detection of inconsistent copies is a nontrivial problem. Naive methods either 1) compare the multiple copies entirely or 2) perform simple tests which will diagnose some consistent copies as inconsistent. Here a new approach, involving version vectors and origin points, is presented and shown to detect single file, multiple copy mutual inconsistency effectively. The approach has been used in the design of LOCUS, a local network operating system at UCLA.     

基于分组特性的冗余流量消除算法

针对大量数据片段冗余传输造成网络传输效率降低的问题,在协议无关冗余消除技术的基础上,提出了一种基于分组特性的冗余流量消除(PFRTE)算法。该算法以对数据包大小分组为基础,动态统计和分析网络流量的双峰特性和分组特性,以对冗余消除贡献大的数据包为阈值,利用滑动窗口计算数据块的边界点,对两个边界点间的数据块计算其指纹并进行指纹匹配。对重复传输的数据块进行简单编码,用编码数据替换重复传输的数据片段,再对消除冗余流量的数据包进行传输。与基于最大值选择和基于静态查找表选择等冗余流量消除算法相比,PFRTE算法动态统计网络流量分组特性,能够大大减少服务器端和客户端的CPU运行时间,同时冗余消除字节节省了8%~40%,证明了该算法的有效性。     

Data consistency in intermittently connected distributed systems

Mobile computing introduces a new form of distributed computation in which communication is most often intermittent, low-bandwidth, or expensive, thus providing only weak connectivity. We present a replication scheme tailored for such environments. Bounded inconsistency is defined by allowing controlled deviation among copies located at weakly connected sites. A dual database interface is proposed that in addition to read and write operations with the usual semantics supports weak read and write operations. In contrast to the usual read and write operations that read consistent values and perform permanent updates, weak operations access only local and potentially inconsistent copies and perform updates that are only conditionally committed. Exploiting weak operations supports disconnected operation since mobile clients can employ them to continue to operate even while disconnected. The extended database interface coupled with bounded inconsistency offers a flexible mechanism for adapting replica consistency to the networking conditions by appropriately balancing the use of weak and normal operations. Adjusting the degree of divergence among copies provides additional support for adaptivity. We present transaction-oriented correctness criteria for the proposed schemes, introduce corresponding serializability-based methods, and outline protocols for their implementation. Then, some practical examples of their applicability are provided. The performance of the scheme is evaluated for a range of networking conditions and varying percentages of weak transactions by using an analytical model developed for this purpose     

基于Voronoi覆盖的邻居信息的重建研究

对于随机部署的大规模无线传感器网络,在保证目标区域完全覆盖的情况下,可以使部分冗余节点进入休眠状态,进而降低能耗.首先介绍了一种分布式的基于2-Voronoi图的冗余节点判别方法,并根据冗余依赖图使部分节点进入休眠状态.然后着重对网络正常工作后出现新增节点和部分节点失效的两种情况分别提出了两个相应的算法,以此来完成因新增节点或部分节点失效而受影响的节点的Voronoi邻居信息重建工作,并对这两个算法的有效性就行了分析.     

Consistent data operations for multi-databases in extended possibility-based data models

This paper considers the data operation for multi-databases in an extended possibility-based data model. Owing to the complexity of the data model considered, inconsistent redundancy of tuples may occur when database relations being operated are associated with different resemblance relations on a given domain. This work first demonstrates the inconsistency problem, and then presents the notions of consistency constraints for multi-database design. Under the constraints, the extended possibility-based databases using different resemblance relations can preserve consistent redundancy.     

Removal of redundant dependences in DOACROSS loops with constantdependences

An efficient algorithm to remove redundant dependences in simple loops with constant dependences is presented. Dependences constrain the parallel execution of programs and are typically enforced by synchronization instructions. The synchronization instructions represent a significant part of the overhead in the parallel execution of a program. Some program dependences are redundant because they are covered by other dependences. It is shown that unlike with single loops, in the case of nested loops, a particular dependence may be redundant at some iterations but not redundant at others, so that the redundancy of a dependence may not be uniform over the entire iteration space. A sufficient condition for the uniformity of redundancy in a doubly nested loop is developed     

Combining flow and dependence analyses to expose redundant array accesses

The success of large-scale, hierarchical and distributed shared memory systems hinges on our ability to reduce delays resulting from remote accesses to shared data. To facilitate this, we present a compile-time algorithm for analyzing programs with doall-style parallelism to determine when read and write accesses to shared data areredundant (unnecessary). One identified, redundant remote accesses can be replaced by local accesses or eliminated entirely. This optimization improves program performance in two ways. First, slow memory accesses are replaced by faster ones. Second, the time to perform other remote memory accesses may be reduced as a result of the decreased traffic level. We also show how the information obtained through redundancy analysis can be used for other compiler optimizations such as prefetching and cache management.     

非一致上下文的自动修复技术

在普适计算中,上下文持续快速变化,上下文感知的应用根据上下文变化自动调整自身的行为以适应这种变化。然而,由于不可预测的环境噪声和动态变化等诸多因素的影响,很容易造成上下文不一致。非一致上下文会导致应用异常,甚至失败。为了解决这个问题,提出了一种自动修复上下文的新技术。它分为两个阶段:生成抽象修复用例;执行用例,以验证上下文不一致性是否已经修复。从用户的实际需要出发,生成的修复用例可以分别满足完整性或正确性。实验结果表明,这种技术在修复成功率上远远超过其他技术。     

Experiential Sampling on Multiple Data Streams

Multimedia systems must deal with multiple data streams. Each data stream usually contains significant volume of redundant noisy data. In many real-time applications, it is essential to focus the computing resources on a relevant subset of data streams at any given time instant and use it to build the model of the environment. We formulate this problem as an experiential sampling problem and propose an approach to utilize computing resources efficiently on the most informative subset of data streams. In this paper, we generalize our experiential sampling framework to multiple data streams and provide an evaluation measure for this technique. We have successfully applied this framework to the problems of traffic monitoring, face detection and monologue detection.     

基于冗余CAN通道的时间触发技术实现

提出了一种基于冗余CAN通道的时间触发技术,保证了分布节点的时钟在其通信通道失效的前提下仍能保证时钟同步,而不需要额外的电子装置。使用该技术可同时获得较高的带宽利用率,抑制不一致的消息重复率,可应用于需传输大量周期数据和少量非周期数据的分布式安全关键系统。     

交替互补定位器及其用于双模比较冗余结构的差错定位

双模比较冗余结构是一种广泛应用的低成本容错结构。当两个冗余模块之一发生故障时,比较器将给出差错检测指示输出,该输出既可以按中断信号形式通知系统作出相应的差错处理,也可以按硬件信号形式直接用于终止系统工作或启动重构,目的是防止故障冗余结构给出错误输出,或者确保系统能够提供连续的服务。这种冗余结构的缺点是比较器不能确切指明故障模块,并因此而需要较大的时间开销来完成系统重构和恢复操作。为解决这一问题,提出了一种具有并发输出差错定位功能的双重比较冗余结构。其中单个冗余模块的输出是一个交替矢量,两个冗余模块的输出形成了一个交替互补矢量,该矢量送入一个交替互补定位器。在正常输入情况下,根据定位器的输出就可以确定冗余系统是无差错的、还是冗余模块或定位顺本身存在故障。交替互补定位器由D型触发器和通用门电路构成,它被证明为是一个完全故障定位的定位器。由于所提出的双模比较冗余结构是基于时间冗余原理工作的,因此它适用于对速度要求并不是非常苛刻的容错系统。