[Seminar] Efficient Deterministic Leader Election for Programmable Matter
Friday, February 17, 2023
3:00 pm - 4:00 pm
Speaker
Shay Kutten
(Technion, Israel)
Host
Gopal
Pandurangan
Location
PGH
232
Abstract
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
鈥減articles鈥,
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
鈥渃lose
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鈥檚
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鈥檚
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鈥檚
journal
on
Selected
Topics
in
Mobile
Networks
and
Applications
(MONET).
He
was
also
a
member
of
the
editorial
board
of
the
ACM鈥檚
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.
