Questions théoriques en informatique distribuée
Le domaine de l'informatique distribuée a été terriblement mis de côté pour développer une seule théorie mathématique décrivant les algorithmes distribués. Il existe plusieurs «modèles» et cadres de calcul distribué qui ne sont tout simplement pas compatibles les uns avec les autres. L’explosion...
Les années 80 ont donné naissance aux modèles PRAM et BSP de calcul parallèle. Il semble que l'apogée des deux modèles remonte à la fin des années 80 et au début des années 90. Ces domaines sont-ils toujours actifs en termes de recherche d'algorithmes parallèles? Existe-t-il des modèles plus...
Inspiré par cette question , quels sont les problèmes majeurs et les solutions existantes qui nécessitent une amélioration dans le domaine des systèmes distribués (théoriques). Quelque chose comme les protocoles d'adhésion, la cohérence des
Cette question a été migrée à partir de la validation croisée car elle peut être répondue sur l'échange théorique de pile informatique. Migré il y a 8 ans . J'ai un problème assez unique à résoudre et j'espère que quelqu'un ici pourra me donner un aperçu de la meilleure façon de le résoudre....
En informatique distribuée, le problème du consensus semble être l'un des sujets centraux qui a attiré des recherches intensives. En particulier, le document "Impossibilité d'un consensus distribué avec un processus défectueux" a reçu le PODC Influential Paper Award 2001 . Alors pourquoi le...
Cette question est inspirée d'un commentaire de Jukka Suomela sur une autre question . Quels sont les exemples de problèmes de calcul infiniment grands mais localement finis (et algorithmes)? En d'autres termes, quels sont les exemples de calculs qui s'arrêtent dans un temps fini, dans lesquels...
Dans cet article de Kempe-Kleinberg-Tardos, les auteurs proposent des algorithmes gourmands basés sur des fonctions sous-modulaires pour déterminer les nœuds les plus influents d'un graphe, avec des applications aux réseaux sociaux.kkk Fondamentalement, l'algorithme se présente comme suit: S= e m p...
Je lis le document "Fast Paxos" de Leslie Lamport et je suis coincé avec les preuves d'exactitude des deux Paxos classiques et Fast Paxos. Par souci de cohérence, la valeur vvv choisie par le coordinateur dans la phase 2a2a2a du tour iii doit satisfaire CP(v,i):CP(v,i):CP(v,i): Pour tout...
La semaine dernière, je lisais à nouveau le transcript de Leslie's Lamport en 1982 d'une conférence qu'il a donnée sur les problèmes résolus, les problèmes non résolus et les non-problèmes dans la concurrence . Le document est facilement lisible, mais l'une des choses qui m'a fait réfléchir est...
Il existe deux principaux types de pannes de processeur dans les modèles informatiques distribués: (1) Échecs de plantage: un processeur s'arrête et ne redémarre plus. (2) Défaillances byzantines: les processeurs se comportent de manière adversaire, malveillante. Ma question est: Quels sont les...
Le problème des commérages dans les systèmes distribués est le suivant. Nous avons un graphe avec n sommets. Chaque sommet v a un message m v qui doit être envoyé à tous les nœuds.ggGnnnvvvmvmvm_v Maintenant, ma question se situe dans le contexte du modèle de réseau ad hoc (nous supposons qu'un...
Dans les systèmes de contrôle de version distribués (tels que Mercurial et Git ), il est nécessaire de comparer efficacement les graphiques acycliques dirigés (DAG). Je suis un développeur Mercurial, et nous serions très intéressés d'entendre des travaux théoriques qui discutent de la complexité...
Je suis un étudiant en master axé sur les systèmes distribués mais également intéressé par l'informatique théorique. Je me demandais s'il y avait une représentation formelle d'un système distribué au-dessus d'une machine de turing? Autrement dit, est-il possible d'étendre (faire une variante) le...
Soit un graphe connecté non régulier dont le degré est borné. Supposons que chaque nœud contienne un jeton unique.G=(V,E)G=(V,E)G= (V, E) Je veux mélanger uniformément les jetons parmi le graphique en utilisant uniquement des swaps locaux (c'est-à-dire l'échange des jetons entre deux nœuds...
Définitions Soit et soit , et des entiers positifs (avec ).ϵ>0ϵ>0\epsilon > 0r g g > 2 r + 1dddrrrgggg>2r+1g>2r+1g > 2r+1 Soit un graphe simple, régulier, non orienté, fini avec une circonférence au moins .d gG=(V,E)G=(V,E)G = (V,E)dddggg Let être un ordre total sur .V≤≤\leVVV Pour...
David Rodríguez - dribeas a écrit dans un commentaire sur StackOverflow que "toutes les collections ne peuvent pas être implémentées sans verrous". Je ne suis pas sûr que ce soit vrai, et je ne trouve aucune preuve de toute façon. Cette déclaration n'est pas très précise, mais permettez-moi...
Contexte: Le traitement des transactions est un sujet de recherche traditionnel en théorie des bases de données. De nos jours, les transactions distribuées sont popularisées par les systèmes de stockage distribué à grande échelle qui impliquent généralement la partition de données (également...
Une transaction de base de données classique simplifiée peut être considérée comme: lecture de M éléments effectuer un calcul basé sur ces lectures écrire quelques résultats N basés sur ces calculs, qui peuvent inclure les éléments lus à l'origine. Lors de l'exécution de ces transactions...
Quels articles sur la gestion des erreurs dans les systèmes distribués
Les algorithmes distribués qui résistent aux défaillances peuvent être déterministes ou probabilistes. Prenons par exemple le problème du consensus. Paxos est déterministe dans le sens où, étant donné l'hypothèse qu'il fait, il fonctionne toujours . En revanche, le consensus randomisé fonctionne...