检索结果-内蒙古大学图书馆

Verifying mutual exclusion algorithms with Non-Atomic Registers

algorithms 2024年第12期17卷 536-536页

作者： Nigro, Libero Univ Calabria DIMES I-87036 Arcavacata Di Rende Italy

The work described in this paper develops a formal method for modeling and exhaustive verification of mutual exclusion algorithms. The process is based on timed automata and the Uppaal model checker. The technique was successfully applied to several mutual exclusion algorithms, mainly under the atomic memory model, when the read and write operations on memory cells (registers) are atomic or indivisible. The original contribution of this paper consists of a generalization of the approach to support modeling mutual exclusion algorithms with non-atomic registers, where multiple read operations can occur on a register simultaneously to a write operation on the same register, thus giving rise to the flickering phenomenon or multiple write operations can occur at the same time on the same register, hence determining the scrambling phenomenon. The paper first clarifies some consistency rules of non-atomic registers. Then, the developed Uppaal-based method for specifying and verifying mutual exclusion algorithms is presented. The method is applied to the correctness assessment of a sample mutual exclusion solution. After that, non-atomic register consistency rules are rendered in Uppaal to be embedded in the specification methodology. The paper goes on by presenting different mutual exclusion algorithms that are studied using non-atomic registers. algorithms are also investigated in the context of a tournament tree organization that can provide standard and efficient mutual exclusion solutions for N>2 processes. The paper compares the proposed techniques for handling non-atomic registers and reports about their application to many other mutual exclusion solutions.

关键词： mutual exclusion algorithms model checking atomic registers non-atomic registers flickering scrambling timed automata Uppaal

来源：评论

学校读者我要写书评

暂无评论

Modelling and Verification of mutual exclusion algorithms 16

Modelling and Verification of Mutual Exclusion Algorithms

引用

20th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications (DS-RT)

作者： Cicirelli, Franco Nigro, Libero CNR Natl Res Council Italy Inst High Performance Comp & Networking ICAR I-87036 Arcavacata Di Rende CS Italy Univ Calabria Dept Informat Modelling Elect & Syst Sci DIMES Arcavacata Di Rende CS Italy

ISBN: (纸本)9781509035052

This paper proposes modelling and exhaustive verification of mutual exclusion algorithms using timed automata (TA) and the popular UPPAAL toolbox. The proposal allows to check all the properties of a mutual exclusion algorithm also along the time dimension. Both the classic case of atomic read/write operations on memory cells and the non determinism of reading a memory cell during one or multiple write operations on it as it may occur in modern multi-port memories are considered. The approach is then applied to some algorithms proposed in the literature of which known properties are confirmed but also new ones are revealed.

关键词： mutual exclusion algorithms atomic vs. non atomic read/write operations timed automata model checking UPPAAL

来源：评论

学校读者我要写书评

暂无评论

Model Checking mutual exclusion algorithms Using UPPAAL 1

引用

5th Computer Science On-line Conference (CSOC)

作者： Cicirelli, Franco Nigro, Libero Sciammarella, Paolo F. Univ Calabria Dept Informat Modelling Elect & Syst Sci DIMES Arcavacata Di Rende CS Italy

ISBN: (数字)9783319336220

ISBN: (纸本)9783319336220;9783319336206

This paper proposes an approach to modelling and exhaustive verification of mutual exclusion algorithms which is based on Timed Automata in the context of the popular UPPAAL toolbox. The approach makes it possible to study the properties of a mutual exclusion algorithm also in the presence of the time dimension. For demonstration purposes some historical algorithms are modelled and thoroughly analyzed, going beyond some informal reasoning reported in the literature. The paper also proposes a mutual exclusion algorithm for N >= 2 processes whose model checking confirms it satisfies all the required properties.

关键词： mutual exclusion algorithms Model checking Timed automata UPPAAL

来源：评论

学校读者我要写书评

暂无评论

Formalization of mutual exclusion algorithms in N-labeled Calculus 7

Formalization of Mutual Exclusion Algorithms in <i>N</i>-lab...

引用

IEEE 7th Joint International Information Technology and Artificial Intelligence Conference (ITAIC)

作者： Mizutani, Tetsuya Tomita, Kohji Univ Tsukuba Fac Engn Informat & Syst Tsukuba Ibaraki Japan AIST Intelligent Syst Res Inst Tsukuba Ibaraki Japan

ISBN: (纸本)9781479944194

A family of formal systems called "labeled calculi" have been investigated lately for verification and analysis of time-concerned cooperating program systems. These calculi have high formality since they are based on the Peano arithmetic, one of the natural number theories. They are axiom-and proof-based approaches, i.e. properties of systems are verified by formal proofs. These approaches are more rigid and precise than that of model-checking. Among the labeled calculi, N-labeled calculus is the simplest and suited for usual time-concerned programs such as mutual exclusion. mutual exclusion algorithms are indispensable for contemporary programs having parallel tasks/jobs/processes, and they offer typical examples of verification of such time-concerned cooperating programs. In this article, two mutual exclusion algorithms are formally represented in the calculus for verification.

关键词： mutual exclusion algorithms Formalism N-labeled calculus

来源：评论

学校读者我要写书评

暂无评论

Formalization of mutual exclusion algorithms in N-labeled Calculus

Formalization of Mutual Exclusion Algorithms in N-labeled Ca...

引用

2014 IEEE 7th Joint International Information Technology and Artificial Intelligence Conference

作者： Tetsuya Mizutani Kohji Tomita Faculty of Engineering Information and SystemsUniversity of Tsukuba Intelligent Systems Research Institute AIST

A family of formal systems called "labeled calculi"have been investigated lately for verification and analysis of timeconcerned cooperating program systems. These calculi have high formality since they are based on the Peano arithmetic, one of the natural number theories. They are axiom- and proof-based approaches, i.e. properties of systems are verified by formal *** approaches are more rigid and precise than that of modelchecking. Among the labeled calculi, N-labeled calculus is the simplest and suited for usual time-concerned programs such as mutual exclusion. mutual exclusion algorithms are indispensable for contemporary programs having parallel tasks/jobs/processes,and they offer typical examples of verification of such timeconcerned cooperating programs. In this article, two mutual exclusion algorithms are formally represented in the calculus for verification.

关键词： mutual exclusion algorithms Formalism N-labeled calculus

来源：评论

学校读者我要写书评

暂无评论

Verification of mutual exclusion algorithms with SMV System 2

Verification of mutual exclusion algorithms with SMV System

引用

International Conference on Computer as a Tool

作者： Bogunovic, N Pek, E Fac Elect & Comp Engn Zagreb Croatia

ISBN: (纸本)078037763X

mutual exclusion algorithms can exhibit intricate behavior for which correctness can be hard to establish. We demonstrate automatic verification of five algorithms by symbolic model checking. We used SMV too I which enables property specification in computation tree logic and allow us to impose fairness constraints on a model. For each of the algorithm we verify safety, liveness, non-blocking and no strict ordering properties.

关键词： formal verification model checking mutual exclusion algorithms CTL SMV

来源：评论

学校读者我要写书评

暂无评论

Transversal merge operation: A nondominated coterie construction method for distributed mutual exclusion

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2005年第2期16卷 183-192页

作者： Harada, T Yamashita, M Hiroshima Univ Grad Sch Management Naka Ku Hiroshima 7300053 Japan Kyushu Univ Dept Comp Sci & Commun Engn Higashi Ku Fukuoka 8128581 Japan

A coterie is a set of subsets (called quorums) of the processes in a distributed system such that any two quorums intersect with each other and is mainly used to solve the mutual exclusion problem in a quorum-based algorithm. The choice of a coterie sensitively affects the performance of the algorithm and it is known that nondominated (ND) coteries achieve good performance in terms of criteria such as availability and load. On the other hand, grid coteries have some other attractive features: 1) A quorum size is small, which implies a low message complexity, and 2) a quorum is constructible on the fly, which benefits a low space complexity. However, they are not ND coteries unfortunately. To construct ND coteries having the favorite features of grid coteries, we introduce the transversal merge operation that transforms a dominated coterie into an ND coterie and apply it to grid coteries. We call the constructed ND coteries ND grid coteries. These ND grid coteries have availability higher than the original ones, inheriting the above desirable features from them. To demonstrate this fact, we then investigate their quorum size, load, and availability, and propose a dynamic quorum construction algorithm for an ND grid coterie.

关键词： coteries distributed systems grid structures mutual exclusion algorithms nondominatedness quorum consensus transversals

来源：评论

学校读者我要写书评

暂无评论

Performance measure sensitive congruences for Markovian process algebras

引用

THEORETICAL COMPUTER SCIENCE 2003年第1期290卷 117-160页

作者： Bernardo, M Bravetti, M Univ Turin Dipartimento Informat I-10149 Turin Italy Univ Bologna Dipartimento Sci Informaz I-40127 Bologna Italy

The modeling and analysis experience with process algebras has shown the necessity of extending them with priority, probabilistic internal/external choice, and time while preserving compositionality. The purpose of this paper is to make a further step by introducing a way to express performance measures, in order to allow the modeler to capture the QoS metrics of interest. We show that the standard technique of expressing stationary and transient performance measures as weighted sums of state probabilities and transition frequencies can be imported in the process algebra framework. Technically speaking, if we denote by n is an element of N the number of performance measures of interest, in this paper we define a family of extended Markovian process algebras with generative master-reactive slaves synchronization mechanism called EMPA(grn) including probabilities, priorities, exponentially distributed durations, and sequences of rewards of length n. Then we show that the Markovian bisimulation equivalence similar to(MBn) is a congruence for EMPA(grn) which preserves the specified performance measures and we give a sound and complete axiomatization for finite EMPA(grn) terms. Finally, we present a case study conducted with the software tool TwoTowers in which we contrast the average performance of a selection of distributed algorithms for mutual exclusion modeled with EMPA(grn). (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： process algebras performance evaluation Markov chains rewards mutual exclusion algorithms

来源：评论

学校读者我要写书评

暂无评论

Evaluating and designing software mutual exclusion algorithms on shared-memory multiprocessors

引用

IEEE PARALLEL & DISTRIBUTED TECHNOLOGY 1996年第1期4卷 25-42页

作者： Zhang, XD Yan, Y Castaneda, R High-Performance Computing and Software Laboratory University of Texas San Antonio USA

Performance evaluations of software-based mutual exclusion algorithms must take into account the effects of architectures and systems. The authors demonstrate ate a framework for such evaluation, and use the framework... 详细信息

关键词： Cache Coherence Memory Hierarchy mutual exclusion algorithms Performance Evaluation And Shared Memory Multiprocessor Systems

来源：评论

学校读者我要写书评

暂无评论

ON THE EQUITY OF mutual exclusion algorithms IN DISTRIBUTED SYSTEMS

引用

INFORMATION PROCESSING LETTERS 1995年第1期56卷 19-22页

作者： GREENWOOD, GW Department of Electrical and Computer Engineering Western Michigan University Kalamazoo MI 49008 USA

In recent years the problem of mutual exclusion in distributed systems has received much attention. The basic problem is to ensure that one and only one site has access to a critical section at any given time. It is suggested that a priority based approach to site selection in token-based mutual exclusion algorithms is better than selection criteria based solely upon timestamps or counters. Sites needing frequent access to a critical section should not spend an inordinate amount of time blocked for sites needing fewer accesses. The overall schedule length of the distributed computation should improve if the sites needing many accesses to a critical section are more unlikely to be blocked.

关键词： DISTRIBUTED SYSTEMS mutual exclusion algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：