Keynote talk I

I- Tasks, objects, and the notion of a distributed problem

Sergio Rajsbaum Universidad Nacional Autonoma de Mexico

Biography:
Sergio Rajsbaum received a degree in Computer Engineering from the National Autonomous University of Mexico (UNAM) in 1985, and a PhD in the Computer Science from the Technion, Israel, in 1991. Since then he has been a faculty member at the Institute of Mathematics at UNAM. His research interests are in the theory of distributed computing, especially issues related to coordination, complexity and computability. He has also worked in graph theory, algorithms, and content management systems. He has published over 100 papers and book on the use of topology for a distributed computing theoretical foundation, a topic on which he is one of the world leading experts.

Abstract:

This is joint work with Armando Castañeda and Michel Raynal.

The universal computing model of Turing, which was central to the birth of modern computer science, identified also the essential notion of a problem, as an input output function to be computed by a Turing machine. In distributed computing, \emph{tasks} are the equivalent of a function: each process gets only part of the input, and computes part of the output after communicating with other processes.
In distributed computing tasks have been studied from early on, in parallel, but independently of \emph{sequential objects}. While tasks explicitly state what might happen when a set of processes run concurrently,  sequential objects only specify what happens when processes run sequentially. Indeed, many distributed problems considered in the literature, seem to have no natural specification neither as tasks nor as sequential objects. I will concentrate on our recent work on interval-linearizability, a notion we introduced to specify objects more general than the usual  sequential objects. I will describe the bridges we establish between these two classical paradigms, and our discussions about what is a distributed problem, and what it means  to solve it.