Serdecznie zapraszamy wszystkich na seminarium wydziałowe pt. „Quantum advantage for fully distributed leader election on a ring”, które wygłosi nasz gość z Australii prof. Amitava Datta. Seminarium odbędzie się w poniedziałek 10 grudnia o godzinie 12:15 w sali 3/40. Poniżej znajdą Państwo streszczenie.

Leader election is one of the most fundamental problems in distributed computing. We consider this problem in one of the simplest distributed systems, a ring of processes, which are connected through uni-directional or bi-directional communication links. The leader election problem is to identify one of the processes as the leader in the ring when each process executes an identical algorithm. Leader election is often the starting point for executing other distributed algorithms. There are different models for leader election. The processes do not have any id in the anonymous model, and have ids in a non-anonymous model. Processes execute the steps of their algorithms one after another according to their ordering on the ring in the synchronous model, and in arbitrary order in an asynchronous model. The ring is called uniform if the number of processes on the ring or an upper bound is known to each process, and non-uniform if each process does not know anything about the total number of processes on the ring. It is known that there is no synchronous, non-uniform algorithm for leader election if the processes are anonymous. The most general setting for this problem is an asynchronous, anonymous, non-uniform and uni-directional ring. We show that it is possible to solve this most general setting of this problem by using quantum resources, in particular when the processes share multi-particle quantum entanglements. I will explain the basics of quantum mechanics and quantum entanglement that will be sufficient for understanding the algorithm. No prior background in quantum computing will be assumed.