1,721,006 research outputs found
Contribution à l'algorithmique distribuée de contrôle : arbres couvrants avec et sans containtes
No full textIn this PhD thesis, we present a study of distributed asynchronousalgorithms of control.Distributed algorithms are algorithms operating on distributedsystems. These systems consist in networks of sites, where each sitecan be either simple (when reduced to a single processor) or complex(when expanded to a whole computer or a Local Area Network).In this study, we only consider networks of sites sharing neithermemory nor global clock. Sites work in parallel, asynchronously andeach computation is only performed by message exchange. In such acontext, distributed algorithms are called ``message-driven''. We tryto limit waiting states by not introducing synchronizationmechanisms. Generally speaking, we make no particular assumption onthe way algorithms start, namely, any non-empty subset of sites maystart an algorithm. We try to remain as general as possible but in thiswork, we limit our considerations to determinist algorithms. Ourassumptions are supporting the essential properties of distributedalgorithms~: that is essentially the local behaviour.A control algorithm establishes a virtual structure over the wholenetwork in which each site can distinguish some of its neighbors toplay special roles. More particularly, we have chosen to studystructures which are similar to spanning trees. We recall thatnumerous problems in distributed computing, such as distributedtermination and leader election, can be reduced to spanning treeconstruction. In order to construct such a structure or to elect aleader, most of known distributed algorithms transform this probleminto an extrema-finding problem. In fact, they elect the site whichhas the greatest (or the lowest) identity and construct a spanning treeat the same time.We study two kinds of algorithms~: phase-based algorithms andwhat we call anarchic algorithms. The latter algorithms are designedto behave without any kind of synchronization. Of course their studyis difficult and they often need more message exchange, but this kindof un-foreseeable behaviour is a rather good way for improving the fault tolerance.We present a new algorithm of such a kind, moreover it is associatedto a leader election which is not an extrema-finding. Its analysisleads us to show worst-case examples, but these examples are rare and our empirical average-case analysis show that this algorithm is almost as good as the best known algorithm for spanning tree construction.This latter algorithm uses token-based methods and therefore behave more sequentially.Other algorithms such as constructing constrained spanning trees, arestudied. The most popular constraint is the minimum total weight,which represents an economical criterion. To our knowledge, theMinimum Diameter Spanning Tree is a problem which had never beenaddressed in the field of distributed research. We consider``weighted'' diameter~: viz. the diameter of a graph is the sum ofthe edges' weights along the longest shortest path. If we considertime complexity, this constraint is obviously of great interest, sinceit always exists a couple of sites needing at least units of timeto exchange information.We present a method for constructing a MDST and from this method, wegive different algorithms, whether fault tolerance is needed or not.Finally, the practical study of distributed algorithm on largenetworks leads to build a simulator. Compared to the otherssimulators, ours offer the advantage of being simple and easilyadaptable. In order to have faster and more realistic simulations, weparallelize this algorithm. The same code can be performed on apersonal computer, a parallel computer or even a distributed machine.Nous présentons dans cette thèse une étude sur desalgorithmes distribués asynchrones et déterministes decontröle. Un système distribué consiste en un réseaude sites (processeurs, ordinateurs ou réseaux locaux). Dans cettethèse, nous ne considérons que des réseaux de sitescommunicants n'ayant ni mémoire partagée ni horloge globale.De nombreux problèmes de l'algorithmique distribuée sontréductibles à la construction d'un Arbre Couvrant qui est lastructure de contrôle qui nous intéresse.Nous étudions deux types d'algorithmes~: ceux utilisantla notion de phase logique et les autres qui ne considèrent aucunmécanisme de synchronisation. Ces derniers ont des comportementsimprévisibles améliorant la tolérance aux fautes. Nousprésentons un nouvel algorithme de ce type associé à uneélection qui n'est pas une recherche d'extremum contrairementà l'usage. Cet algorithme est comparable au meilleuralgorithme connu qui utilise des jetons et des phases logiquesinduisant un comportement plus "séquentiel".D'autres algorithmes, construisant des AC contraints, sontconsidérés. En particulier l'AC de Diamètre Minimum quiest, à notre connaissance, un problème qui n'a jamaisété étudié dans ce domaine. Le diamètre d'ungraphe est la somme des poids des arêtes du plus long des pluscourts chemins. Si nous considérons la complexité temporelle,cette contrainte est d'un intérêt &vident. Nous proposonsdifférents algorithmes suivant que la tolérance aux fautes estnécessaire ou non.Finalement, l'étude pratique des algorithmes distribués surdes réseaux de grande taille nous a conduit à la constructiond'un simulateur. Il permet l'exécution d'un même code sourcesur des machines séquentielles ou parallèles
Procedings of the 4th International Conference on Principles of Distributed Systems, OPODIS 2000
No full textISBN 2-912590-11-
Contribution à l'algorithmique distribuée : arbres et ordonnancement
No full textIn this "Licence to supervise research" (HDR in French) thesis, we present a study of distributed asynchronous algorithms for control and scheduling. A control algorithm establishes a virtual structure over a network of communicating sites. We choose to make a minimum of assumptions about the knowledge of each site. In this study, we only consider networks of sites sharing neither memory nor global clock. Sites work in parallel, asynchronously and each computation is only performed by message exchange. In such a context, distributed algorithms are called ''message-driven''. We try to limit waiting states by not introducing synchronization mechanisms. Generally speaking, we make no particular assumption on the way algorithms start, namely, any non-empty subset of sites may start an algorithm. We try to remain as general as possible but in this work, we limit our considerations to deterministic algorithms. Our assumptions are supporting the essential properties of distributed algorithms~: that is essentially the local behavior. A control algorithm establishes a virtual structure over the whole network in which each site can distinguish some of its neighbors to play special roles. More particularly, we have chosen to study structures which are similar to trees. We recall that numerous problems in distributed computing, such as distributed termination and leader election, can be reduced to spanning tree construction. In order to construct such a structure or to elect a leader, most of known distributed algorithms transform this problem into an extrema-finding problem. In fact, they elect the site which has the greatest (or the lowest) identity and construct a spanning tree at the same time. In a first part, we study algorithms to construct constrained spanning trees, these constraints contribute to a greater efficiency to the control structure established. The most popular constraint is the minimum total weight, which represents an economical criterion. To our knowledge, the Minimum Diameter Spanning Tree is a problem which had never been addressed in the field of distributed research. We consider ''weighted'' diameter~: viz. the diameter of a graph is the sum of the edges' weights along the longest shortest path. If we consider time complexity, this constraint is obviously of great interest, since it always exists a couple of sites needing at least units of time to exchange information. The Minimum Degree Spanning Tree is a new problem in the field of distributed research also. This constraint allows, for example, the use of cheaper interconnection equipments. We present an approximate algorithm for this problem (proven to be NP-hard) that find a spanning tree of degree 1 to the optimum. In the final part we are interested in finding efficient heuristics to the problem of distributed on-line scheduling, with sporadic arrivals, first for independent tasks and next for tasks with dependencies (directed acyclic graph of dependencies). We show that the tree structure can be used with much benefits. In particular, in arbitrary wide networks, shortest paths trees limited to not too far neighbors can be used to define a new and promising concept: the computing sphere. This computing sphere limits exchanged messages and computation time.Nous présentons dans ce mémoire de thèse d'habilitation une étude sur des algorithmes distribués asynchrones de contrôle et d'ordonnancement. Un algorithme de contrôle établit une structure virtuelle sur un réseau de sites communicants. Nous faisons le choix %délibéré de faire un minimum d'hypothèses sur les connaissances de chaque site. De même, nous évitons autant que possible d'utiliser des mécanismes conduisant à des attentes qui peuvent être pénalisantes comme, par exemple, l'utilisation de synchroniseurs. Ces choix conduisent à privilégier les modes de fonctionnement essentiellement locaux. %dépendant le moins possible de l'état du reste du réseau. Nous introduisons toutefois une limite à cette démarche, dans ce travail, nous ne considérons que des algorithmes déterministes. Dans ces circonstances, un problème essentiel de l'algorithmique distribuée est l'établissement d'une structure de contrôle couvrant la totalité du réseau, dans laquelle chaque site distingue certains de ses voisins de façon spécifique. Après avoir rappelé des notions fondamentales en partie I, nous présentons dans la première partie, trois de nos algorithmes de construction d'arbre couvrant avec contraintes, ces dernières apportant une plus grande efficacité à la structure de contrôle établie. En particulier, nous considérons la contrainte de poids total minimum qui caractérise plutôt une recherche économique, celle de diamètre minimum qui concerne l'efficacité à la fois en temps mais aussi évidemment en messages et la contrainte de degré minimal qui permet par exemple d'utiliser des équipements d'interconnection moins coûteux. Dans la troisième partie nous présentons deux de nos heuristiques pour la résolution du problème de l'ordonnancement distribué en ligne, avec arrivées sporadiques, d'abord de tâches indépendantes puis de tâches avec dépendances non cycliques. Nous montrons que là encore, la structure d'arbre peut être utilisée de façon bénéfique. En particulier, dans des réseaux de taille arbitrairement grande, des arbres de plus courts chemins limités aux voisins relativement proches peuvent être utilisés pour définir un concept nouveau et prometteur ,: la Sphère de Calcul. Cette Sphère de Calcul limite le nombre de messages échangés et le temps de calcul. Tout au long de ce mémoire nous présentons des algorithmes nouveaux, voire pionniers dans leurs domaine. De nombreux développements sont possibles, certains déjà réalisés par nous-même ou par d'autres auteurs, d'autres sont des problèmes ouverts (recherche d'algorithmes optimaux par exemple)
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Data Coherency in Distributed Shared Memory
No full textInternational audienceWe present a new model for distributed shared memory systems, based on remote data accesses. Such features are offered by network interface cards that allow one-sided operations, remote direct memory access and OS bypass. This model leads to new interpretations of distributed algorithms allowing us to propose an innovative detection technique of race conditions only based on logical clocks. Indeed, the presence of (data) races in a parallel program makes it hard to reason about and is usually considered as a bug
Contribution à l'algorithmique distribuée de contrôle : arbres couvrants avec et sans containtes
No full textIn this PhD thesis, we present a study of distributed asynchronousalgorithms of control.Distributed algorithms are algorithms operating on distributedsystems. These systems consist in networks of sites, where each sitecan be either simple (when reduced to a single processor) or complex(when expanded to a whole computer or a Local Area Network).In this study, we only consider networks of sites sharing neithermemory nor global clock. Sites work in parallel, asynchronously andeach computation is only performed by message exchange. In such acontext, distributed algorithms are called ``message-driven''. We tryto limit waiting states by not introducing synchronizationmechanisms. Generally speaking, we make no particular assumption onthe way algorithms start, namely, any non-empty subset of sites maystart an algorithm. We try to remain as general as possible but in thiswork, we limit our considerations to determinist algorithms. Ourassumptions are supporting the essential properties of distributedalgorithms~: that is essentially the local behaviour.A control algorithm establishes a virtual structure over the wholenetwork in which each site can distinguish some of its neighbors toplay special roles. More particularly, we have chosen to studystructures which are similar to spanning trees. We recall thatnumerous problems in distributed computing, such as distributedtermination and leader election, can be reduced to spanning treeconstruction. In order to construct such a structure or to elect aleader, most of known distributed algorithms transform this probleminto an extrema-finding problem. In fact, they elect the site whichhas the greatest (or the lowest) identity and construct a spanning treeat the same time.We study two kinds of algorithms~: phase-based algorithms andwhat we call anarchic algorithms. The latter algorithms are designedto behave without any kind of synchronization. Of course their studyis difficult and they often need more message exchange, but this kindof un-foreseeable behaviour is a rather good way for improving the fault tolerance.We present a new algorithm of such a kind, moreover it is associatedto a leader election which is not an extrema-finding. Its analysisleads us to show worst-case examples, but these examples are rare and our empirical average-case analysis show that this algorithm is almost as good as the best known algorithm for spanning tree construction.This latter algorithm uses token-based methods and therefore behave more sequentially.Other algorithms such as constructing constrained spanning trees, arestudied. The most popular constraint is the minimum total weight,which represents an economical criterion. To our knowledge, theMinimum Diameter Spanning Tree is a problem which had never beenaddressed in the field of distributed research. We consider``weighted'' diameter~: viz. the diameter of a graph is the sum ofthe edges' weights along the longest shortest path. If we considertime complexity, this constraint is obviously of great interest, sinceit always exists a couple of sites needing at least units of timeto exchange information.We present a method for constructing a MDST and from this method, wegive different algorithms, whether fault tolerance is needed or not.Finally, the practical study of distributed algorithm on largenetworks leads to build a simulator. Compared to the otherssimulators, ours offer the advantage of being simple and easilyadaptable. In order to have faster and more realistic simulations, weparallelize this algorithm. The same code can be performed on apersonal computer, a parallel computer or even a distributed machine.Nous présentons dans cette thèse une étude sur desalgorithmes distribués asynchrones et déterministes decontröle. Un système distribué consiste en un réseaude sites (processeurs, ordinateurs ou réseaux locaux). Dans cettethèse, nous ne considérons que des réseaux de sitescommunicants n'ayant ni mémoire partagée ni horloge globale.De nombreux problèmes de l'algorithmique distribuée sontréductibles à la construction d'un Arbre Couvrant qui est lastructure de contrôle qui nous intéresse.Nous étudions deux types d'algorithmes~: ceux utilisantla notion de phase logique et les autres qui ne considèrent aucunmécanisme de synchronisation. Ces derniers ont des comportementsimprévisibles améliorant la tolérance aux fautes. Nousprésentons un nouvel algorithme de ce type associé à uneélection qui n'est pas une recherche d'extremum contrairementà l'usage. Cet algorithme est comparable au meilleuralgorithme connu qui utilise des jetons et des phases logiquesinduisant un comportement plus "séquentiel".D'autres algorithmes, construisant des AC contraints, sontconsidérés. En particulier l'AC de Diamètre Minimum quiest, à notre connaissance, un problème qui n'a jamaisété étudié dans ce domaine. Le diamètre d'ungraphe est la somme des poids des arêtes du plus long des pluscourts chemins. Si nous considérons la complexité temporelle,cette contrainte est d'un intérêt &vident. Nous proposonsdifférents algorithmes suivant que la tolérance aux fautes estnécessaire ou non.Finalement, l'étude pratique des algorithmes distribués surdes réseaux de grande taille nous a conduit à la constructiond'un simulateur. Il permet l'exécution d'un même code sourcesur des machines séquentielles ou parallèles
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
A Bi-objective Algorithm for Scheduling Parallel Applications on Heterogeneous Systems Subject to Failures
No full textNational audienc
- …
