The Experts below are selected from a list of 113691 Experts worldwide ranked by ideXlab platform
P S Thiagarajan - One of the best experts on this subject based on the ideXlab platform.
-
a product version of dynamic linear time temporal logic
International Conference on Concurrency Theory, 1997Co-Authors: Jesper G Henriksen, P S ThiagarajanAbstract:We present here a linear time temporal logic which simultaneously extends LTL, the propositional temporal logic of linear time, along two dimensions. Firstly, the until operator is strengthened by indexing it with the regular Programs of propositional dynamic logic (PDL). Secondly, the core formulas of the logic are decorated with names of sequential agents drawn from fixed finite set. The resulting logic has a natural semantics in terms of the runs of a Distributed Program consisting of a finite set of sequential Programs that communicate by performing common actions together. We show that our logic, denoted DLTL⊗, admits an exponential time decision procedure. We also show that DLTL⊗ is expressively equivalent to the so called regular product languages. Roughly speaking, this class of languages is obtained by starting with synchronized products of (ω-)regular languages and closing under boolean operations. We also sketch how the behaviours captured by our temporal logic fit into the framework of labelled partial orders known as Mazurkiewicz traces.
-
a product version of dynamic linear time temporal logic
BRICS Report Series, 1997Co-Authors: Jesper G Henriksen, P S ThiagarajanAbstract:We present here a linear time temporal logic which simultaneously extends LTL, the propositional temporal logic of linear time, along two dimensions. Firstly, the until operator is strengthened by indexing it with the regular Programs of propositional dynamic logic (PDL). Secondly, the core formulas of the logic are decorated with names of sequential agents drawn from fixed finite set. The resulting logic has a natural semantics in terms of the runs of a Distributed Program consisting of a finite set of sequential Programs that communicate by performing common actions together. We show that our logic, denoted DLTL, admits an exponential time decision procedure. We also show that DLTL is expressively equivalent to the so called regular product languages.
Deng-jyi Chen - One of the best experts on this subject based on the ideXlab platform.
-
The Distributed Program reliability analysis on ring-type topologies
Computers & Operations Research, 2001Co-Authors: Min-sheng Lin, Ming-sang Chang, Deng-jyi ChenAbstract:Abstract Distributed computing system (DCS) has become very popular for its high fault-tolerance, potential for parallel processing, and better reliability performance. One of the important issues in the design of the DCS is the reliability performance. Distributed Program reliability (DPR) is addressed to obtain this reliability measure. In this paper, we propose a polynomial-time algorithm for computing the DPR of ring topology and show that solving the DPR problem on a ring of trees topology is NP-hard. Scope and purpose The widespread use of Distributed computing system is due to the price–performance revolution in microelectronics, the development of cost-effective and efficient communication subsets, the development of resource sharing software, and the increased user demands for communication, economical sharing of resources, and productivity. This article is concerned with the analysis of Distributed Program reliability on a ring-Distributed computing system. The Distributed Program reliability is a useful measure for reliability evaluation of Distributed computing system. The Distributed Program reliability analyses also give a good index for designing a high-reliability-performance-Distributed computing system.
-
The Distributed Program reliability analysis on star topologies
Computers & Operations Research, 2000Co-Authors: Ming-sang Chang, Deng-jyi Chen, Min-sheng LinAbstract:Abstract A Distributed computing system consists of processing elements, communication links, memory units, data files, and Programs. These resources are interconnected via a communication network and controlled by a Distributed operating system. The Distributed Program reliability in a Distributed computing system is the probability that a Program which runs on multiple processing elements and needs to retrieve data files from other processing elements will be executed successfully. This reliability varies according to (1) the topology of the Distributed computing system, (2) the reliability of the communication edges, (3) the data files and Programs distribution among processing elements, and (4) the data files required to execute a Program. In this paper, we show that computing the Distributed Program reliability on the star Distributed computing systems is NP-hard. We also develop an efficiently solvable case to compute Distributed Program reliability when some additional file distribution is restricted on the star topology. Scope and purpose Recent advances in VLSI circuitry have a tremendous impact on the price-performance revolution in microelectronics. This development has led to an increased use of workstations connected in the form of a powerful Distributed computing system. Potential benefits offered by such Distributed computing systems include better cost performance, enhanced fault tolerance, increased system throughput, and efficient sharing of resources. Distributed Program reliability is an important measure that should be examined for designing a high fault-tolerance Distributed computing system. This reliability varies according to (1) the topology of the Distributed computing system, (2) the reliability of the communication edges, (3) the data files and Programs distribution among processing elements, and (4) the data files required to execute a Program. This article is concerned with the analysis of Distributed Program reliability on star Distributed computing systems.
-
Distributed-Program reliability analysis: complexity and efficient algorithms
IEEE Transactions on Reliability, 1999Co-Authors: Min-sheng Lin, Ming-sang Chang, Deng-jyi ChenAbstract:This paper investigates the problem of Distributed-Program reliability in various classes of Distributed computing systems. This problem is computationally intractable for arbitrary Distributed computing systems, even when it is restricted to the class of star Distributed computing systems. One solvable case for star Distributed computing systems is identified, in which data files are Distributed with respective to a consecutive property; a polynomial-time algorithm is developed for this case. A linear-time algorithm is developed to test whether or not an arbitrary star Distributed computing system has this consecutive file distribution property. Efficient algorithms may still be sought for computing lower and upper bounds on the Distributed Program reliability for arbitrary Distributed computing systems.
-
The computational complexity of the reliability problem on Distributed systems
Information Processing Letters, 1997Co-Authors: Deng-jyi ChenAbstract:Abstract The reliability of a Distributed Program in a Distributed computing system is the probability that a Program which runs on multiple processing elements and needs to communicate with other processing elements for remote data files will be executed successfully. This reliability varies according to 1. (1) the topology of the Distributed computing system 2. (2) the reliability of the communication links 3. (3) the data files and Program distribution among processing elements and 4. (4) the data files required to execute a Program. This paper shows that solving this reliability problem is NP-hard even when the Distributed computing system is restricted to a series-parallel, a 2-tree, a tree, or a star structure.
-
a heuristic approach to generating file spanning trees for reliability analysis of Distributed computing systems
Computers & Mathematics With Applications, 1997Co-Authors: Deng-jyi Chen, Rueyshun Chen, Tienhsiang HuangAbstract:Abstract The reliability of Distributed Computing Systems (DCS) in terms of Distributed Program Reliability (DPR) and Distributed System Reliability (DSR) has been studied intensively. Current reliability algorithms available for the analysis of DPR and DSR include MFST, FARE, FST, and FST-SPR. This paper presents a reliability algorithm, called HRFST, that eliminates the need to search a spanning tree during each subgraph generation. The HRFST algorithm reduces both the number of subgraphs (or trees) generated and the actual execution time required for analysis of DPR and DSR. Examination of several sample cases shows that the HRFST algorithm is more efficient than the FST-SPR algorithm.
Jesper G Henriksen - One of the best experts on this subject based on the ideXlab platform.
-
a product version of dynamic linear time temporal logic
International Conference on Concurrency Theory, 1997Co-Authors: Jesper G Henriksen, P S ThiagarajanAbstract:We present here a linear time temporal logic which simultaneously extends LTL, the propositional temporal logic of linear time, along two dimensions. Firstly, the until operator is strengthened by indexing it with the regular Programs of propositional dynamic logic (PDL). Secondly, the core formulas of the logic are decorated with names of sequential agents drawn from fixed finite set. The resulting logic has a natural semantics in terms of the runs of a Distributed Program consisting of a finite set of sequential Programs that communicate by performing common actions together. We show that our logic, denoted DLTL⊗, admits an exponential time decision procedure. We also show that DLTL⊗ is expressively equivalent to the so called regular product languages. Roughly speaking, this class of languages is obtained by starting with synchronized products of (ω-)regular languages and closing under boolean operations. We also sketch how the behaviours captured by our temporal logic fit into the framework of labelled partial orders known as Mazurkiewicz traces.
-
a product version of dynamic linear time temporal logic
BRICS Report Series, 1997Co-Authors: Jesper G Henriksen, P S ThiagarajanAbstract:We present here a linear time temporal logic which simultaneously extends LTL, the propositional temporal logic of linear time, along two dimensions. Firstly, the until operator is strengthened by indexing it with the regular Programs of propositional dynamic logic (PDL). Secondly, the core formulas of the logic are decorated with names of sequential agents drawn from fixed finite set. The resulting logic has a natural semantics in terms of the runs of a Distributed Program consisting of a finite set of sequential Programs that communicate by performing common actions together. We show that our logic, denoted DLTL, admits an exponential time decision procedure. We also show that DLTL is expressively equivalent to the so called regular product languages.
B. Waldecker - One of the best experts on this subject based on the ideXlab platform.
-
Detection of strong unstable predicates in Distributed Programs
IEEE Transactions on Parallel and Distributed Systems, 1996Co-Authors: Vijay K. Garg, B. WaldeckerAbstract:This paper discusses detection of global predicates in a Distributed Program. A run of a Distributed Program results in a set of sequential traces, one for each process. These traces may be combined to form many global sequences consistent with the single run of the Program. A strong global predicate is true in a run if it is true for all global sequences consistent with the run. We present algorithms which detect if the given strong global predicate became true in a run of a Distributed Program. Our algorithms can be executed on line as well as off line. Moreover, our algorithms do not assume that underlying channels satisfy FIFO ordering.
-
FSTTCS - Detection of Unstable Predicates in Distributed Programs
Lecture Notes in Computer Science, 1992Co-Authors: Vijay K. Garg, B. WaldeckerAbstract:This paper discusses detection of global predicates in a Distributed Program. Earlier algorithms for detection of global predicates proposed by Chandy and Lamport work only for stable predicates. Our algorithms detect even unstable predicates without excessive overhead. The predicates are specified using a logic described formally in this paper. We require the predicates to be conjunction, disjunction or linking of local predicates. The message complexity of our algorithm is bounded by the number of messages used by the Program. The main application of our results are in debugging and testing of Distributed Programs. We have incorporated our algorithms in a Distributed debugger that runs on a cluster of Sun workstations.
-
Detection of unstable predicates in debugging Distributed Programs
1991Co-Authors: B. WaldeckerAbstract:This dissertation examines the problem of unstable predicate detection in Distributed Programs, which is an important aspect of debugging Distributed Programs. We address this problem for a loosely-coupled message-passing environment. The significance of this research lies in the fact that detection methods are given for Distributed predicates that may be unstable in nature. A Distributed predicate is one that depends on state information in different processes. A stable predicate is one which, once it becomes true, stays true forever. Stable predicates can be detected by checking periodically to see if they have become true, however this is not the case with unstable predicates. The predicates in this research are both Distributed and unstable and, in the past, such predicates have often been regarded as too difficult to detect. Previous work on Distributed Program debugging is reviewed and we show that none of the existing approaches satisfies our requirements for unstable predicate detection. These requirements are a taxonomy for unstable Distributed predicates, accurate detection methods, and feasible detection costs. We present a structured method of constructing predicates for a Distributed Program and identify what constructs can be detected. This is presented in the form of a predicate logic or grammar which gives the specific rewrite rules to be used in constructing various types of Distributed predicates. A restricted version of this logic is then given which characterizes those types of Distributed predicates that can be feasibly detected. Detection algorithms are given for those predicates in the restricted logic along with correctness proofs. Any predicate belonging to this restricted logic can be detected directly using the algorithms we provide. Further, any predicate which can be reduced to a set of predicates from this restricted logic is detectable. Finally, we give examples including mutual exclusion, leadership election, and database applications to illustrate the usefulness of such predicates. The algorithms presented have been implemented in C under Berkeley UNIX to further validate their correctness and practicality.
-
SPDP - Detection of strong predicates in Distributed Programs
Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, 1Co-Authors: B. Waldecker, Vijay K. GargAbstract:This paper discusses detection of unstable predicates in a Distributed Program. Some applications of this are in Program debugging and testing. The authors provide a predicate logic in the form of a grammar giving the rewrite rules for constructing predicates about a Distributed Program. This predicate logic is general enough to describe many conditions Programmers are interested in. These predicates may depend on the global state of the system and may be unstable in nature. However, the detection algorithms given guarantee to detect such predicates should one ever become true. The main results of this work are a logic for expressing unstable Distributed predicates and detection methods for certain unstable Distributed predicates. >
Marek Tudruj - One of the best experts on this subject based on the ideXlab platform.
-
Extremal Optimization applied to load balancing in execution of Distributed Programs
Applied Soft Computing, 2015Co-Authors: Ivanoe De Falco, Eryk Laskowski, Richard Olejnik, Umberto Scafuri, Ernesto Tarantino, Marek TudrujAbstract:The paper describes methods for using Extremal Optimization (EO) for processor load balancing during execution of Distributed applications. A load balancing algorithm for clusters of multicore processors is presented and discussed. In this algorithm the EO approach is used to periodically detect the best tasks as candidates for migration and for a guided selection of the best computing nodes to receive the migrating tasks. To decrease the complexity of selection for migration, the embedded EO algorithm assumes a two-step stochastic selection during the solution improvement based on two separate fitness functions. The functions are based on specific models which estimate relations between the Programs and the executive hardware. The proposed load balancing algorithm is assessed by experiments with simulated load balancing of Distributed Program graphs. The algorithm is compared against a greedy fully deterministic approach, a genetic algorithm and an EO-based algorithm with random placement of migrated tasks.
-
pegasus da framework for Distributed Program execution control based on application global states monitoring
Concurrency and Computation: Practice and Experience, 2015Co-Authors: Marek Tudruj, Janusz Borkowski, Damian Kopanski, Eryk Laskowski, łukasz Maśko, Adam SmykAbstract:The paper presents basic design decisions taken in the implementation of a novel Distributed Program design framework Program Execution Governed by Asynchronous SUpervision of States in Distributed Applications PEGASUS DA. This framework supports application Program execution control design based on evolved automated Program global states monitoring. The framework provides to a Programmer a ready-to-use infrastructure for defining and handling local and global application states to be used as the basis for Program execution control decisions. The paper presents how the provided infrastructure can be used for automated construction of strongly consistent application global states. Also, the use of global states for graphically supported specification of Distributed Program execution control is covered for clusters of multicore processors based on multithreading and message passing. Both architecture and implementation solutions applied for PEGASUS DA are discussed. Especially, multivariant algorithms for construction of Program strongly consistent global states and methods for their use in the design of Distributed Program global execution control are shown. The use of PEGASUS DA is illustrated with an example of a traveling salesman problem solved by the branch and bound method. Copyright © 2015 John Wiley & Sons, Ltd.
-
Parallel Extremal Optimization with Guided State Changes Applied to Load Balancing
Lecture Notes in Computer Science, 2015Co-Authors: Ivanoe De Falco, Eryk Laskowski, Richard Olejnik, Umberto Scafuri, Ernesto Tarantino, Marek TudrujAbstract:The paper concerns parallel methods for Extremal Optimization (EO) applied for processor load balancing for Distributed Programs. In these methods the EO approach is used which is parallelized and extended by a guided search of next solution state. EO detects the best strategy of tasks migration leading to a reduction in Program execution time. We assume a parallel improvement of the EO algorithm with guided state changes which provides a parallel search for a solution based on two step stochastic selection during the solution improvement based on two fitness functions. The load balancing improvements based on EO aim at better convergence of the algorithm and better quality of Program execution in terms of the execution time. The proposed load balancing algorithm is evaluated by experiments with simulated parallelized load balancing of Distributed Program graphs.
-
Improving Extremal Optimization in Load Balancing by Local Search
Lecture Notes in Computer Science, 2014Co-Authors: Ivanoe De Falco, Eryk Laskowski, Richard Olejnik, Umberto Scafuri, Ernesto Tarantino, Marek TudrujAbstract:The paper concerns the use of Extremal Optimization (EO) technique in dynamic load balancing for optimized execution of Distributed Programs. EO approach is used to periodically detect the best candidates for task migration leading to balanced execution. To improve the quality of load balancing and decrease time complexity of the algorithms, we have improved EO by a local search of the best computing node to receive migrating tasks. The improved guided EO algorithm assumes a two-step stochastic selection based on two separate fitness functions. The functions are based on specific Program models which estimate relations between the Programs and the executive hardware. The proposed load balancing algorithm is compared against a standard EO-based algorithm with random placement of migrated tasks and a classic genetic algorithm. The algorithm is assessed by experiments with simulated load balancing of Distributed Program graphs and analysis of the outcome of the discussed approaches.
-
Extremal Optimization with Guided State Changes in Load Balancing of Distributed Programs
IEEE Computer Society, 2014Co-Authors: Ivanoe De Falco, Eryk Laskowski, Richard Olejnik, Umberto Scafuri, Ernesto Tarantino, Marek TudrujAbstract:The paper concerns methods for using Extremal Optimization (EO) for processor load balancing during execution of Distributed Programs. A load balancing algorithm for clusters of multicore processors is presented and discussed. In this algorithm the EO approach is used to periodically detect the best tasks as candidates for migration and for a guided selection of the best processors to receive the migrated tasks. To decrease the complexity of selection for migration, we propose a guided EO algorithm which assumes a two step stochastic selection during the solution improvement based on two separate fitness functions. The functions are based on specific Program models which estimate relations between the Programs and the executive hardware. The proposed load balancing algorithm is assessed by experiments with simulated load balancing of Distributed Program graphs. The algorithm is compared against an EO - based algorithm with random placement of migrated tasks and a classic genetic algorithm.
