An implementation of F-channels

An F-channel can permit as much concurrency as a non-first-in-first-out (FIFO) communication channel and yet retain the properties of a FIFO channel that lead to simplicity of reasoning in design and proofs of the correctness of distributed algorithms. The author presents an implementation of an F-channel on top of a non-FIFO channel that derives its non-FIFO nature from a message taking any of the alternate paths from the source to the destination in the underlying network in which each channel is either an F-channel implemented using some other implementation or recursively using the implementation presented or a FIFO channel. The correctness of the implementation is proven     

基于冲突率预测的自适应并发控制算法

并发控制算法能够保证数据库事务集并发执行的正确性和一致性。为了提高并发事务的执行效率,提出了一种基于冲突率预测的自适应并发控制算法(ACC-PRC)。该算法将并发控制过程分为信息收集和策略选择两个阶段。信息收集阶段利用先验事务队列保证事务执行的可串行化,并且利用循环冲突队列收集系统的事务执行状态。策略选择阶段在循环冲突队列上运用改进的加权移动平均法预测下一阶段冲突率,并根据双向阈值决策下一阶段的并发策略。所提算法在事务到达率较高时能保持良好的事务执行效率,同时能够准确及时地感知冲突率的变化。对比实验表明ACC-PRC算法的综合性能优于HCC算法和ADCC算法。     

An optimistic approach to lock-free FIFO queues

First-in-first-out (FIFO) queues are among the most fundamental and highly studied concurrent data structures. The most effective and practical dynamic-memory concurrent queue implementation in the literature is the lock-free FIFO queue algorithm of Michael and Scott, included in the standard Java ^TM Concurrency Package. This work presents a new dynamic-memory concurrent lock-free FIFO queue algorithm that in a variety of circumstances performs better than the Michael and Scott queue. The key idea behind our new algorithm is a novel way of replacing the singly-linked list of Michael and Scott, whose pointers are inserted using a costly compare-and-swap (CAS) operation, by an “optimistic” doubly - linked list whose pointers are updated using a simple store, yet can be “fixed” if a bad ordering of events causes them to be inconsistent. We believe it is the first example of such an “optimistic” approach being applied to a real world data structure. A preliminary version of this paper appeared in the proceedings of the 18th International Conference on Distributed Computing (DISC) 2004, pages 117–131.     

基于交互式定理证明的并发程序验证工作综述

并发程序与并发系统可以拥有非常高的执行效率和相对串行系统较快的响应速度,在现实中有着非常广泛的应用。但是并发程序与并发系统往往难以保证其实现的正确性,实际应用程序运行中的错误会带来严重的后果。同时,并发程序执行时的不确定性会给其正确性验证带来巨大的困难。在形式化验证方法中,人们可以通过交互式定理证明器严格地对并发程序进行验证。本文对在交互式定理证明中可用于描述并发程序正确性的验证目标进行总结,它们包括霍尔三元组、可线性化、上下文精化和逻辑原子性。交互式定理证明方法中常用程序逻辑对程序进行验证,本文分析了基于并发分离逻辑、依赖保证逻辑、关系霍尔逻辑等理论研究的系列成果与相应形式化方案,并对使用了这些方法的程序验证工具和程序验证成果进行了总结。     

内存数据库并发控制算法的实验研究

并发控制算法是数据库系统保证事务执行正确且高效的重要手段,一直是数据库工业界和学术界研究的核心问题之一.将并发控制算法的基本思想归纳为“先定序后检验”,并基于该思想对现有各类并发控制算法进行了重新描述和分类总结.基于在开源内存型分布式事务测试床3TS上的实际对比实验,系统性地探究了各类算法的优缺点和适用场景,为面向内存数据库的并发控制算法的后续研究提供参考.     

实时数据库的准一致性可串行化并发控制

可串行化的并发控制对传统应用是合适的,它旨在确保数据的“绝对正确”性,然而在实时数据库中,事务的定时限制往往比数据的“绝对正确”性更重要。为此,本文提出了新颖的准一致性可串行化的并发控制策略,文中着重讨论了准一致性可串行化的有关概念与理论,调度的可准一致性可串行化的判别方法,并发控制协议以及在事务的准一致性可串行化并发执行中不一致性传播放大的控制策略。     

Experimental Study of Concurrency Control Algorithms in Main-memory Database Systems

The concurrency control algorithm is a key approach for a database system to guarantee the correctness and efficiency of the transaction execution. Thus, substantial effort has been devoted to proposing new concurrency control algorithms in both the database industry and academia. In this paper, we take the lead in summarizing the fundamental ideas of concurrency control algorithms as ``ordering-and-verifying''. We then redescribe and sort out the existing concurrency control algorithms following the ordering-and-verifying paradigm. On the basis of extensive comparative experiments on an open-source main-memory distributed transaction testbed called 3TS, we systematically investigate the advantages and disadvantages of the mainstream concurrency control algorithms and finally summarize the preferable application scenario for each algorithm to provide valuable references for follow-up research on concurrency control algorithms used in main-memory databases.     

Applying semantic knowledge to real-time update of access control policies

Real-time update of access control policies, that is, updating policies while they are in effect and enforcing the changes immediately, is necessary for many security-critical applications. In this paper, we consider real-time update of access control policies in a database system. Updating policies while they are in effect can lead to potential security problems, such as, access to database objects by unauthorized users. In this paper, we propose several algorithms that not only prevent such security breaches but also ensure the correctness of execution. The algorithms differ from each other in the degree of concurrency provided and the semantic knowledge used. Of the algorithms presented, the most concurrency is achieved when transactions are decomposed into atomic steps. Once transactions are decomposed, the atomicity, consistency, and isolation properties no longer hold. Since the traditional transaction processing model can no longer be used to ensure the correctness of the execution, we use an alternate semantic-based transaction processing model. To ensure correct behavior, our model requires an application to satisfy a set of necessary properties, namely, semantic atomicity, consistent execution, sensitive transaction isolation, and policy-compliant. We show how one can verify an application statically to check for the existence of these properties.     

用不对称的P/V操作设计并发算法

多线程并发是提高系统性能的常用手段,文章提出了一种用信号量的不对称P/V操作来设计多线程并发算法的新思路,这种思路适合于设计多线程同步程序以解决某些具有复杂同步语义要求的问题,而这些问题用传统的方法很难得到简洁高效的求解。为了演示这种新思路的特点和优点,笔者对几个常见问题(读写锁、排队锁和记录锁)给出了新的算法设计以及实现。实验数据表明,采用这种思路设计的算法在算法复杂度,读写速度和资源使用方面相对于传统的算法存在较大优势。     

基于语义约束的资源工作流并发正确性保证

控制流结构中并发变迁的正确性是工作流模型正确性的基础．为保证模型的正确性，提出了资源语义约束工作流网的基本概念，丰富了控制流的数据语义，给出了两方面的控制流并发正确性：并发控制流与其数据语义的一致性检测算法及改正原则，保证了模型中的并发控制流结构的正确性；实例中基于数据语义约束的并发变迁正确性保证机制，提出了申请锁和释放锁的算法，保证了工作流实例中并发执行的正确性。     

Using refinement calculus techniques to prove linearizability

Stepwise refinement is a method for systematically transforming a high-level program into an efficiently executable one. A sequence of successively refined programs can also serve as a correctness proof, which makes different mechanisms in the program explicit. We present rules for refinement of multi-threaded shared-variable concurrent programs. We apply our rules to the problem of verifying linearizability of concurrent objects, that are accessed by an unbounded number of concurrent threads. Linearizability is an established correctness criterion for concurrent objects, which states that the effect of each method execution can be considered to occur atomically at some point in time between its invocation and response. We show how linearizability can be expressed in terms of our refinement relation, and present rules for establishing this refinement relation between programs by a sequence of local transformations of method bodies. Contributions include strengthenings of previous techniques for atomicity refinement, as well as an absorption rule, which is particularly suitable for reasoning about concurrent algorithms that implement atomic operations. We illustrate the application of the refinement rules by proving linearizability of Treiber’s concurrent stack algorithm and Michael and Scott’s concurrent queue algorithm.     

The effect of uncontrolled concurrency on model checking

Correctness of concurrent software is usually checked by techniques such as peer code reviews or code walkthroughs and testing. These techniques, however, are subject to human error, and thus do not achieve an in‐depth verification of correctness. Model‐checking techniques, which can systematically identify and verify every state that a system can enter, are a powerful alternative method for verifying concurrent systems. However, the usefulness of model checking is limited because the number of states for concurrent models grows exponentially with the number of processes in the system. This is often referred to as the ‘state explosion problem.’ Some processes are a central part of the software operation and must be included in the model. However, we have found that some exponential complexity results due to uncontrolled concurrency introduced by the programmer rather than due to the intrinsic characteristics of the software being modeled. We have performed tests on multimedia synchronization to show the effect of abstraction as well as uncontrolled concurrency using the Promela/SPIN model checker. We begin with a sequential model not expected to have exponential complexity but that results in exponential complexity. In this paper, we provide alternative designs and explain how uncontrolled concurrency can be removed from the code. Copyright © 2007 John Wiley & Sons, Ltd.     

网络中常用的队列管理方法比较

本文主要介绍了网络中常用的两种队列管理方法:先进先出(FIFO)和随机提前检测(RED),并且通过实验比较了这两种队列管理方法在解决网络拥塞控制方面的表现,体现了研究主动式队列管理方法的重要意义。     

Buffer management for lossless service in shared buffer switches

Fair scheduling and buffer management are two typical approaches to provide differentiated service. Fair scheduling algorithms usually need to keep a separate queue and maintain associated state variables for each incoming flow, which makes them difficult to operate and scale. On the contrary, buffer management (in conjunction with FIFO scheduling) needs only a constant amount of state information and processing, and can be efficiently implemented. In this paper, we consider using buffer management to provide lossless service for guaranteed performance flows in shared buffer switches. We study the buffer size requirement and buffer allocation strategies by starting with the single output switch and then extending the analytical results to the general multiple output switch. We present a universally applicable buffer allocation method for assuring lossless service, and validate the correctness of the theoretical results through simulations.     

Reasoning with geometric information in digital space

Concurrency requires consistency and correctness. Isothetic rectangles can be used as a geometrical technique to verify a safe and deadlock free schedule for concurrent nodes. However, the known algorithms for concurrency using isothetic rectangles require the prior knowledge of the system behavior. We provide a new mechanism to use isothetic rectangles without this limitation. The discrete nature of isothetic rectangles provides an opportunity for inter-diagrammatic reasoning. Inter-Diagrammatic Reasoning (IDR) can be easily computed on a parallel machine, and has a complexity of O(n) for most of the iso-rectangles problems where the best known algorithm was O(n log n) in Euclidean geometry. This new framework will also allow dynamic mode of operation in calculating the closure of a set of iso-rectangles; rather than restricting the solution to static systems where all required resources must be reserved in advance.     

A Causal Model for Analyzing Distributed Concurrency Control Algorithms

An event order based model for specifying and analyzing concurrency control algorithms for distributed database systems has been presented. An expanded notion of history that includes the database access events as well as synchronization events is used to study the correctness, degree of concurrency, and other aspects of the algorithms such as deadlocks and reliability. The algorithms are mapped into serializable classes that have been defined based on the order of synchronization events such as lock points, commit point, arrival of a transaction, etc,.     

Modular synchronization in distributed, multiversion databases:version control and concurrency control

A version control mechanism is proposed that enhances the modularity and extensibility of multiversion concurrency control algorithms. The multiversion algorithms are decoupled into two components: version control and concurrency control. This permits modular development of multiversion protocols and simplifies the task of proving the correctness of these protocols. A set of procedures for version control is described that defines the interface with the version control component. It is shown that the same interface can be used by the database actions of both two-phase locking and time-stamp concurrency control protocols to access multiversion data. An interesting feature of the framework is that the execution of read-only transactions becomes completely independent of the underlying concurrency control implementation. Unlike other multiversion algorithms, read-only transactions in this scheme do not modify any version-related information, and therefore do not interfere with the execution of read-write transactions. The extension of the multiversion algorithms to a distributed environment becomes very simple     

Mechanically verifying concurrent programs with the Boyer-Mooreprover

A proof system suitable for the mechanical verification of concurrent programs is described. This proof system is based on Unity, and may be used to specify and verify both safety and liveness properties. However, it is defined with respect to an operational semantics of the transition system model of concurrency. Proof rules are simply theorems of this operational semantics. This methodology makes a clear distinction between the theorems in the proof system and the logical inference rules and syntax which define the underlying logic. Since this proof system essentially encodes Unity in another sound logic, and this encoding has been mechanically verified, this encoding proves the soundness of this formalization of Unity. This proof system has been mechanically verified by the Boyer-Moore prover. This proof system has been used to mechanically verify the correctness of a distributed algorithm that computes the minimum node value in a tree     

The partitioned synchronization rule for planar extendible partialorders

The partitioned synchronization rule is a technique for proving the correctness of concurrency control algorithms. Prior work has shown the applicability of the partitioned synchronization rule to hierarchically decomposed databases whose structure is restricted to semitrees. The principal contribution of the paper is a demonstration that the partitioned synchronization rule also applies to more general structures than semitrees, specifically, to any planar extendible partial order, a partial order which when extended with a least and a greatest element still remains planar. To demonstrate utility, the paper presents two applications of the partitioned synchronization rule. The first application shows correctness of a component based timestamp generation algorithm suitable for implementing a timestamp ordering concurrency control algorithm. The second application shows correctness of a snapshot algorithm for concurrency control in a replicated multilevel secure database; we choose this application to highlight that hierarchically decomposed databases and multilevel secure databases are structurally similar. In both cases, the correctness proofs via the partitioned synchronization rule are substantially simpler than corresponding direct proofs     

Performance of B+ tree concurrency control algorithms

A number of algorithms have been proposed to access B⁺-trees concurrently, but they are not well understood. In this article, we study the performance of various B⁺-tree concurrency control algorithms using a detailed simulation model of B⁺-tree operations in a centralized DBMS. Our study covers a wide range of data contention situations and resource conditions. In addition, based on the performance of the set of B⁺-tree concurrency control algorithms, which includes one new algorithm, we make projections regarding the performance of other algorithms in the literature. Our results indicate that algorithms with updaters that lock-couple using exclusive locks perform poorly as compared to those that permit more optimistic index descents. In particular, the B-link algorithms are seen to provide the most concurrency and the best overall performance. Finally, we demonstrate the need for a highly concurrent long-term lock holding strategy to obtain the full benefits of a highly concurrent algorithm for index operations.