Problème du consensusLe problème du consensus est un problème fondamental en théorie du calcul distribué. Il consiste pour un ensemble de machines à se mettre d'accord sur une valeur ou, par extension, sur une séquence de valeurs. La résolution du consensus est primordiale pour la coordination des systèmes distribués. Elle permet notamment la consistance des systèmes répliqués malgré la défaillance d'une partie de leurs composants.
Read–modify–writeIn computer science, read–modify–write is a class of atomic operations (such as test-and-set, fetch-and-add, and compare-and-swap) that both read a memory location and write a new value into it simultaneously, either with a completely new value or some function of the previous value. These operations prevent race conditions in multi-threaded applications. Typically they are used to implement mutexes or semaphores. These atomic operations are also heavily used in non-blocking synchronization.
Distributed transactionA distributed transaction is a database transaction in which two or more network hosts are involved. Usually, hosts provide transactional resources, while the transaction manager is responsible for creating and managing a global transaction that encompasses all operations against such resources. Distributed transactions, as any other transactions, must have all four ACID (atomicity, consistency, isolation, durability) properties, where atomicity guarantees all-or-nothing outcomes for the unit of work (operations bundle).
Modèle de cohérenceEn Informatique, les modèles de cohérence sont utilisés dans les systèmes répartis comme les systèmes de mémoire partagée distribuée (DSM) ou les magasins de données distribuées (tels que les système de fichiers, les bases de données, les systèmes de réplication optimiste ou la mise en cache web). On dit que le système supporte un modèle donné si les opérations sur la mémoire suivent des règles spécifiques.
Non-blocking algorithmIn computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003.
LinearizabilityIn concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events, that may be extended by adding response events such that: The extended list can be re-expressed as a sequential history (is serializable). That sequential history is a subset of the original unextended list. Informally, this means that the unmodified list of events is linearizable if and only if its invocations were serializable, but some of the responses of the serial schedule have yet to return.
Concurrency controlIn information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible. Computer systems, both software and hardware, consist of modules, or components. Each component is designed to operate correctly, i.e., to obey or to meet certain consistency rules.
Reconfigurable computingReconfigurable computing is a computer architecture combining some of the flexibility of software with the high performance of hardware by processing with very flexible high speed computing fabrics like field-programmable gate arrays (FPGAs). The principal difference when compared to using ordinary microprocessors is the ability to make substantial changes to the datapath itself in addition to the control flow. On the other hand, the main difference from custom hardware, i.e.
Durabilité (informatique)Dans le contexte des bases de données, la durabilité est la propriété qui garantit qu'une transaction informatique qui a été confirmée survit de façon permanente, quels que soient les problèmes rencontrés par la base de données ou le système informatique où cette transaction a été traitée. Par exemple, dans un système de réservation de sièges d'avion, la durabilité assure qu'une réservation confirmée restera enregistrée quels que soient les problèmes rencontrés par l'ordinateur qui gère le système de réservation (panne d'électricité, écrasement de la tête sur le disque dur, etc.
Problème des généraux byzantinsEn informatique, le problème des généraux byzantins est une métaphore qui traite de la remise en cause de la fiabilité des transmissions et de l'intégrité des interlocuteurs. La question est donc de savoir comment, et dans quelle mesure, il est possible de prendre en compte une information dont la source ou le canal de transmission est suspect. La solution implique l'établissement d'un algorithme (d'une stratégie) adapté. Ce problème a été traité en profondeur pour la première fois dans l'article The Byzantine Generals Problem publié en 1982.
Réplication (informatique)En informatique, la réplication est un processus de partage d'informations pour assurer la cohérence de données entre plusieurs sources de données redondantes, pour améliorer la fiabilité, la tolérance aux pannes, ou la disponibilité. On parle de réplication de données si les mêmes données sont dupliquées sur plusieurs périphériques. La réplication n'est pas à confondre avec une sauvegarde : les données sauvegardées ne changent pas dans le temps, reflétant un état fixe des données, tandis que les données répliquées évoluent sans cesse à mesure que les données sources changent.
Read-copy-updateIn computer science, read-copy-update (RCU) is a synchronization mechanism that avoids the use of lock primitives while multiple threads concurrently read and update elements that are linked through pointers and that belong to shared data structures (e.g., linked lists, trees, hash tables). Whenever a thread is inserting or deleting elements of data structures in shared memory, all readers are guaranteed to see and traverse either the older or the new structure, therefore avoiding inconsistencies (e.g.
Designvignette|Chaise de Charles Rennie Mackintosh, 1897. Le design, le stylisme ou la stylique est une activité de création souvent à vocation industrielle ou commerciale, pouvant s’orienter vers les milieux sociaux, politiques, scientifiques et environnementaux. Le but premier du design est d’inventer, d’améliorer ou de faciliter l’usage ou le processus d’un élément ayant à interagir avec un produit ou un service matériel ou virtuel.
Tolérance aux pannesvignette|Fichier GIF animé de 8 algorithmes ECT dans un réseau 802.1aq. La source est surlignée en violet, la destination en jaune. Les lignes violettes sont des chemins entre la source et la destination et l'épaisseur indique combien de chemins traversent un lien donné. La tolérance aux pannes (ou « insensibilité aux pannes ») désigne une méthode de conception permettant à un système de continuer à fonctionner, éventuellement de manière réduite (on dit aussi en « mode dégradé »), au lieu de tomber complètement en panne, lorsque l'un de ses composants ne fonctionne plus correctement.
Méthode formelle (informatique)En informatique, les méthodes formelles sont des techniques permettant de raisonner rigoureusement, à l'aide de logique mathématique, sur un programme informatique ou du matériel électronique numérique, afin de démontrer leur validité par rapport à une certaine spécification. Elles reposent sur les sémantiques des programmes, c'est-à-dire sur des descriptions mathématiques formelles du sens d'un programme donné par son code source (ou, parfois, son code objet).
Two-phase commit protocolIn transaction processing, databases, and computer networking, the two-phase commit protocol (2PC, tupac) is a type of atomic commitment protocol (ACP). It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort (roll back) the transaction. This protocol (a specialised type of consensus protocol) achieves its goal even in many cases of temporary system failure (involving either process, network node, communication, etc.
Write protectionWrite protection is any physical mechanism that prevents writing, modifying, or erasing data on a device. Most commercial software, audio and video on writeable media is write-protected when distributed. IBM -inch magnetic tape reels, introduced in the 1950s, had a circular groove on one side of the reel, into which a soft plastic ring had to be placed in order to write on the tape. ("No ring, no write.") Audio cassettes and VHS videocassettes have tabs on the top/rear edge that can be broken off (uncovered = protected).
Algorithme de Primthumb|right|Arbre couvrant de poids minimum L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.
Algorithme de DijkstraEn théorie des graphes, l'algorithme de Dijkstra (prononcé ) sert à résoudre le problème du plus court chemin. Il permet, par exemple, de déterminer un plus court chemin pour se rendre d'une ville à une autre connaissant le réseau routier d'une région. Plus précisément, il calcule des plus courts chemins à partir d'une source vers tous les autres sommets dans un graphe orienté pondéré par des réels positifs. On peut aussi l'utiliser pour calculer un plus court chemin entre un sommet de départ et un sommet d'arrivée.
Démonstration automatique de théorèmesLa démonstration automatique de théorèmes (DAT) est l'activité d'un logiciel qui démontre une proposition qu'on lui soumet, sans l'aide de l'utilisateur. Les démonstrateurs automatiques de théorème ont résolu des conjectures intéressantes difficiles à établir, certaines ayant échappé aux mathématiciens pendant longtemps ; c'est le cas, par exemple, de la , démontrée en 1996 par le logiciel EQP.
