Paris Kanellakis

in Memoriam

Paris Kanellakis joined the Computer Science Department in 1981 and became a full professor in 1990. His research area was theoretical computer science, with emphasis on the principles of database systems, logic in computer science, the principles of distributed computing and combinatorial optimization. He died in an airplane crash on December 20, 1995, along with his wife, Maria Teresa Otoya, and their two young children, Alexandra and Stephanos Kanellakis.

History
Lectures
Symposium
Campaign
Staff
IPP 15th
Kanellakis
Research
conduit!
BB

25th Home

Paris Kanellakis Lecture Series

Progress in System Modeling and Testing
As software systems become larger and more complex, it becomes that much harder to design and test them to ensure their correct functioning. This is especially the case for control-oriented systems such as communications systems. In this talk we will present some of the work we have been doing in recent years to help in this task. The approach involves the formal modeling of requirements and systems, and the development of algorithms for their analysis, and for the automated generation of effective tests.

Algorithmic Aspects of the Internet

The Internet is the first computational artifact that was not designed by a single entity, but emerged from the complex interaction of many. Hence, it must be approached as a mysterious object, akin to the universe and the cell, to be understood by observation and falsifiable theories. Game theory plays an important role in this endeavor, since the entities involved in the Internet are in various and varying degrees of collaboration and competition.

We survey work in progress considering the Internet and its protocols as equilibria in appropriate games, and striving to explain phenomena such as the power law distributions of the degrees of the Internet topology in terms of the complex optimization problems aced by each node.

Nancy Lynch, MIT

Talk to be given by Alex Shvartsman

Reconfigurable Atomic Networks for Dynamic Systems

We describe recent work on algorithms to implement atomic operations on shared objects in a dynamic network setting. A key component of this work is the RAMBO algorithm (Reconfigurable Atomic Memory for Basic Objects) that can be tailored to run in many settings, including peer-to-peer networks and mobile ad hoc networks. Long-lived data availability is ensured through replication. Atomicity is ensured by performing reads and writes using “quorum configurations,” sets of members and sets of read/write-quorums.  We show that RAMBO is reconfigurable without violating atomicity and that it tolerates processor and link failures.

RAMBO concurrently (1) reads and writes objects, (2) chooses new configurations and notifies members, and (3) identifies and removes (“garbage-collects”) obsolete configurations. Atomicity, the main safety property of RAMBO, holds for arbitrary patterns of asynchrony. RAMBO's performance depends on failure and timing assumptions. Under reasonable assumptions, we show that read and write operations complete within a time proportional to the maximum message latency. We also discuss the “Geoquorums algorithm” that implements atomic memory in mobile ad hoc networks using an abstract computing platform consisting of virtual machines associated with fixed geographical locations. Mobile nodes implement the virtual machines, using a replicated state machine strategy.< Joint work with Alex Shvartsman, Seth Gilbert, Shlomi Dolev, and Jennifer Welch.