BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:22d35898-a8bc-4771-aa9a-a8c47e175b77
X-WR-CALNAME:GT algodist - «Byzantine gathering in polynomial time»\, Sébas
 tien Bouchard\, LaBRI
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20251026T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20241027T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20240331T020000
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:22d35898-a8bc-4771-aa9a-a8c47e175b77
DTSTAMP:20260412T173649Z
CLASS:PUBLIC
DESCRIPTION:Sébastien Bouchard\, LaBRI\n\nTitre: Byzantine gathering in pol
 ynomial time.\n\nAbstract:\n\nGathering is a key task in distributed and m
 obile systems\, which becomes significantly harder if some agents are subj
 ect to Byzantine faults\, known as being the worst ones. We propose here t
 o study the task of Byzantine gathering in an arbitrary graph: despite the
  presence of Byzantine agents\, the goal is to ensure that all the other (
 good) agents\, executing the same algorithm\, eventually meet at the same 
 node and stop. Initially\, each agent gets as input a different label and 
 some global knowledge that is common to all agents. The agents move in syn
 chronous rounds and communicate with each other only when located at the s
 ame node. There are f Byzantine agents. These agents act in an unpredictab
 le way\, e.g.\, they may convey arbitrary information or forge any label. 
 In the literature\, the gathering algorithms working in such a context all
  have an exponential time complexity in the number n of nodes and the labe
 ls of the good agents. In this paper\, we design a deterministic algorithm
  to solve Byzantine gathering in time polynomial in n and the logarithm l 
 of the smallest label of a good agent\, provided the agents are a strong t
 eam i.e.\, a team where the number of good agents is at least some quadrat
 ic polynomial in f. Our algorithm requires global knowledge that can be co
 ded in O(log log log n) bits: we prove this size is of optimal order of ma
 gnitude to obtain a polynomial time complexity in n and l with strong team
 s.\n\n\n\nhttps://algodist.labri.fr/index.php/Main/GT
DTSTART;TZID=Europe/Paris:20231129T110000
DTEND;TZID=Europe/Paris:20231129T120000
LOCATION:LaBRI salle 178 - lien visio https://webconf.u-bordeaux.fr/b/arn-4
 tr-7gp
SEQUENCE:0
SUMMARY:GT algodist - «Byzantine gathering in polynomial time»\, Sébastien 
 Bouchard\, LaBRI
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
