The formalization and analysis of a communications protocol

The MSMIE protocol [SBC89] allows processors in a distributed system to communicate via shared memory. It was designed to meet the reliability and efficiency needs of applications such as nuclear safety systems. We present a formal model of the MSMIE protocol expressed in the notation CCS. Desirable properties of the protocol are expressed in the modal mu-calculus, an expressive modal logic. We show that the protocol lacks an important liveness property. In actual operation, additional operating constraints are checked to avoid potential problems. We present a modified protocol and show that it possesses the liveness property even without checking operating constraints. We also show how parts of the analysis were automated with the Concurrency Workbench.     

New and used temporal models: An issue of time

TheSpecial Issue on Applications of Temporal Models raises many issues of time: What are the important properties of time? How can time be best represented? How can one reason about time-dependent properties? What are the important directions of temporal research? This introductory piece very briefly surveys the current wide variety of temporal models, temporal reasoning methods, and applications to time-varying phenomena. Promising areas of investigation such as the verification of concurrent systems, knowledge-base representation methods, and dealing with theFrame Problem pass in fleeting review. Brief introductions to each of the works in the volume close the section.     

Parallel branch-and-bound search in Parlog

The concurrent logic languages, of which Parlog is one, have been promoted as a new generation of software languages specifically designed for parallel programming. This paper investigates their application to a search problem commonly used as an illustration of artificial intelligence techniques, the 8-puzzle. It notes that programs written in the concurrent logic languages which do not pay attention to the parallelism can fall into two possible traps: either there is little real parallelism in them due to data dependencies, or there is too much parallelism and any practical architecture will be overwhelmed. A solution which controls the parallelism using user-defined priorities is proposed. This solution has the advantage of being architecture-independent.     

What is a free name in a process algebra?

There are two popular approaches to specifying the semantics of process algebras: labelled transition semantics and reaction semantics. While the notion of free name is rather unproblematic for labelled transition semantics this is not so for reaction semantics in the presence of a structural congruence for unfolding recursive declarations.We show that the standard definition of free name is not preserved under the structural congruence. We then develop a fixed point approach to the set of free names and show that it is invariant under the structural congruence.     

适用于实时协同编著系统的并发控制研究

实时协同编著系统是最受欢迎的实时ＣＳＣＷ应用系统之一，适用于实时协同编著系统的并发控制用于解决参与协同工作用户对共享对象操作时存在的冲突问题。本文对这种新的并发控制与适用于分布式数据库系统等的传统并发控制进行了比较，讨论了一些适用于实时协同编著系统并发控制方法的新评价参数，分析了传统并发控制方法应用到实时协同编著系统时所遇到的问题。最后，我们介绍了一些文献中已有原型系统所使用的并发控制方法。     

Local and global deadlock-detection in component-based systems are NP-hard

Interaction systems are a formal model for component-based systems. Combining components via connectors to form more complex systems may give rise to deadlock situations. We present here a polynomial time reduction from 3-SAT to the question whether an interaction system contains deadlocks.     

An exercise in structural congruence

Milner's structural congruence is decidable for the pi-calculus without restriction, in exponential space.     

A survey of support for structured communication in concurrency control models

The two standard models used for communication in concurrent programs, shared memory and message passing, have been the focus of much debate for a long time. Still, we believe the main issue at stake should not be the choice between these models, but rather how to ensure that communication is structured, i.e., it occurs only in syntactically restricted code regions. In this survey, we explore concurrency control models and evaluate how their characteristics contribute positively or negatively to the support for structured communication. We focus the evaluation on three properties: reasonability, which is the main property we are interested in and determines how easily programmers can reason about a concurrent program’s execution; performance, which determines whether there are any distinct features which can prevent or facilitate efficient implementations; and composability, which determines whether a model offers constructs that can be used as building blocks for coarser-grained, or higher-level, concurrency abstractions.     

操作系统多任务应用模式实验开发

多个任务的并发执行是计算机操作系统的一个主要特征,为了满足Windows下分时多任务,或实时多任务应用系统的开发,给出通过C程序设计对操作系统中多任务并发执行设计模式开发,提出Windows下利用时钟中断方式进行多任务并发执行的方法。该模式实现系统内多任务在宏观上的"同时"运行,解决Windows环境下用户应用开发自己的分时,或实时多任务应用系统的一般方法和结构。