Publication

Optimal Fair Computation

Rachid Guerraoui
2016
Reports

Résumé

A computation scheme among n parties is fair if no party obtains the computation result unless all other n-1 parties obtain the same result. A fair computation scheme is optimistic if n honest parties can obtain the computation result without resorting to a trusted third party. We prove, for the first time, a tight lower bound on the message complexity of optimistic fair computation for n parties among which n-1 can be malicious in an asynchronous network. We do so by relating the optimal message complexity of optimistic fair computation to the length of the shortest permutation sequence in combinatorics.

Source officielle

https://infoscience.epfl.ch/entities/publication/f4314eeb-46da-48bc-a726-9e0e3db2fa6d

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Rachid Guerraoui
2016
Reports

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/f4314eeb-46da-48bc-a726-9e0e3db2fa6d

À propos de ce résultat

Concepts associés (32)

Parti politique

Un parti politique est un groupe de personnes possédant des idées politiques communes réunis en association. Il peut chercher à influencer le gouvernement en place, en le soutenant si celui-ci en est issu, ou en s'y opposant. Il nomme également ses propres candidats aux différentes élections et en tentant d'obtenir des mandats politiques. Un parti politique peut aussi influencer l'opinion publique. Il peut être présent au Parlement. Plus généralement, la notion de parti politique possède deux définitions.

Complexité de Kolmogorov

En informatique théorique et en mathématiques, plus précisément en théorie de l'information, la complexité de Kolmogorov, ou complexité aléatoire, ou complexité algorithmique d'un objet — nombre, , chaîne de caractères — est la taille du plus petit algorithme (dans un certain langage de programmation fixé) qui engendre cet objet. Elle est nommée d'après le mathématicien Andreï Kolmogorov, qui publia sur le sujet dès 1963. Elle est aussi parfois nommée complexité de Kolmogorov-Solomonoff.

Combinatoire

En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements. La combinatoire est en fait présente dans toute l'antiquité en Inde et en Chine. Donald Knuth, dans le volume 4A « Combinatorial Algorithms » de The Art of Computer Programming parle de la génération de n-uplets ; il dit que la génération de motifs combinatoires «a commencé alors que la civilisation elle-même prenait forme» (« began as civilization itself was taking shape»).

Afficher plus

Publications associées (5)

Afficher plus

Optimal Fair Computation

Chattez avec Graph Search

Symmetry-Aware Bayesian Optimization via Max Kernels

Complexity of linear relaxations in integer programming

Continuously Reproducing Toolchains in Pattern Recognition and Machine Learning Experiments