Calendar - University of Houston
Skip to main content

[Seminar] Efficient Deterministic Leader Election for Programmable Matter

Friday, February 17, 2023

3:00 pm - 4:00 pm


Shay Kutten

(Technion, Israel)

Gopal Pandurangan

PGH 232


The notion of programmable matter [Toffoli and Margolus 1993] and specifically, Ameobots [Derakhshandeh, Richa, Dolev, Scheideler, Gmyr and Strothmann 2014] envisions matter as being composed of tiny weak robots called “particles”, each with no unique identity, very limited memory size and very limited abilities for movement, computation, environment sensing, and communication. At the same time, hardware researchers in various places have been developing such particles. Multiple studies have been addressing how entities who are that weak can even cooperate and what they can achieve by cooperation. See e.g. work on coating of objects (for protection and for coloring) and forming bridges.

An important primitive used often for coordinating such tasks is the election of a unique leader.
Given leader election as a building block, it is known that various tasks in programmable matter can be performed, or improved. Interestingly, in the past, deterministic algorithms either elected multiple co-leaders in cases of symmetrical shapes of the programmable matter, or relied on various assumptions on the particles, such as initially forming a specific shape (no holes), or initially sharing a common chirality.
We show that the common definition of a scheduler for the Ameobot model, together with the movement ability of the particles, allow the development of deterministic leader election algorithms in spite of impossibility results presented in the past for other models. Let us note that previous leader election algorithms have not exploited movements. Also, previous Ameobot algorithms in general have not allowed the programmable matter to ever get disconnected (where a graph is defined with the particles as nodes and two particles are neighbors if they are “close to each other”). We show that by allowing the matter to disconnect temporarily, the time complexity of deterministic leader election algorithms becomes as low as that of known probabilistic algorithms.

This talk is based on papers with Fabien Dufoloun, Yuval Emek, Ron Lavi, and William Moses Jr. [ICALP’19],[PODC21].

About the Speaker

Professor Shay Kutten holds the William M. Davidson Chair in Industrial Engineering and Management at the Technion – Israel Institute of Technology in Haifa, Israel. He received his PhD in Computer Science from the Technion in 1987. From 1987 to 2000 he was with IBM T.J. Watson Research Center, as a post-doctoral fellow, as a project leader, as the manager of the Network Architecture and Algorithms group and of Distributed Systems Security, and as a Research Staff Member.He led the network security project which developed the security architecture for several IBM products, and developed algorithms for network control, security, and distributed processing control, that were later used in IBM’s products. He received (in 1993) the IBM Corporation Outstanding Innovation Award (OIA) for his work on distributed control protocols that were basis to the distributed control of IBM Broad Band Networking Services architecture, NBBS. In 1994 he received the IBM Outstanding Innovation Award (OIA) for his work on authentication protocols and his contributions to IBM’s network security and NetSP (by itself an award winning product). The same authentication protocols influenced the later development of the Internet payment protocol, so IBM had to grant a no-fee license, so that the Internet can adopt this payment protocol.

Prof. Kutten also contributed to the theory of distributed computing, mostly by introducing new theoretical subjects, many of them inspired by his work on practical issues, and by giving well founded solutions to practical problems. His early work was probably the first algorithmic treatment of radio networks protocol, and introduced a theoretical model that allowed such treatment by many following studies.

His publications have been cited more than 9500 times with an h-index of 45 (Google Scholar).

At the Technion, he was the head of the Information Systems area of the Davidson Faculty of IE&M and the coordinator of undergraduate studies of the faculty of IE&M. He won the Taub Award for excellence in research, and the Mitchner Award for research on Quality Sciences and Quality Management. He is an area editor (for security, reliability, and availability) of the ACM’s journal on Selected Topics in Mobile Networks and Applications (MONET). He was also a member of the editorial board of the ACM’s Wireless Networks and of the Elsevier journal Computer Networks. He was the chair of the program committee of the 1998 DISC conference and of the 2004 ACM PODC conference. He is a senior member of the IEEE.