Cette thèse a pour sujet les protocoles de communication peer-to-peer asynchrones. Nous introduisons deux mesures basées sur la théorie de l'information,la Public Information Complexity (PIC) et la Multi-party Information Complexity (MIC), étudions leurs propriétés et leur relation avec d'autres mesures fondamentales en calcul distribué, telles que la communication complexity et la randomness complexity. Nous utilisons ensuite ces deux mesures pour étudier la fonction parité et la fonction disjointness. / This thesis is concerned with the study of multi-party communicationprotocols in the asynchronous message-passing peer-to-peer model. We introducetwo new information measures, the Public Information Complexity(PIC) and the Multi-party Information Complexity (MIC), study their propertiesand how they are related to other fundamental quantities in distributedcomputing such as communication complexity and randomness complexity.We then use these two measures to study the parity function and the disjointness function.
| Identifer | oai:union.ndltd.org:theses.fr/2018USPCC015 |
| Date | 25 May 2018 |
| Creators | Urrutia, Florent |
| Contributors | Sorbonne Paris Cité, Kerenidis, Iordanis |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation, Text, Collection |
Page generated in 0.1957 seconds