Mutual exclusion (ME) is used to coordinate access to shared resources by concurrent processes. We investigate several new N-process shared-memory algorithms for variants of ME, each of which uses only reads and writes, and is local-spin, i.e., has bounded remote memory reference (RMR) complexity. We study these algorithms under two different shared-memory models: the distributed shared-memory (DSM) model, and the cache-coherent (CC) model. In particular, we present the first known algorithm for first- come-first-served (FCFS) ME that has O(log N) RMR complexity in both the DSM and CC models, and uses only atomic reads and writes. Our algorithm is also adaptive to point contention, i.e., the number of processes that are simultaneously active during a passage by some process. More precisely, the number of RMRs a process makes per passage in our algorithm is \Theta(min(c, log N)), where c is the point contention. We also present the first known FCFS abortable ME algorithm that is local-spin and uses only atomic reads and writes. This algorithm has O(N) RMR complexity in both the DSM and CC models, and is in the form of a transformation from abortable ME to FCFS abortable ME. In conjunction with other results, this transformation also yields the first known local-spin group mutual exclusion algorithm that uses only atomic reads and writes. Additionally, we present the first known local-spin k-exclusion algorithms that use only atomic reads and writes and tolerate up to k − 1 crash failures. These algorithms have RMR complexity O(N) in both the DSM and CC models. The simplest of these algorithms satisfies a new fairness property, called k-FCFS, that generalizes the FCFS fairness property for ME algorithms. A modification of this algorithm satisfies the stronger first-in-first-enabled (FIFE) fairness property. Finally, we present a modification to the FIFE k-exclusion algorithm that works with non-atomic reads and writes. The high-level structure of all our k-exclusion algorithms is inspired by Lamport’s famous Bakery algorithm.

Mutual exclusion (ME) is used to coordinate access to shared resources by concurrent processes. We investigate several new N-process shared-memory algorithms for variants of ME, each of which uses only reads and writes, and is local-spin, i.e., has bounded remote memory reference (RMR) complexity. We study these algorithms under two different shared-memory models: the distributed shared-memory (DSM) model, and the cache-coherent (CC) model. In particular, we present the first known algorithm for first- come-first-served (FCFS) ME that has O(log N) RMR complexity in both the DSM and CC models, and uses only atomic reads and writes. Our algorithm is also adaptive to point contention, i.e., the number of processes that are simultaneously active during a passage by some process. More precisely, the number of RMRs a process makes per passage in our algorithm is \Theta(min(c, log N)), where c is the point contention. We also present the first known FCFS abortable ME algorithm that is local-spin and uses only atomic reads and writes. This algorithm has O(N) RMR complexity in both the DSM and CC models, and is in the form of a transformation from abortable ME to FCFS abortable ME. In conjunction with other results, this transformation also yields the first known local-spin group mutual exclusion algorithm that uses only atomic reads and writes. Additionally, we present the first known local-spin k-exclusion algorithms that use only atomic reads and writes and tolerate up to k − 1 crash failures. These algorithms have RMR complexity O(N) in both the DSM and CC models. The simplest of these algorithms satisfies a new fairness property, called k-FCFS, that generalizes the FCFS fairness property for ME algorithms. A modification of this algorithm satisfies the stronger first-in-first-enabled (FIFE) fairness property. Finally, we present a modification to the FIFE k-exclusion algorithm that works with non-atomic reads and writes. The high-level structure of all our k-exclusion algorithms is inspired by Lamport’s famous Bakery algorithm.

Doctor of Philosophy / Department of Computing and Information Sciences / Gurdip Singh / In this dissertation, we propose a cyber-physical system model, and based on this model, present algorithms for a set of distributed computing problems. Our model specifies a cyber-physical system as a combination of cyber-infrastructure, physical-infrastructure, and user behavior specification. The cyber-infrastructure is superimposed on the physical-infrastructure and continuously monitors its (physical-infrastructure's) changing state. Users operate in the physical-infrastructure and interact with the cyber-infrastructure using hand-held devices and sensors; and their behavior is specified in terms of actions they can perform (e.g., move, observe). While in traditional distributed systems, users interact solely via the underlying cyber-infrastructure, users in a cyber-physical system may interact directly with one another, access sensor data directly, and perform actions asynchronously with respect to the underlying cyber-infrastructure. These additional types of interactions have an impact on how distributed algorithms for cyber-physical systems are designed. We augment distributed mutual exclusion and predicate detection algorithms so that they can accommodate user behavior, interactions among them and the physical-infrastructure. The new algorithms have two components - one describing the behavior of the users in the physical-infrastructure and the other describing the algorithms in the cyber-infrastructure. Each combination of users' behavior and an algorithm in the cyber-infrastructure yields a different cyber-physical system algorithm. We have performed extensive simulation study of our algorithms using OMNeT++ simulation engine and Uppaal model checker. We also propose Cyber-Physical System Modeling Language (CPSML) to specify cyber-physical systems, and a centralized global state recording algorithm.

Abortable mutual exclusion is a variant of mutual exclusion, in which processes are allowed to abort in the trying protocol. Scott presented the first local-spin abortable mutual exclusion algorithms. They are based on a queue and perform O(1) remote memory accesses (RMAs) when no processes abort. However, they use unbounded space and a process can perform an unbounded number of RMAs, in the worst case, to enter the critical section. The only other local-spin abortable mutual exclusion algorithm is by Jayanti. It has bounded space and RMA complexity, but a process always performs \Theta(log N) RMAs to enter the critical section, where N is the number of processes. In this thesis, three new, bounded space, abortable mutual exclusion algorithms are presented. We give the first local-spin abortable mutual exclusion algorithm that uses only registers. It has \Theta(log N) RMA complexity, even if no processes abort. We also present the first local-spin abortable mutual exclusion algorithm using more general primitives which has bounded space and in which each process performs O(1) RMAs to enter the critical section when no processes abort. However, this algorithm is local-spin only for a certain type of cache-coherent model. Finally, we present an abortable mutual exclusion algorithm which is local-spin in any cache-coherent model and in which each process performs O(1) RMAs to enter the critical section when no processes abort. We develop a new reference counting method to bound the space used in this algorithm.

Abortable mutual exclusion is a variant of mutual exclusion, in which processes are allowed to abort in the trying protocol. Scott presented the first local-spin abortable mutual exclusion algorithms. They are based on a queue and perform O(1) remote memory accesses (RMAs) when no processes abort. However, they use unbounded space and a process can perform an unbounded number of RMAs, in the worst case, to enter the critical section. The only other local-spin abortable mutual exclusion algorithm is by Jayanti. It has bounded space and RMA complexity, but a process always performs \Theta(log N) RMAs to enter the critical section, where N is the number of processes. In this thesis, three new, bounded space, abortable mutual exclusion algorithms are presented. We give the first local-spin abortable mutual exclusion algorithm that uses only registers. It has \Theta(log N) RMA complexity, even if no processes abort. We also present the first local-spin abortable mutual exclusion algorithm using more general primitives which has bounded space and in which each process performs O(1) RMAs to enter the critical section when no processes abort. However, this algorithm is local-spin only for a certain type of cache-coherent model. Finally, we present an abortable mutual exclusion algorithm which is local-spin in any cache-coherent model and in which each process performs O(1) RMAs to enter the critical section when no processes abort. We develop a new reference counting method to bound the space used in this algorithm.

A mobile ad hoc network consists of certain nodes that communicate only through wireless medium and can move arbitrarily. The key feature of a mobile ad hoc network is the mobility of the nodes. Because of the mobility, communication links form and disappear as nodes come into and go out of each other's communica- tion range. Mobile ad hoc networks are particularly useful in situations like disaster recovery and search, military operations, etc. Research on mobile ad hoc networks has drawn a huge amount of attention recently. The main challenges for mobile ad hoc networks are the sparse resources and frequent mobility. Most of the research work has been focused on the MAC and routing layer. In this work, we focus on distributed services for mobile ad hoc networks. These services will provide some fundamental functions in developing various applications for mobile ad hoc networks. In particular, we focus on the clock synchronization, connected dominating set, and k-mutual exclusion problems in mobile ad hoc networks.

Les systèmes à grande échelle comme les Grilles ou les Nuages (Clouds) mettent à disposition pour les utilisateurs des ressources informatiques hétérogènes. Dans les Nuages, les accès aux ressources sont orchestrés par des contrats permettant de définir un niveau de qualité de service (temps de réponse, disponibilité ...) que le fournisseur doit respecter. Ma thèse a donc contribué à concevoir de nouveaux algorithmes distribués de verrouillage de ressources dans les systèmes large échelle en prenant en compte des notions de qualité de service. Dans un premier temps, mes travaux de thèse se portent sur des algorithmes distribués de verrouillage ayant des contraintes en termes de priorités et de temps. Deux algorithmes d'exclusion mutuelle ont été proposés : un algorithme prenant en compte les priorités des clients et un autre pour des requêtes avec des dates d'échéance. Dans un second temps, j'ai abordé le problème de l'exclusion mutuelle généralisée pour allouer de manière exclusive plusieurs types de ressources hétérogènes. J'ai proposé un nouvel algorithme qui réduit les coûts de synchronisation en limitant la communication entre processus non conflictuels. Tous ces algorithmes ont été implémentés et évalués sur la plateforme nationale Grid 5000. Les évaluations ont montré que nos algorithmes satisfaisaient bien les contraintes applicatives tout en améliorant de manière significative les performances en termes de taux d'utilisation et de temps de réponse. / Distributed large-scale systems such as Grids or Clouds provide large amounts of heterogeneous computing resources. Clouds manage ressource access by contracts that allow to define a quality of service (response time, availability, ...) that the provider has to respect. My thesis focuses on designing new distributed locking algorithms for large scale systems that integrate notions of quality of service. At first, my thesis targets distributed locking algorithms with constraints in terms of priorities and response time. Two mutual exclusion algorithms are proposed: a first algorithm takes into account client-defined priorities and a second one associates requests with deadlines. I then move on to a generalized mutual exclusion problem in order to allocate several types of heterogeneous resources in a exclusive way. I propose a new algorithm that reduces the cost of synchronization by limiting communication between non-conflicting processes.All algorithms have been implemented and evaluated over the national platform Grid 5000. Evaluations show that our algorithms satisfy applicative constraints while improving performance significatively in terms of resources use rate and response time.

No description available.

No description available.

Une multitude d'algorithmes d'exclusion mutuelle ont été conçus au cours des vingt cinq dernières années, dans le but d'améliorer les performances liées à l'exécution de sections critiques et aux verrous.Malheureusement, il n'existe actuellement pas d'étude générale et complète au sujet du comportement de ces algorithmes d'exclusion mutuelle sur des applications réalistes (par opposition à des applications synthétiques) qui considère plusieurs métriques de performances, telles que l'efficacité énergétique ou la latence.Dans cette thèse, nous effectuons une analyse pragmatique des mécanismes d'exclusion mutuelle, dans le but de proposer aux développeurs logiciels assez d'informations pour leur permettre de concevoir et/ou d'utiliser des mécanismes rapides, qui passent à l'échelle et efficaces énergétiquement.Premièrement, nous effectuons une étude de performances de 28 algorithmes d'exclusion mutuelle faisant partie de l'état de l'art, en considérant 40 applications et quatre machines multicœurs différentes.Nous considérons non seulement le débit (la métrique de performance traditionnellement considérée), mais aussi l'efficacité énergétique et la latence, deux facteurs qui deviennent de plus en plus importants.Deuxièmement, nous présentons une analyse en profondeur de nos résultats.Plus particulièrement, nous décrivons neufs problèmes de performance liés aux verrous et proposons six recommandations aidant les développeurs logiciels dans le choix d'un algorithme d'exclusion mutuelle, se basant sur les caractéristiques de leur application ainsi que les propriétés des différents algorithmes.A partir de notre analyse détaillée, nous faisons plusieurs observations relatives à l'interaction des verrous et des applications, dont plusieurs d'entre elles sont à notre connaissance originales:(i) les applications sollicitent fortement les primitives lock/unlock mais aussi l'ensemble des primitives de synchronisation liées à l'exclusion mutuelle (ex. trylocks, variables de conditions),(ii) l'empreinte mémoire d'un verrou peut directement impacter les performances de l'application,(iii) pour beaucoup d'applications, l'interaction entre les verrous et l'ordonnanceur du système d'exploitation est un facteur primordial de performance,(iv) la latence d'acquisition d'un verrou a un impact très variable sur la latence d'une application,(v) aucun verrou n'est systématiquement le meilleur,(vi) choisir le meilleur verrou est difficile, et(vii) l'efficacité énergétique et le débit vont de pair dans le contexte des algorithmes d'exclusion mutuelle.Ces découvertes mettent en avant le fait que la synchronisation à base de verrou ne se résume pas seulement à la simple interface "lock - unlock".En conséquence, ces résultats appellent à plus de recherche dans le but de concevoir des algorithmes d'exclusion mutuelle avec une empreinte mémoire faible, adaptatifs et qui implémentent l'ensemble des primitives de synchronisation liées à l'exclusion mutuelle.De plus, ces algorithmes ne doivent pas seulement avoir de bonnes performances d'un point de vue du débit, mais aussi considérer la latence ainsi que l'efficacité énergétique. / A plethora of optimized mutual exclusion lock algorithms have been designed over the past 25 years to mitigate performance bottlenecks related to critical sections and synchronization.Unfortunately, there is currently no broad study of the behavior of these optimized lock algorithms on realistic applications that consider different performance metrics, such as energy efficiency and tail latency.In this thesis, we perform a thorough and practical analysis, with the goal of providing software developers with enough information to achieve fast, scalable and energy-efficient synchronization in their systems.First, we provide a performance study of 28 state-of-the-art mutex lock algorithms, on 40 applications, and four different multicore machines.We not only consider throughput (traditionally the main performance metric), but also energy efficiency and tail latency, which are becoming increasingly important.Second, we present an in-depth analysis in which we summarize our findings for all the studied applications.In particular, we describe nine different lock-related performance bottlenecks, and propose six guidelines helping software developers with their choice of a lock algorithm according to the different lock properties and the application characteristics.From our detailed analysis, we make a number of observations regarding locking algorithms and application behaviors, several of which have not been previously discovered:(i) applications not only stress the lock/unlock interface, but also the full locking API (e.g., trylocks, condition variables),(ii) the memory footprint of a lock can directly affect the application performance,(iii) for many applications, the interaction between locks and scheduling is an important application performance factor,(iv) lock tail latencies may or may not affect application tail latency,(v) no single lock is systematically the best,(vi) choosing the best lock is difficult (as it depends on many factors such as the workload and the machine), and(vii) energy efficiency and throughput go hand in hand in the context of lock algorithms.These findings highlight that locking involves more considerations than the simple "lock - unlock" interface and call for further research on designing low-memory footprint adaptive locks that fully and efficiently support the full lock interface, and consider all performance metrics.