A fully distributed and symmetric algorithm is presented for solving the distributedtermination problem along with its correctness arguments. The algorithm does not employ time-stamps and clock-synchronization and i...
详细信息
A fully distributed and symmetric algorithm is presented for solving the distributedtermination problem along with its correctness arguments. The algorithm does not employ time-stamps and clock-synchronization and is very simple. In the detection phase, the local information in terms of keeping the status of neighbors of a process in its control section is automatically generated when basic communication occurs between the process and its neighbors. The probe-message, once issued from a process, develops around the ring in anti-clockwise direction and either reaches back its originating process, thereby determining the truth of the distributedtermination condition, or gets purged on its way on encountering either an active process or a passive process with at least one of its neighbors in active state. A process gets terminated only after it has received and forwarded a termination message sent by a process or processes.
A multiple inheritance mechanism on processes is designed and presented within the framework of a small object oriented language. Processes are described in classes, and the different action parts of a process inherit...
详细信息
A multiple inheritance mechanism on processes is designed and presented within the framework of a small object oriented language. Processes are described in classes, and the different action parts of a process inherited from different classes are executed in a coroutine-like style called alternation. The inheritance mechanism is a useful tool for factorizing the description of common aspects of processes. This is demonstrated within the domain of distributed programming by using the inheritance mechanism to factorize the description of distributed termination detection algorithms from the description of the distributed main computations for which termination is to be detected. A clear separation of concerns is obtained, and arbitrary combinations of terminationdetection algorithms and main computations can be formed. The same terminationdetection classes can also be used for more general purposes within distributed programming, such as detecting termination of each phase in a multi-phase main computation.
distributed termination detection (DTD) algorithms are important since they detect globally stable states in distributed computations. Here we introduce a new DTD mechanism, the Doomsday protocol together with its pro...
详细信息
distributed termination detection (DTD) algorithms are important since they detect globally stable states in distributed computations. Here we introduce a new DTD mechanism, the Doomsday protocol together with its proof of correctness. Doomsday is generic since it forms the basis for a number of new and existing DTD algorithms for which the correctness proof may be reused. The paper describes the Doomsday protocol, provides its formal proof, derives one new DTD algorithm and shows how other hitherto unrelated algorithms, Dijkstra-Scholten, Task Balancing and Credit Recovery, can be derived from the protocol. The paper concludes by examining various properties of the protocol in the context of existing DTD algorithms.
Compact Local Integrated Radial Basis Function (CLIRBF) methods based on Cartesian grids can be effective numerical methods for solving partial differential equations (PDEs) for fluid flow problems. The combination of...
详细信息
Compact Local Integrated Radial Basis Function (CLIRBF) methods based on Cartesian grids can be effective numerical methods for solving partial differential equations (PDEs) for fluid flow problems. The combination of the domain decomposition method and function approximation using CLIRBF methods yields an effective coarse-grained parallel processing approach. This approach has enabled not only each sub-domain in the original analysis domain to be discretised by a separate CLIRBF network but also compact local stencils to be independently treated. The present algorithm, namely parallel CLIRBF, achieves higher throughput in solving large scale problems by, firstly, parallel processing of sub-regions which constitute the original domain and, secondly, accelerating the convergence rate within each sub-region using groups of CLIRBF stencils in which function approximations are carried out by parallel processes. The procedure is illustrated with several numerical examples of PDEs and lid-driven cavity problem using Message Passing Interface supported by MATLAB.
It is shown that the terminationdetection problem for distributed computations can be modeled as an instance of the garbage collection problem. Consequently, algorithms for the terminationdetection problem are obtai...
详细信息
It is shown that the terminationdetection problem for distributed computations can be modeled as an instance of the garbage collection problem. Consequently, algorithms for the terminationdetection problem are obtained by applying transformations to garbage collection algorithms. The transformation can be applied to collectors of the ''mark-and-sweep'' type as well as to reference-counting garbage collectors. As examples, the scheme is used to transform the distributed reference-counting protocol of Lermen and Maurer, the weighted-reference-counting protocol, the local-reference-counting protocol, and Ben-Ari's mark-and-sweep collector into terminationdetection algorithms. Known termination-detection algorithms as well as new variants are obtained.
This article studies characteristic properties of synchronous and asynchronous message communications in distributed systems. Based on the causality relation between events in computations with asynchronous communicat...
详细信息
This article studies characteristic properties of synchronous and asynchronous message communications in distributed systems. Based on the causality relation between events in computations with asynchronous communications, we characterize computations which are realizable with synchronous communications, which respect causal order, or where messages between two processes are always received in the order sent. It is shown that the corresponding computation classes form a strict hierarchy. Furthermore, an axiomatic definition of distributed computations with synchronous communications is given, and it is shown that several informal characterizations of such computations are equivalent when they are formalized appropriately. As an application, we use our results to show that the distributed termination detection algorithm by Dijkstra et al. is correct under a weaker synchrony assumption than originally stated.
Current multi-agent systems (MASs) don't include the detection of their termination. Without such detection, the MAS will be either incomplete or incoherent. It is incomplete if it is a MAS lacking the detection o...
详细信息
ISBN:
(纸本)9783319136479;9783319136462
Current multi-agent systems (MASs) don't include the detection of their termination. Without such detection, the MAS will be either incomplete or incoherent. It is incomplete if it is a MAS lacking the detection of its termination. It is incoherent if it is other kind of systems than a MAS even if it terminates correctly. The problem of terminationdetection is borrowed from distributed systems where several solutions are proposed and/or improved. However, few works deal with this problem in the MAS context. In such context, the proposed solutions don't meet MASs requirements. This paper proposes MAS-td approach to the problem of terminationdetection in the MAS context. MAS-td improves the probe algorithm and meets the MASs requirements.
暂无评论