Spelling suggestions: "subject:"concurrence""
51 |
Nash equilibria in concurrent games : application to timed gamesBrenguier, Romain 29 November 2012 (has links) (PDF)
This work focuses on the study of concurrent and timed games. These two classes of games have been useful models in controller synthesis. In situations where several agents interact, the notion of winning strategies used so far is not adapted and it is necessary to adopt concepts from game theory. The main concept considered in this area is that of Nash equilibrium. For concurrent games, we propose a transformation which draw a parallel between equilibria and winning strategies. Many works have focused on the computation of winning strategies and we can take advantage of the available algorithms. To compute equilibria in timed games we show that it is possible to reduce them to concurrent games. We propose algorithms for the computation of equilibria, first with classical objectives. Then, we propose a more general framework, in which more quantitative preferences can be described. We also study the theoretical complexity of the associated decision problems. Finally, we present a tool that implements one of the algorithms that we developed.
|
52 |
Generation of Concurrency Controls using Discrete-Event SystemsDragert, Christopher 27 September 2008 (has links)
The development of controls for the execution of concurrent code is non-trivial. This work shows how existing discrete-event system (DES) theory can be successfully applied to this problem. From code without concurrency controls and a specification of desired behaviours, a DES representation of the problem is obtained, and then used to generate concurrency control code. By applying rigorously proven DES theory, the resulting code comes with guarantees not present in similar works. All control schemes generated in DES are nonblocking, yielding code that is free of both livelock and deadlock. Additionally, the generated control scheme is minimally restrictive, meaning only problematic behaviours are prevented.
If the specifications cannot be enforced as presented, the largest controllable subset is instead enforced. The result, which requires no further interaction to generate, is the best possible control scheme given the interaction between the specifications and the original code. Existing methods encounter difficulties when faced with multiple specifications that interact to form deadlocks. Modular DES theory is successfully applied, allowing resolution of these conflicts without requiring the user to introduce new specifications. Moreover, the approach is independent of specific programming or specification languages. A Java implementation is given, along with two problems showing the process in action. / Thesis (Master, Computing) -- Queen's University, 2008-09-25 09:03:51.593
|
53 |
SCOPE: Scalable Clustered Objects with Portable EventsMatthews, Christopher 27 September 2006 (has links)
Writing truly concurrent software is hard, scaling software to fully utilize hardware is
one of the reasons why. One abstraction for increasing the scalability of systems software is clustered objects. Clustered objects is a proven method of increasing scalability.
This thesis explores a user-level abstraction based on clustered objects which increases
hardware utilization without requiring any customization of the underlying system. We
detail the design, implementation and testing of Scalable Clustered Objects with Portable
Events or (SCOPE), a user-level system inspired by an implementation of the clustered objects model from IBM Research’s K42 operating system. To aid in the portability of the new system, we introduce the idea of a clustered object event, which is responsible for maintaining the runtime environment of the clustered objects. We show that SCOPE can increase scalability on a simple micro benchmark, and provide most of the benefits that the kernel-level implementation provided.
|
54 |
Virtual files : a framework for experimental designRoss, George D. M. January 1983 (has links)
The increasing power and decreasing cost of computers has resulted in them being applied in an ever widening area. In the world of Computer Aided Design it is now practicable to involve the machine in the earlier stages where a design is still speculative, as well as in the later stages where the computer's calculating ability becomes paramount. Research on database systems has not followed this trend, concentrating instead on commercial applications, with the result that there are very few systems targeted at the early stages of the design process. In this thesis we consider the design and implementation of the file manager for such a system, first of all from the point of view of a single designer working on an entire design, and then from the point of view of a team of designers, each working on a separate aspect of a design. We consider the functionality required of the type of system we are proposing, defining the terminology of experiments to describe it. Having ascertained our requirements we survey current database technology in order to determine to what extent it meets our requirements. We consider traditional concurrency control methods and conclude that they are incompatible with our requirements. We consider current data models and conclude that, with the exception of the persistent programming model, they are not appropriate in the context required, while the implementation of the persistent programming model provides transactions on data structures but not experiments. The implementation of experiments is considered. We examine a number of potential methods, deciding on differential files as the one most likely both to meet our requirements and to have the lowest overheads. Measurements conducted on both a preliminary and a full-scale implementation confirm that this is the case. There are, nevertheless, further gains in convenience and performance to be obtained by exploiting the capabilities of the hardware to the full; we discuss these in relation to virtual memory systems, with particular reference to the VAX/VMS environment. Turning to the case where several designers are each working on a (nearly) distinct part of a design, we consider how to detect conflicts between experiments. Basing our approach on optimistic concurrency control methods, we show how read and write sets may be used to determine those areas of the database where conflicts might arise. As an aside, we show how the methods we propose can be used in an alternative approach to optimistic concurrency control, giving a reduction in system overheads for certain applications. We consider implementation techniques, concluding that a differential files approach has significant advantages in maintaining write sets, while a two-level bitmap may be used to maintain read sets efficiently.
|
55 |
Advanced Concepts in Asynchronous Exception HandlingKrischer, Roy January 2010 (has links)
Asynchronous exception handling is a useful and sometimes necessary alternative form of communication among threads. This thesis examines and classifies general concepts related to asynchrony, asynchronous propagation control, and how asynchronous exception handling affects control flow. The work covers four advanced topics affecting asynchronous exception-handling in a multi-threaded environment.
The first topic is concerned with the non-determinism that asynchronous exceptions introduce into a program's control-flow because exceptions can be
propagated at virtually any point during execution. The concept of asynchronous propagation control, which restricts the set of exceptions that can be propagated, is examined in depth. Combining it with a restriction of asynchrony that permits propagation of asynchronous exceptions only at certain well-defined (poll) points can re-establish sufficient determinism to verify a program's correctness, but introduces overhead, as well as a delay between the delivery of an asynchronous exception and its propagation. It also disturbs a programmer's intuition about asynchronous propagation in the program, and requires the use of programming idioms to avoid errors.
The second topic demonstrates how a combined model of full and restricted asynchrony can be safely employed, and thus, allow for a more intuitive use of asynchronous propagation control, as well as potentially improve performance.
The third topic focuses on the delay of propagation that is introduced when a thread is blocked, i.e., on concurrency constructs that provide mutual exclusion or synchronization. An approach is presented to transparently unblock threads so propagation of asynchronous termination and resumption
exceptions can begin immediately. The approach does not require additional syntax, simplifies certain programming situations, and can improve performance.
The fourth topic explores usability issues affecting the understanding of (asynchronous) exception handling as a language feature.
To overcome these issues, tools and language features are presented that help in understanding exception handling code by providing additional run-time information, as well as assist in testing.
For all topics, the necessary extensions to the syntax/semantics of the
language are discussed; where applicable, a prototypical implementation is presented, with examples that demonstrate the benefits of the new approaches.
|
56 |
Asynchronous Backup and Initialization of a Database Server for Replicated Database SystemsBhalla, Subhash, Madnick, Stuart E. 14 April 2003 (has links)
A possibility of a temporary disconnection of database service exists in many computing environments. It is a common need to permit a participating site to lag behind and re-initialize to full recovery. It is also necessary that active transactions view a globally consistent system state for ongoing operations. We present an algorithm for on-the-fly backup and site-initialization. The technique is non-blocking in the sense that failure and recovery procedures do not interfere with ordinary transactions. As a result the system can tolerate disconnection of services and reconnection of disconnected services, without incurring high overheads
|
57 |
A Distributed Component-based Software Framework for Laboratory Automation SystemsJanuary 2012 (has links)
abstract: Laboratory automation systems have seen a lot of technological advances in recent times. As a result, the software that is written for them are becoming increasingly sophisticated. Existing software architectures and standards are targeted to a wider domain of software development and need to be customized in order to use them for developing software for laboratory automation systems. This thesis proposes an architecture that is based on existing software architectural paradigms and is specifically tailored to developing software for a laboratory automation system. The architecture is based on fairly autonomous software components that can be distributed across multiple computers. The components in the architecture make use of asynchronous communication methodologies that are facilitated by passing messages between one another. The architecture can be used to develop software that is distributed, responsive and thread-safe. The thesis also proposes a framework that has been developed to implement the ideas proposed by the architecture. The framework is used to develop software that is scalable, distributed, responsive and thread-safe. The framework currently has components to control very commonly used laboratory automation devices such as mechanical stages, cameras, and also to do common laboratory automation functionalities such as imaging. / Dissertation/Thesis / Thesis Presentation / M.S. Computer Science 2012
|
58 |
Spatially Induced Independence and Concurrency within Presheaves of Labelled Transition SystemsFortier-Garceau, Simon January 2015 (has links)
In this thesis, we demonstrate how presheaves of labelled transition systems (LTS) acquire a very natural form of spatially induced independence on their actions when we allow a minimal amount of gluing on selected transitions within such systems. This gluing condition is characterized in the new model of LTS-adapted presheaf, and we also make use of the new model of asynchronous labelled transition system with equivalence (ALTSE) to characterize independence on actions. As such, our main result, the Theorem of Spatially Induced Independence, establishes functors from the categories of LTS-adapted presheaves to the categories of ALTSE-valued presheaves; it is a result that extends a proposition of Malcolm [SSTS] in the context of LTS-valued sheaves on complete Heyting algebras.
|
59 |
Factorisation des régions cubiques et application à la concurrence / Factorization of cubical area and application to concurrencyNinin, Nicolas 11 December 2017 (has links)
Cette thèse se propose d'étudier des problèmes de factorisations des régions cubiques. Dans le cadre de l'analyse de programme concurrent via des méthodes issues de la topologie algébrique, les régions cubiques sont un modèle géométrique simple mais expressif de la concurrence. Tout programme concurrent (sans boucle ni branchement) est ainsi représenté comme sous partie de R^n auquel on enlève des cubes interdits représentant les états du programme interdit par les contraintes de la concurrence (mutex par exemple) où n est le nombre de processus. La première partie de cette thèse s’intéresse à la question d'indépendance des processus. Cette question est cruciale dans l'analyse de programme non concurrent car elle permet de simplifier l'analyse en séparant le programme en groupe de processus indépendants. Dans le modèle géométrique d'un programme, l'indépendance se traduit comme une factorisation modulo permutation des processus. Ainsi le but de cette section est de donner un algorithme effectif de factorisation des régions cubiques et de le démontrer. L'algorithme donné est relativement simple et généralise l'algorithme très intuitif suivant (dit algorithme syntaxique). A partir du programme, on met dans un même groupe les processus qui partagent une ressource, puis l’on prend la clôture transitive de cette relation. Le nouvel algorithme s'effectue de la même manière, cependant il supprime certaines de ces relations. En effet par des jeux d'inclusion entre cubes interdits, il est possible d'avoir deux processus qui partagent une ressource mais qui sont toutefois indépendant. Ainsi la nouvelle relation est obtenue en regardant l'ensemble des cubes maximaux de la région interdite. Lorsque deux coordonnées sont différentes de R dans un cube maximal on dira qu’elles sont reliées. Il suffit alors de faire la clôture transitive de cette relation pour obtenir la factorisation optimale. La seconde partie de ce manuscrit s'intéresse à un invariant catégorique que l'on peut définir sur une région cubique. Celui-ci découpe la région cubique en cubes appelés "dés" auxquels on associe une catégorie appelée catégorie émincée de la région cubique. On peut voir cette catégorie comme un intermédiaire fini entre la catégorie des composantes et la catégorie fondamentale. On peut ainsi montrer que lorsque la région cubique factorise alors la catégorie émincée associée va elle-même se factoriser. Cependant la réciproque est plus compliquée et de nombreux contre exemples empêchent une réciproque totale. La troisième et dernière partie de cette thèse s'intéresse à la structure de produit tensoriel que l'on peut mettre sur les régions cubiques. En remarquant comment les opérations booléennes sur une région cubique peuvent être obtenues à partir des opérations sur les régions cubiques de dimension inférieure, on tente de voir ces régions cubiques comme un produit tensoriel des régions de dimension inférieure. La structure de produit tensoriel est hautement dépendante de la catégorie dans laquelle on la considère. Dans ce cas, si l'on considère le produit dans les algèbres de Boole, le résultat n'est pas celui souhaité. Au final il se trouve que le produit tensoriel dans la catégorie des demi-treillis avec zéro donne le résultat voulu. / This thesis studies some problems of the factorization of cubical areas. In the setting of analysis of programs through methods coming from algebraic topology, cubical areas are geometric models used to understand concurrency. Any concurrent programs (without loops nor branchings) can be seen as a subset of R^n where we remove some cubes which contains the states forbidden by the concurrency (think of a mutex) and where n is the number of process in the program. The first part of this thesis is interested in the question the independence of process. This question is particularly important to analyse a program, indeed being able to separate groups of process into independent part will greatly reduce the complexity of the analysis. In the geometric model, the independency is seen as a factorization up to permutation of processes. Hence the goal is to give a new effective algorithm which factorizes cubical areas, and proves that it does. The given algorithm is quite straightforward and is a generalization of the following algorithm (that we called syntactic algorithm). From the written program, groups together process that shares a resource, then take the transitive closure of this relation. This algorithm is not always optimal in that it can groups together process that actually could be separated. Thus we create a new (more relax) relationship between process. From the maximal cubes of the forbidden area of the program, if two coordinate are not equal to R, then groups them together. We can then take the transitive closure of this and get the optimal factorization. Each cube is an object of the category and between two adjacent cubes is an arrow. We can see that this category is in between the fundamental category and the components category of the cubical area. We can then show that if the cubical area factorize then so does the minced category. The reciprocal is harder to get. Indeed there's a few counter example on which we cant go back. The third and last part of this thesis is interested in seeing cubical areas as some kind of product over lower dimension cubical areas. By looking at how the booleans operations of a cubical area arise from the same operation on lower dimensional cubical areas we understand that it can be expressed as a tensor product. A tensor product is highly dependent on the category on which it is built upon. We show that to take the category of Boolean algebra is too restrictive and gives trivial result, while the category of semi-lattice with zeros works well. are not equal to R, then groups them together. We can then take the transitive closure of this and get the optimal factorization. The second part of this thesis looks at some categorical invariant that we define over cubical areas. These categories (called the minced category) slice the space into cubes.
|
60 |
HyflowCPP: A Distributed Software Transactional Memory Framework for C++Mishra, Sudhanshu 13 February 2013 (has links)
The distributed transactional memory (DTM) abstraction aims to simplify the development of distributed concurrent programs. It frees programmers from the complicated and error-prone task of explicit concurrency control based on locks (e.g., deadlocks, livelocks, non-scalability, non-composability), which are aggravated in a distributed environment due to the complexity of multi-node concurrency. At its core, DTM's atomic section-based synchronization abstraction enables the execution of a sequence of multi-node object operations with the classical serializability property, which significantly increases the programmability of distributed systems.
In this thesis, we present the first ever DTM framework for distributed concurrency control in C++, called HyflowCPP. HyflowCPP provides distributed atomic sections, and pluggable support for concurrency control algorithms, directory lookup protocols, contention management policies, and network communication protocols. The framework uses the Transaction Forwarding Algorithm (or TFA) for concurrency control. While there exists implementations of TFA and other DTM concurrency control algorithms in Scala and Java, and concomitant DTM frameworks (e.g., HyflowJava, HyflowScala, D2STM, GenRSTM), HyflowCPP provides a uniquely distinguishing TFA/DTM implementation for C++. Also, HyflowCPP supports strong atomicity, transactional nesting models including closed and open nesting (supported using modifications to TFA), and checkpointing.
We evaluated HyflowCPP through an experimental study that measured transactional throughput for a set of micro- and macro-benchmarks, and comparing with competitor DTM frameworks. Our results revealed that HyflowCPP achieves up to 600% performance improvement over competitor Java DTM frameworks including D2STM, GenRSTM, HyflowScala and HyflowJava, which can be attributed to the competitors' JVM overhead and rudimentary networking support. Additionally, our experimental studies revealed that checkpointing achieves up to 100% performance improvement over flat nesting and 50% over closed nesting. Open nesting model achieves up to 140% performance improvement over flat nesting and 90% over closed nesting. / Master of Science
|
Page generated in 0.0561 seconds