Bonjour,
Je me pose la question suivante : lorsque Duniter choisit le contenu d’un bloc qu’il crée et pour lequel il a plusieurs options concurrentes, fait-il ce choix de façon aléatoire, ou y a-t-il un biais déterministe dans ce choix de par sa programmation ? Une autre façon de formuler la question est : le choix du contenu d’un bloc vient-il d’un déterminisme interne (programmation) ou externe (réseau) ?
Exemple : MystraSam a un dossier complet en piscine et devrait bientôt devenir membre. Il est notamment certifié par Mandy et sa date d’entrée dépend de la date de disponibilité de cette certification. Toutefois Mandy peut aussi certifier quatre autres personnes déjà membres à la même date que MystraSam. Qui va être certtifié en premier ? Est-ce que Duniter favorise plutôt la certification d’un dossier en piscine ? d’une personne déjà membre ? ou est-il agnostique de ce point de vue ?
Je cherche à calculer les probabilités d’admission des dossiers à telle ou telle date, et j’ai supposé jusqu’à présent que toutes les options concurrentes à la même date étaient équiprobables, mais un doute m’étreint, d’où ma question.
Duniter procède par itérations : il essaye l’identité A, puis B, puis C, etc. Bien sûr si A et B ont des certifieurs en commun, il se peut que B soit refusé pour ce bloc précis.
Quant au choix des identités, elles viennent par ordre alphabétique je crois bien. Le code est franchement peu lisible dans cette partie, toutefois elle se trouve ici : https://github.com/duniter/duniter/blob/dev/app/modules/prover/lib/blockGenerator.ts
Je compte la refactorer dans les prochaines semaines elle aussi, afin d’optimiser le nombre d’entrées simultanées. Donc l’algorithme va changer 
Merci.
J’ai un peu de mal à lire le javascript. Il faudra que je l’apprenne un jour si je trouve un peu de temps, au moins pour pouvoir le lire. Mais si les entités examinées sont traitées dans l’ordre alphabétique (des pubkeys ? des uids ?), il ne devrait pas y avoir de différence entre le traitement des dossiers et celui des certifications isolées. Je vais donc conserver mon hypothèse de départ. Pour le futur algorithme, tu pourrais faire le choix avec un générateur pseudo-aléatoire.
Il me semble que Duniter priorise les certifications externes (vers un nouvel entrant) par rapport aux certifications internes (vers un membre déjà membre). @cgeek m’avais dit cela sur le salon et c’est aussi le comportement que je constate sur tout les cas que j’ai observer sur les périodes ou les piscines se synchronisait bien (car un nœud qui n’aurait que la certif interne et qui trouve le 1er bloc ou le certifieur est de nouveau dispo écrira forcément cette certif interne mais ce cas est très rare)
Ah, OK. J’avais aussi un peu ce sentiment, mais n’avais pas encore assez de recul. Je vais vérifier sur quelques exemples et, si ça se confirme, je changerai mon algorithme. Et que penses-tu de l’ordre de passage des certifications internes concurrentes ? @cgeek évoque un passage dans l’ordre alphabétique (mais de quel champ ?). As-tu remarqué quelque chose dans ce sens ?
Oui c’est le champ uid 
Bon, merci. On va voir si ça se vérifie.
Mais si ça se vérifie, ce n’est pas une bonne nouvelle. Il vaudra mieux avoir alors un pseudo proche du début de l’alphabet pour entrer vite dans la toile. Ça manque d’équité, même si ce n’est qu’un effet à la marge.
Première vérification : nana est entrée avant stanjourdan. Pour l’instant, c’est le seul exemple que j’ai sous la main.
En fait, ce n’est pas un problème si à la marge que ça. Lorsque des dossiers d’entrée ont plusieurs certificateurs en commun, il arrive souvent qu’ils soient en concurrence à la même date. Et dans ce cas, ils seraient validés dans l’ordre alphabétique, avec des retards de 5, 10, 15 jours ou plus pour les derniers ? Il me semblerait assez important de corriger ça dans la prochaine version si c’est possible.
Il y a plusieurs algos possibles. J’en retiens deux pour l’instant parmi lesquels il faut choisir :
- Maximiser le nombre d’entrées de membres
- Prioriser les vieux dossiers
En tous les cas, peux-tu faire un ticket GitHub en ce sens avec un lien vers cette conversation ? Et jalon 1.4.0.
C’est vrai que l’optimisation n’était pas ma priorité au début des développements, mais maintenant c’est le moment !
On peut aussi faire un tirage au sort. Ce serait sans doute le plus juste, le plus simple à programmer, et peut-être le plus efficace pour faire passer tout le monde le plus vite possible en moyenne.
OK pour le ticket Github (ou Gitlab ?).
Oui aussi, pourquoi pas. Je n’ai pas d’avis tranché, mais une solution simple me conviendra parfaitement
Sur GitHub. On n’a pas encore de GitLab.
Suite à ton ticket, j’ai donc implémenté un mélange avant intégration des nouveaux dans le bloc :
Il s’agit d’un mélange basé sur l’algorithme Fisher–Yates.
Oui, ça parait bien. Super ! Juste une dernière question : tu n’appliques ce mélange qu’aux certifications externes, je suppose, les certifications internes à la même date n’étant traitées qu’après. C’est bien ça ? Je n’y vois pas d’inconvénient majeur, sauf qu’on n’est jamais tout à fait sûr que le contenu particulier de la piscine du noeud produisant le bloc contienne un dossier externe et qu’il peut faire passer les certifications internes avant. C’est pour cela que j’aurais préféré un mélange aléatoire sur l’ensemble du contenu de la piscine afin qu’il n’y ait pas de cas particulier. Toutefois, je conçois que le phénomène est rare et qu’en tenir compte peut compliquer la programmation.
En fait, j’applique ce mélange aux identités. J’utilise ensuite les certifications comme contrainte nécessaire à passer, et si par exemple pour une identité B une certification vient d’être consommée par une identité précédente A dans le même bloc, alors l’identité B est rejetée pour le bloc.
Je ne peux donc pas mélanger les certifications dans ce cas. D’ailleurs j’imagine mal un tel algorithme ?
Tu mélanges toutes les identités devant être certifiées, qu’elles soient déjà membres ou non ? Si c’est ça, alors c’est exactement ce que je voulais. Il n’y a pas lieu, je suis bien d’accord, de mélanger les certifications, ce qui n’a, effectivement, pas grand sens. Désolé de ne pas avoir été plus clair.
Non si tu regarde le code c’est seulement les newcomers qui sont mélangés, et c’est mieux ainsi pour des raisons de perf, s’il fallait mélanger un million de membres bonjour la latence sur les machines peu puissantes !
EDIT : alors que le nombre de newcomers (identités non-membre) restera toujours faible, dans une communauté stable cela correspond au débit des naissances.
J’ai bien dit “devant être certifiées”. Il ne s’agit pas de mélanger toutes les identités. On regarde toutes les certifications en attente, on construit l’ensemble des identités destinataires de ces certifications et on le mélange. C’est très rapide.
Oui ç’aurait été possible, mais je privilégie en effet les nouveaux entrants plutôt que les membres.
Mais du coup, si je devais mélanger parmis tous les certifiés, alors je devrais revoir profondément le code. Ce que je ne souhaite pas faire pour le moment.
OK, c’est clair. L’essentiel est là, et je t’en remercie.