Ph.D. Research Proposal Exam: Georgios Tsimos

Tuesday, April 2, 2024
1:00 p.m.
Maria Hoo
301 405 3681

ANNOUNCEMENT: Ph.D. Research Proposal Exam


Name: Georgios Tsimos



Professor Jonathan Katz (Chair)

Professor Dana Dachman-Soled

Professor Tudor Dumitraş

Date/time: April 2, 2024 at 1pm 


Location: (Online)


Title: Improving Round and Communication Metrics in Consensus


Byzantine Consensus protocols, aka Byzantine Agreement (BA), Byzantine Broadcast (BB), allow a set of n mutually distrusting parties to share input values and agree on the same output value. Notable practical applications of consensus in blockchains and MPC require efficient practical consensus protocols. To this end, in this research proposal we explore directions towards improving the two major metrics of efficiency of such protocols; i.e. their communication and round complexities.

In CRYPTO’22, we deployed gossiping techniques to provide randomized (Parallel) BB protocols with improved communication complexity, against both static and adaptive adversaries who can control the majority of participants. Namely, we proposed the first synchronous Parallel BB protocol against t < (1 − ε)n adaptive corruptions, with quadratic communication complexity. In a different result of the same paper, we provide an alternative protocol, in case fewer trust assumptions are preferable. 

In SODA’24, we showed the first synchronous deterministic strong BA protocol with O(n·f) adaptive communication complexity against an adaptive adversary, where f is the runtime number of corruptions. Our protocol incurs subquadratic communication in cases where the runtime number of corruptions is o(n), even if the corruption threshold t is O(n); in that case, the previous best-known result required quadratic communication independently of f.

Our results so far tackle communication complexity. In order to more holistically improve the practicality of consensus protocols, we propose to further attack research questions related to different aspects of efficiency such as: 1) improving the round complexity of synchronous BB protocols, 2) rendering communication-efficient BB protocols more practical and, 3) improving the concrete efficiency of existing deployed consensus protocols, also in asynchronous or partially synchronous settings.

Audience: Graduate  Faculty 

remind we with google calendar


April 2024

31 1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 1 2 3 4
Submit an Event