Load Balanced Scalable Byzantine Agreement through Quorum Building, with Full Information

We address the problem of designing distributed algorithms for large scale networks that are robust to Byzantine faults. We consider a message passing, full information model: the adversary is malicious, controls a constant fraction of processors, and can view all messages in a round before sending out its own messages for that round. Furthermore, each bad processor may send an unlimited number of messages. The only constraint on the adversary is that it must choose its corrupt processors at the start, without knowledge of the processors’ private random bits.

A good quorum is a set of O(logn) processors, which contains a majority of good processors. In this paper, we give a synchronous algorithm which uses polylogarithmic time and Õ(vn) bits of communication per processor to bring all processors to agreement on a collection of n good quorums, solving Byzantine agreement as well. The collection is balanced in that no processor is in more than O(logn) quorums. This yields the first solution to Byzantine agreement which is both scalable and load-balanced in the full information model.

The technique which involves going from situation where slightly more than 1/2 fraction of processors are good and and agree on a short string with a constant fraction of random bits to a situation where all good processors agree on n good quorums can be done in a fully asynchronous model as well, providing an approach for extending the Byzantine agreement result to this model.

Fast Byzantine Leader Election in Dynamic Networks

We study the fundamental Byzantine leader election problem in dynamic networks where the topology can change from round to round and nodes can also experience heavy {\em churn} (i.e., nodes can join and leave the network continuously over time). We assume the full information model where the Byzantine nodes have complete knowledge about the entire state of the network at every round (including random choices made by all the nodes), have unbounded computational power and can deviate arbitrarily from the protocol. The churn is controlled by an adversary that has complete knowledge and control over which nodes join and leave and at what times and also may rewire the topology in every round and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is an $O(\log^3 n)$ round algorithm that achieves Byzantine leader election under the presence of up to $O({n}^{1/2 - \epsilon})$ Byzantine nodes (for a small constant $\epsilon > 0$) and a churn of up to \\$O(\sqrt{n}/\poly\log(n))$ nodes per round (where $n$ is the stable network size).The algorithm elects a leader with probability at least $1-n^{-\Omega(1)}$ and guarantees that it is an honest node with probability at least $1-n^{-\Omega(1)}$; assuming the algorithm succeeds, the leader's identity will be known to a $1-o(1)$ fraction of the honest nodes. Our algorithm is fully-distributed, lightweight, and is simple to implement. It is also scalable, as it runs in polylogarithmic (in $n$) time and requires nodes to send and receive messages of only polylogarithmic size per round.To the best of our knowledge, our algorithm is the first scalable solution for Byzantine leader election in a dynamic network with a high rate of churn; our protocol can also be used to solve Byzantine agreement in a straightforward way.We also show how to implement an (almost-everywhere) public coin with constant bias in a dynamic network with Byzantine nodes and provide a mechanism for enabling honest nodes to store information reliably in the network, which might be of independent interest.

L'hagiographie pataphysique : enjeux de l'ethos dans les Vies de Saints du Calendrier

RÉSUMÉ Forme littéraire développée dès les débuts du IVe siècle, l’hagiographie, plus tard sanctionnée par l’Église catholique romaine, se déploie avec tout le rituel et le décorum requis par le genre institué, dévoilant les modalités du savoir et du croire qui la distingue. Cette forme fixe fut réactivée, contre toute attente, dans une somme étoffée durant la seconde moitié du XXe siècle par le Collège de ‘Pataphysique, aréopage de philosophes, littérateurs et plasticiens, qui n’est pas un conclave d’excentriques, pas davantage qu’un nouvel « isme », mais une institution qui résolument emblématise la Science. Ce réemploi générique de l’hagiographie est caractérisé par une hétérogénéité bien peu canonique s’inscrivant dans une continuité problématique par rapport au sous-texte. Une première traversée du Calendrier inviterait à croire à une entreprise parodique et iconoclaste. La parodie, qui est aussi une imitation, pose un problème de visée. Le second degré de Gérard Genette implique deux grands régimes discursifs : le sérieux (le sérieux proprement dit et le satirique) et le ludique. Ces régimes nous ont été utiles pour arrimer la question de l’humour. Il y a là en somme deux possibilités, soit la parodie sérieuse conduisant à ridiculiser l’hagiographie et le Calendrier des Saints qui seraient sérieusement visés, néantisés, tournés en dérision; soit la parodie ludique, à portée nulle, simple jeu, farce farfelue, « pour rire ». Or, nous avons tenté de démontrer dans ce mémoire que, même s’il y a lieu d’avancer des arguments en faveur de l’un et de l’autre type de parodie, le partage ne fonctionne pas, précisément peut-être parce qu’il est possible de montrer à la fois que c’est sérieux et pas sérieux. Dans un troisième temps, on peut aussi faire la démonstration que le pas-sérieux est sérieux. Les jeux de mots, d’homophonie n’engagent-ils pas le Verbe? L’imitation impossible ne réfléchit-elle pas les imitabile de la Sainte Église? La situation énonciatrice tributaire de l’hagiographie pataphysique est non différentiable d’un souci de didactisme qui place la composante moralisatrice au centre des enjeux discursifs. Elle induit de ce fait des attentes en matière d’ethos consistant à mettre au même diapason une représentation sociale de l’énonciateur et une représentation intradiscursive au ton didactique. Elle adjoint un autre ton, savant celui-là, érudit, qui vient défaire la belle convergence et fait disjoncter la rhétorique du genre. Cette rhétoricité problématique de l’hagiographie pataphysique a été abordée sous l’angle de l’ethos. L’ethos est l’instance de validation par laquelle nous renvoyons non pas au caractère de l’orateur, mais, suivant en cela Dominique Maingueneau, au type de parole engendrée par le discours et qui, en retour, rend ce discours crédible. Que devient cette instance lorsque la visée persuasive du discours est remise en question, que l’ethos se démultiplie de façon hétérogène sans véritablement assurer la cohésion du propos ni garantir sa portée? La parodie posant incidemment un problème de visée, est-ce du côté d’un ethos parodique que se trouve la réponse? Il nous a convenu de mesurer, d’articuler, de déplacer cette postulation. Nous nous sommes saisi, pour les besoins de notre argumentation, d’une discipline historiquement lourde d’investissement théorique, soit la rhétorique. Celle-ci constitue à la fois une méthode de composition d’un discours reposant sur des lieux susceptibles de susciter l’adhésion et l’émulation de l’énonciataire et une méthode d’analyse. Guidé par une définition étendue du texte, traversant les littératures non narrative et narrative, il nous a importé enfin de restituer la pratique cymbaliste à partir d’un corpus qui est resté l’apanage du « seul » pataphysicien. Nous nous sommes ainsi situé dans l’horizon plus global de la réceptivité d’un discours qui évacue l’idéologique, qui jamais ne se laisse saisir tout à fait, ni enferrer par le fétiche du sens au profit des potentialités qu’il recèle, et cela à partir d’axiomes arbitraires soumis à l’unique exigence de cohérence interne.