Evolutionary Algorithms for Allocating Data in Distributed Database Systems

A major cost in executing queries in a distributed database system is the data transfer cost incurred in transferring relations (fragments) accessed by a query from different sites to the site where the query is initiated. The objective of a data allocation algorithm is to determine an assignment of fragments at different sites so as to minimize the total data transfer cost incurred in executing a set of queries. This is equivalent to minimizing the average query execution time, which is of primary importance in a wide class of distributed conventional as well as multimedia database systems. The data allocation problem, however, is NP-complete, and thus requires fast heuristics to generate efficient solutions. Furthermore, the optimal allocation of database objects highly depends on the query execution strategy employed by a distributed database system, and the given query execution strategy usually assumes an allocation of the fragments. We develop a site-independent fragment dependency graph representation to model the dependencies among the fragments accessed by a query, and use it to formulate and tackle data allocation problems for distributed database systems based on query-site and move-small query execution strategies. We have designed and evaluated evolutionary algorithms for data allocation for distributed database systems.     

分布式数字资产交易平台的问题与评估

近年来,分布式数字资产交易平台(decentralized digital asset exchanges,DDAE)受到了广泛的关注.基于金融市场基础设施(principles for financial market infrastructures,PFMI)原理,提出了评估数字资产交易平台的5项基本原则.并基于这...     

Using Predicate/Transition-Nets to Model and Analyze Distributed Database Systems

In this paper, a net model for decentralized control of user accesses to a distributed database is proposed. It is developed in detail for the restricted case of updating distributed copies of a single database. Predicate/transition-nets, a first-order extension of Petri nets, are shown to provide suitable means for concise representation of complex decentralized systems and for their rigorous formal analysis. It will be demonstrated in the present paper how these net models can be constructed and interpreted in a quite natural manner and how they can be analyzed by linear algebraic methods. By this, it will be shown that the modeled distributed database system is deadlock-free and guarantees a consistent database as well as a fair and effective service to the users.     

Automatic generation of process flow diagrams

An algorithm which automates the generation of process flow diagrams for distributed programs has been developed. The algorithm maps a graph specification to a graph diagram. The implementation of a graphics monitor uses process flow diagrams to monitor execution of distributed programs on an experimental multiprocessor system. Process states are superimposed onto process flow diagrams to enhance visualization of the execution sequence. Techniques of clustering and unclustering processes are also described.     

A decentralized approach for mining event correlations in distributed system monitoring

Nowadays, there is an increasing demand to monitor, analyze, and control large scale distributed systems. Events detected during monitoring are temporally correlated, which is helpful to resource allocation, job scheduling, and failure prediction. To discover the correlations among detected events, many existing approaches concentrate detected events into an event database and perform data mining on it. We argue that these approaches are not scalable to large scale distributed systems as monitored events grow so fast that event correlation discovering can hardly be done with the power of a single computer. In this paper, we present a decentralized approach to efficiently detect events, filter irrelative events, and discover their temporal correlations. We propose a MapReduce-based algorithm, MapReduce-Apriori, to data mining event association rules, which utilizes the computational resource of multiple dedicated nodes of the system. Experimental results show that our decentralized event correlation mining algorithm achieves nearly ideal speedup compared to centralized mining approaches.     

A proof technique for concurrency control and recovery algorithms for replicated databases

A replicated database is a distributed database in which copies of some data items are stored redundantly at multiple sites. In such a system, an execution of transactions iscorrect if it is equivalent to a serial execution of those transactions on a one copy database. We show that in any serializable execution, if all transactions see the failures and recoveries of data item copies in a consistent order, then the execution is correct. We model this condition using a modified type of serialization graph, and show that if this graph is acyclic then the corresponding execution is correct. We demonstrate the value of this model by using it to prove the correctness of an algorithm for synchronizing access to a replicated database. Philip A. Bernstein is Professor of Information Technology at the Wang Institute of Graduate Studies. Previously, he was Vice President Software at Sequoia Systems, Associate at Harvard University, and a researcher at Computer Corporation of America, where he was codesigner of four distributed database systems. Professor Bernstein's research focuses on the theory and implementation of database systems and transaction processing systems. He is an Associate Editor of ACM Transactions on Database Systems, and on the editorial board of this journal. Nathan Goodman is a senior consulting engineer at Encore Computer Corporation. Previously he was with Sequoia Systems, where he developed a transaction processing system for a fault-tolerant multiprocessor computer. Prior to that he was with Computer Corporation of America, where he participated in the design of three distributed systems: SDD-1, the first relational distributed DBMS; Multibase, a system for querying relational and nonrelational distributed databases; and DDM, a distributed DBMS based on ADA. Dr. Goodman was a professor Computer Science at Harvard University and Boston University. He has done research on query optimization, concurrency control, and failure recovery.Research supported by the National Science Foundation, grant number MCS79-07762, and by the Office of Naval Research, contract number N00014-80-C-674.     

Global scheduling for flexible transactions in heterogeneousdistributed database systems

A heterogeneous distributed database environment integrates a set of autonomous database systems to provide global database functions. A flexible transaction approach has been proposed for the heterogeneous distributed database environments. In such an environment, flexible transactions can increase the failure resilience of global transactions by allowing alternate (but in some sense equivalent) executions to be attempted when a local database system fails or some subtransactions of the global transaction abort. We study the impact of compensation, retry, and switching to alternative executions on global concurrency control for the execution of flexible transactions. We propose a new concurrency control criterion for the execution of flexible and local transactions, termed F-serializability, in the error-prone heterogeneous distributed database environments. We then present a scheduling protocol that ensures F-serializability on global schedules. We also demonstrate that this scheduler avoids unnecessary aborts and compensation     

Finding idle machines in a workstation-based distributed system

The authors describe the design and performance of scheduling facilities for finding idle hosts in a workstation-based distributed system. They focus on the tradeoffs between centralized and decentralized architectures with respect to scalability, fault tolerance, and simplicity of design, as well as several implementation issues of interest when multicast communication is used. They conclude that the principal tradeoff between the two approaches is that a centralized architecture can be scaled to a significantly greater degree and can more easily monitor global system statistics whereas a decentralized architecture is simpler to implement     

Implementation of the conversation scheme in message-baseddistributed computer systems

Several different approaches for implementing conversations in message-based distributed computer systems (DCSs) are discussed. Two different exit control strategies (synchronous and asynchronous) and three different approaches to execution of the conversation acceptance test (centralized, decentralized, and semicentralized) are examined and compared in terms of system performance and implementation cost. An efficient approach to run-time management of recovery information based on an extension of the recovery cache scheme is also discussed. The two major types of conversation structures, name-linked recovery block and abstract data type conversations, are examined to analyze which execution approaches are the most efficient for each conversation structure. As a case study, an unmanned vehicle system is used to illustrate how the approaches can be used in a realistic real-time application     

DEUCON: Decentralized End-to-End Utilization Control for Distributed Real-Time Systems

Many real-time systems must control their CPU utilizations in order to meet end-to-end deadlines and prevent overload. Utilization control is particularly challenging in distributed real-time systems with highly unpredictable workloads and a large number of end-to-end tasks and processors. This paper presents the decentralized end-to-end utilization control (DEUCON) algorithm, which can dynamically enforce the desired utilizations on multiple processors in such systems. In contrast to centralized control schemes adopted in earlier works, DEUCON features a novel decentralized control structure that requires only localized coordination among neighbor processors. DEUCON is systematically designed based on advances in distributed model predictive control theory. Both control-theoretic analysis and simulations show that DEUCON can provide robust utilization guarantees and maintain global system stability despite severe variations in task execution times. Furthermore, DEUCON can effectively distribute the computation and communication cost to different processors and tolerate considerable communication delay between local controllers. Our results indicate that DEUCON can provide a scalable and robust utilization control for large-scale distributed real-time systems executing in unpredictable environments.     

分布式数据库管理系统中的多线程事务处理

本文讨论了在分布式数据库中实现高性能原子事务的一种方法:通过使用多线程结构的事务,分布式数据库系统的性能可以得到大幅提高。性能的改善是由于多个线程的并发执行;而且,由于线程创建和线程间切换的开销都比进程的相应开销小得多,采用多线程的分布式数据库系统的性能比传统的采用单线程(即进程)结构的数据库系统的性能要好得多。     

On the asymptotical optimality of multilayered decentralized consensus protocol

A decentralized consensus protocol refers to a process for all nodes in a distributed system to collect the information/status from every other node and reach a consensus among them. Two classes of decentralized consensus protocols have been studied before: the one without an initiator and the one with an initiator. While the one without an initiator has been well studied in the literature, it is noted that the prior protocols with an initiator mainly relied upon the one without an initiator and thus did not fully exploit the intrinsic properties of having an initiator. By exploiting the concept of multilayered execution, we develop in this paper an efficient multilayered decentralized consensus protocol for a distributed system with an initiator. By adapting itself to the number of nodes in the system, the proposed protocol can determine a proper layer for execution and reach the consensus in the minimal numbers of message steps while incurring a much smaller number of messages than required by prior works. Several illustrative examples are given and performance analysis of the proposed algorithm is conducted to provide many insights into the problem studied. It is shown that the decentralized consensus protocols developed in this paper for the case of having an initiator significantly outperform prior schemes. Specifically, it is proven that (1) the ratio of the average number of messages incurred by the proposed algorithm to that by the prior method approaches zero as the number of nodes increases and (2) the proposed algorithm is asymptotically optimal in the sense that the message number required by the proposed algorithm and that of the optimal one are asymptotically of the same complexity with respect to the number of nodes in the system, showing the very important advantage of the proposed algorithm.     

Decentralized Traffic Control for Non-Holonomic Flexible Automated Guided Vehicles in Industrial Environments

This paper deals with the problem of coordinating flexible automated guided vehicles (AGVs) in real manufacturing systems. The problem consists of ensuring safe and successful task execution while several AGVs operate as a distributed transportation system in real industrial environments. The proposed solution combines different decentralized techniques to increase the flexibility and scalability of the multirobot system. The coordination is addressed by dividing the problem into path planning, obstacle avoidance and traffic control problems. The path planning method takes into account the location of mates for replanning the routes. The obstacle avoidance technique considers the kinematic constraints of the platform for reactive motion control. The traffic control approach makes use of a decentralized control policy that takes into account the capabilities of vehicles. By combining all these techniques and configuring the system properly, we present the successful development of a distributed transportation system composed of a team of flexible AGVs. The proposed solution has been validated using both a set of custom-modified AGVs operating in a real factory and a simulation of several AGVs operating in a virtual scenario.     

多智能体机器人系统分散式通信决策研究

为了减少多智能体机器人系统协调所需通信的数量,提出了一种新的方法.利用有向无环图表示团队的可能联合信度,并基于此以分散式的方式制定通信决策,仅当智能体自身的观察信息显示共享信息将导致期望回报升高时才选择通信.通过维持以及推理团队的可能联合信度将集中式单智能体策略应用于分散式多智能体POM-DP问题.通过实验以及一个详细的实例表明,本文方法能够有效地减少通信资源的使用,同时提高分散执行的性能.     

基于B/S架构的高校医院综合管理平台的设计与实现

以B/S为架构,设计并实现了一个分布式数据处理的高校医院综合管理平台,将校园内不同校区的医院实行统一的信息管理。对高校医院的信息化管理水平和适应医疗管理制度的改革,具有一定的借鉴意义。     

Performance analysis of distributed real-time databases

In a distributed process control system, information about the behavior of physical processes is usually collected and stored in a real-time database which can be remotely accessed by human operators. In this paper we propose an analytic approach to compute the response-time distribution of operator consoles in a distributed process control environment. The technique we develop is based on Markov regenerative processes (MRGPs) and described with the assistance of deterministic and stochastic Petri nets (DSPNs). We construct exact models for performance analysis of centralized and decentralized database architectures. However, due to limitations on the exact solution, we also propose an approximate solution which is then used to study response-time distributions of large systems.     

浅谈分布式数据库系统查询优化

分布式数据库系统的查询优化,就是要寻找执行代价最小的查询执行策略,使系统执行效率达到最高。我们在应用中需要选择适当优化方法,在执行代价和便捷度之间得到最佳执行方案。     

BETASCO: 面向智能合约分片的联盟区块链系统

基于区块链的去中心化应用已在加密数字货币、云存储、物联网等多个领域提供健壮、可信且持久的服务, 然而区块链的吞吐能力难以满足去中心化应用日益增长的性能需求. 分片是当前主流的区块链性能优化技术, 但现有的区块链分片主要面向用户和用户之间的转账交易, 并不完全适用于以智能合约调用交易为主的去中心化应用. 针对此问题, 设计并实现面向智能合约分片的联盟区块链系统BETASCO. BETASCO为每个智能合约提供一个分片作为独立执行环境, 通过基于分布式散列表的合约定位服务将交易路由至目标智能合约所在的分片, 并通过智能合约间的异步调用机制满足跨智能合约的通信和协作需求. BETASCO通过节点虚拟化允许一个节点加入多个分片, 支持同一组节点上多个智能合约的并行执行. 实验结果表明, BETASCO整体吞吐能力可随智能合约数量的增加而线性增长, 且执行单个智能合约的吞吐能力与HyperLedger Fabric相当.     

基于多数法的分布式并发控制的实现及改善

对分布式事务采用多副本并发控制的多数法,实现了一个多层分布式数据库应用系统的模型设计;引入了协调对象并使用COM＋技术,在实现分布式事务执行无阻塞、数据正确恢复的前提下,对模型进行了改善,提高了数据库模型执行的效率。     

分布式数据库系统的查询优化策略

简要的介绍了分布式数据库系统的概念和特点,并在分析比较分布式数据库系统和集中式数据库系统查询优化目标不同特点的基础上,归纳出分布式数据库系统的查询优化目标和代价分析,进而提出查询优化的策略,并在举例中重点讨论了操作执行顺序的不同对查询性能的影响。