Sergio Rajsbaum's Personal
Home Page
Instituto de Matematicas, Universidad
Nacional Autonoma de Mexico (UNAM)
Ciudad Universitaria, D.F. 04510
Mexico
Voice: +(52-55) 5622 4492, 4520, 4526
Fax: +(52-55) 5616 0348
rajsbaum@matem.unam.mx
This page: http://www.matem.unam.mx/~rajsbaum
.
Contents
- Biography
- Publications:
Research, Others (talks, surveys,
SIGACTNews Distributed Computing Columns, etc)
- Teaching
- Technical
writing advise and resources
- Events
- Some
links related to my research
- Links
to places
I was born in Mexico
City, Mexico
in 1962. My son is Oliver.
I received a degree in Computer Engineering from the National
Autonomous University of Mexico (UNAM)
in 1985, and a PhD in the Computer Science
Department at the Israeli Institute of Technology-Technion in 1991, under the supervision of
Shimon Even.
In 1991 I joined the Institute
of Mathematics at UNAM, where I am currently a Professor
(Investigador Titular "C"). Also, I am SNI nivel
III. I was a visiting scientist at the Laboratory for Computer Science
of MIT 1993-1995, in the Theory of Distributed
Systems Group of Nancy Lynch. As
part of this post-doctoral stay, I also visited the Cambridge Research
Laboratory of HP (formerly Digital and then Compaq). I was
a Research Staff member there from September 1999 to September
2002, on Sabbatical leave.
My research interests are in the
theory of distributed computing, especially issues related to
coordination, complexity and computability. I am also interested
in graph theory and algorithms. I teach
courses on all of these subjects. I have been a Program Committee member of various
international conferences. I was Local Arrangements Chair
for PODC98. I was
chair of the program committee for Latin American Theoretical
Informatics LATIN02,
for PODC03, and for
ENC06. I have been
Steering Committee member of: DISC, LADC, LATIN, PODC. I was an invited speaker
for the 24th Mathematical Foundations of Computer Science
Conference MFCS99,
for the 9th Latin American Theoretical Informatics Symposium LATIN2010,
for the Congreso Iberoamericano de Seguridad Informática
CIBSI2011, and for
the 9th International Conference on Electrical Engineering,
Computing Science and automatic Control CCE2012.
I ran the Distributed
Computing
Column of SIGACT
News, the newsletter for SIGACT, the ACM Special Interest Group on
Algorithms and Computation Theory, from December 2000 until
September 2007.
Since then the column is edited by Idit Keidar.
My genealogy,
within all the mathematicians of the world, where my ancestors
and descendants can be found. My Erdös number
is 2 because I am coauthor of Shlomo Moran,
who is coauthor of Paul
Erdös.
List
of publications from the
Collection
of Computer Science Bibliographies
List
of publications from the
DBLP
Bibliography
Server
List
of publications with citations from
Google Scholar
List
of publications and
citations
from
CiteSeer
List
of publications from
MathSciNet
List
of publications from
Graph
Theory
- Armando Castañeda and S.
Rajsbaum, "New Combinatorial Topology
Upper and Lower Bounds for Renaming." Extended
Abstract in ACM PODC 2008, Best Student Paper Award. Full
version: Publicación Preliminar del Instituto de
Matemáticas, Universidad Nacional
Autónoma de México (UNAM), June 9, 2008.
- Achour Mostefaoui, S. Rajsbaum,
Michel Raynal, "Synchronous
condition-based consensus," to appear in Distributed Computing.
Journal version of DISC 2003 and DISC 2004 papers.
- Eli Gafni and S. Rajsbaum,
"Musical Benches," Lecture
Notes in Computer Science 3724, Springer Verlag,
Pierre Fraignaud (Ed.), pp. 63-77: 19th International
Symposium on Distributed Computing (DISC), Cracow, Poland,
September 26-29, 2005.
- Achour Mostefaoui, S. Rajsbaum,
Michel Raynal, "The Combined
Power of Conditions and
Failure Detectors to Solve
Asynchronous Set Agreement," in the 24th ACM Symposium on
Principles of Distributed Computing (PODC), July 17-20,
2005, Las Vegas, Nevada, pp. 179-188.
- Pierre Fraigniaud, David
Ilcinkas, S. Rajsbaum, and Sébastien Tixeuil, "An Ω(log n) space lower bound for graph
exploration with stop (Extended Abstract)," Lecture Notes in Computer
Science 3499, Springer Verlag, Andrzej Pelc and
Michel Raynal (Eds.), pp. 140-154: 12th Colloquium on
Structural Information and Communication Complexity
(SIROCCO), May 24-26, 2005, Le Mont Saint-Michel, France. Based on this, a chapter
will be published in A
Book in Memory of Shimon Even, Springer's
LNCS Festschrift
series (as Vol 3895, to appear in Spring 2006).
- Paul Attie, Rachid Guerraoui,
Petr Kouznetsov, Nancy Lynch, and S. Rajsbaum, "The Impossibility of Boosting
Distributed Service Resilience,'' in the proc. of the
25th IEEE Int. Conference on Distributed Computing Systems,
Columbus, Ohio, June 6-10, 2005, pp. 39-48.
- Lior Davidovitch, Shlomi Dolev,
and S. Rajsbaum, "Consensus continue? Stability of
multi-valued continuous consensus!" in Preliminary
Proceedings of the Workshop on Geometry and Topology in
Concurrency and Distributed Computing (GETCO 2004),
Amsterdam, The Netherlands, October 4, 2004, pp. 21-24. P.
Cousot, L. Fajstrup, E. Goubault, M. Herlihy, M.
Raußen, V. Sassone (Eds.) BRICS Notes Series NS-04-2,
September 2004, ISSN 0909-3206.
- Maurice Herlihy, S. Rajsbaum,
and Mark Tuttle, "An axiomatic approach to computing the
connectivity of synchronous and asynchronous systems,"
in Preliminary Proceedings of the Workshop on
Geometry and Topology in Concurrency and Distributed
Computing (GETCO 2004), Amsterdam, The Netherlands, October
4, 2004, pp. 5-20. P. Cousot, L. Fajstrup, E. Goubault, M.
Herlihy, M. Raußen, V. Sassone (Eds.) BRICS Notes
Series NS-04-2, September 2004, ISSN 0909-3206.
- Achour Mostefaoui, S. Rajsbaum,
Michel Raynal, "The Synchronous Condition-Based
Consensus Hierarchy,'' Lecture
Notes in Computer Science #3274, Springer Verlag,
pp. 1-15: 18th International Symposium on Distributed
Computing (DISC), Amsterdam, Netherlands, October 4-7, 2004.
- Achour Mostefaoui, S. Rajsbaum,
Michel Raynal, "Using Conditions to Expedite Consensus
in Synchronous Distributed Systems,'' Lecture Notes in Computer
Science #2848, Springer Verlag, pp. 249-263: 17th
International Symposium on Distributed Computing (DISC),
Sorrento, Italy, October 1-3, 2003.
- Elisa Viso, S. Rajsbaum,
"Object-oriented algorithm analysis and design with Java,"
in Science of Computer
Programming, 54(1): 25-47 (2005), Elsevier.
Preliminary version in 2nd ACM International Conference on
the Principles and Practice of Programming in Java
(PPPJ), Kilkenny City, Ireland, June 16-18, 2003, pp.
79--83.
- Roy Friedman,
Achour Mostefaoui, S. Rajsbaum, Michel Raynal,
"Distributed Agreement and its Relation with
Error-Correcting Codes," in Dahlia Malkhi (Ed.) Lecture
Notes in Computer Science #2508, Springer Verlag,
pp. 63-87: 16th International Symposium on Distributed
Computing (DISCbefore WDAG), Toulouse, France, Oct. 28-30,
2002.
- Achour Mostefaoui, S. Rajsbaum, Michel
Raynal, Matthieu Roy, "Condition-Based Protocols for Set
Agreement Problems," in Dahlia Malkhi (Ed.) Lecture
Notes in Computer Science #2508, Springer Verlag, pp.
48-62: 16th International Symposium on Distributed Computing
(DISCbefore WDAG), Toulouse, France, Oct. 28-30, 2002.
- Achour Mostefaoui, S. Rajsbaum,
Michel Raynal, "A Versatile and Modular Consensus Protocol,"
IEEE International Conference on Dependable Systems and
Networks (DSN), Washington, DC, June 23rd - 26th, 2002.
- Maurice Herlihy, S. Rajsbaum, Mark Tuttle, "A
New Synchronous Lower Bound for Set Agreement,'' in Jennifer
L. Welch (Ed.) Lecture Notes in Computer Science # 2180,
Springer Verlag, pp. 136-150: 15th International Symposium
on Distributed Computing (DISCbefore WDAG), Oct. 3-5, 2001
- Achour Mostefaoui, S. Rajsbaum, Michel
Raynal, Matthieu Roy, "Efficient Condition-Based Consensus,"
8th International Colloquium on Structural Information and
Communication Complexity (SIROCCO), Vall de Núria,
Catalonia, Spain, June 27-29, 2001; Proc. in Informatics 11,
Francesc Comellas, Josep Fabrega, and Pierre Fraigniaud
(Eds.),Carleton Scientific Press, pp. 275-293.
- Achour Mostefaoui, S. Rajsbaum, Michel
Raynal, Matthieu Roy, "A Hierarchy of Conditions for
Consensus Solvability," 20th ACM Symposium on Principles of
Distributed Computing (PODC), August 26-29, 2001,
Newport, Rhode Island, pp. 151-160. Journal version
"Condition-Based Consensus Solvability: a Hierarchy of
Conditions and Efficient Protocols,'' Distributed Computing.
Vol. 17, No. 1, 2004, pp. 1--20.
- Achour Mostefaoui, S. Rajsbaum, Michel
Raynal, "Conditions on Input Vectors for Consensus
Solvability in Asynchronous Distributed Systems," in 33rd
ACM Symp. on the Theory of Computation (STOC), July
2001, pp. 153-162. Journal version in J.
ACM 50(6): pp. 922-954, 2003.
- S. Dolev, S. Rajsbaum, "Stability of Long-lived Consensus,"
in Proc. 19th ACM Symposium on Principles of Distributed
Computing (PODC), p. 309-318, July 2000. Journal version in J. of Computer and System
Sciences, Vol. 67, Num. 1, August 2003, pp.26--45.
- Y. Dinitz, S. Moran, S. Rajsbaum,
"Exact Communication Costs for
Consensus and Leader in a Tree," 7th International
Colloquium on Structural Information and Communication
Complexity (SIROCCO), June 2000, in: Proc. in Informatics
7, M. Flammini, E. Nardelli, and P. Spirakis (Eds.), Carleton
Scientific Press, p. 63-77. Journal version in J. of Discrete Algorithms,
Vol. 1, Num. 2, April 2003, pp. 167-183.
- S. Rajsbaum, J. Urrutia, "Some Problems in Distributed
Computational Geometry," 6th International Colloquium on
Structural Information and Communication Complexity (SIROCCO),
July 1999, in: Proc. in Informatics 5, C. Gavoille,
J-C. Bermond, A. Raspaud (Eds.), Carleton Scientific Press, p.
233-248. To appear in Theoretical Computer Science.
- Y. Dinitz, S. Moran, S. Rajsbaum,
"Bit Complexity of Breaking and
Achieving Symmetry in Chains and Rings." in Proc. 31st
ACM Symp. on the Theory of Computation (STOC), p. 265-274, May
1999.
- M. Herlihy, S.
Rajsbaum, "A Wait-Free
Classification of Loop Agreement Tasks," 12th
International Symposium on Distributed Computing (DISC,
formerly WDAG), Sept. 1998, Abstract, in: Lecture Notes in
Computer Science 1499, Springer Verlag, p. 175-185. To
appear in Theoretical Computer Science.
- Y. Moses, S. Rajsbaum,
"A Layered Analysis of Consensus," SIAM
J. on Computing, Vol. 31, No. 4, pp. 989 - 1021, 2002.
Preliminary version in "The
Unified Structure of Consensus: a Layered Analysis
Approach," Proc. 17th ACM Symposium on Principles of
Distributed Computing (PODC), p. 123-132, June 1998.
- M. Herlihy, S. Rajsbaum, M.
Tuttle, "Unifying Synchronous and
Asynchronous Message-Passing Models," Proc. 17th ACM
Symposium on Principles of Distributed Computing (PODC), p.
133-142, June 1998.
- M. Herlihy, S. Rajsbaum, "On the Decidability of Distributed
Decision Tasks," Proc. 29th ACM Symp. on the Theory of
Computation (STOC), p. 589-598, May 1997.
- H. Attiya, S.
Rajsbaum, “The Combinatorial Structure of
Wait-Free Solvable Tasks,” SIAM
J. on Computing, Vol. 31, No. 4, pp. 1286 - 1313, 2002.
A preliminary version appeared as “A
Combinatorial Framework for Wait-free Computability,” Lecture
Notes in Computer Science, 1151, p. 321-343, Springer
Verlag: Proc. 10th International Workshop on Distributed
Algorithms (WDAG), Oct. 9--11, 1996.
- E. Borowsky,
E. Gafni, N. Lynch, S. Rajsbaum, “The
Borowsky-Gafni Simulation Algorithm,” in
Distributed Computing, Vol. 14, No. 3, July 2001.
- S. Even, G. Itkis, S. Rajsbaum, “On
Mixed Connectivity Certificates,” Theoretical
Computer Science, Vol. 203, No. 2, August 1998, pp.
253-269.
- M. Herlihy, S. Rajsbaum, “Algebraic Spans,”
Mathematical Structures in Computer Science, Vol.
10, Issue 4, 2000, pp. 549-573.
- M. Herlihy, S. Rajsbaum, "Set Consensus Using Arbitrary Objects," Proc.
13th ACM Symposium on Principles of Distributed Computing
(PODC '94), pp. 324-333, 1994.
- B. Patt-Shamir, S. Rajsbaum, “A Theory of Clock Synchronization,” Proc.
26th ACM Symp. on the Theory of Computation (STOC), pp.
810--819, 1994.
- H. Attiya, A. Herzberg, S.
Rajsbaum, “Optimal Clock
Synchronization under Different Delay Assumptions,” SIAM
Journal on Computing, Vol. 25, No. 2, pp. 369--389, April
1996.
- H. Galeana--Sanchez, S. Rajsbaum,
“Cycle Pancyclism in Tournaments,” Graphs and Combinatorics, Part I in vol. 11, 1995, pp. 233-243;
Part II in vol. 12, 1996, pp. 9-16; Part III in vol. 13, 1997, pp. 57-63.
In Discussiones Mathematicae--Graph Theory A Conjecture on ... in vol. 18, 1998,
pp. 243-251.
- S. Rajsbaum, “Upper and Lower Bounds for Stochastic
Marked Graphs,” Information Processing Letters, 49
(1994) pp. 291--295.
- S. Rajsbaum, M. Sidi, “On the Performance of Synchronized
Programs in Distributed Networks with Random Processing
Times and Transmission Delays,” IEEE Trans. on Parallel
and Distributed Systems, Vol. 5, No. 9, Sept. 1994, pp.
939--950.
- S. Even, S. Rajsbaum, “The Use of a Synchronizer Yields Maximum
Computation Rate in Distributed Networks,” Theory of
Computing Systems, Vol. 30, 1997, pp. 447--474. Extended
Abstract in 22nd ACM Symp. on the Theory of Computation
(STOC), 1990, pp. 95-105.
- S. Even, S. Rajsbaum, "Unison,
Canon,
and
Sluggish
Clocks
in Networks Controlled by a Synchronizer," Mathematical
Systems Theory, Vol. 28, 1995, pp. 421-435.
- Y. Malka, S. Rajsbaum, “Analysis of
Distributed Algorithms based on Recurrence Relations,” in S.
Toueg, P.G. Spirakis, L. Kirousis, (Eds.) Lecture Notes
in Computer Science 579, Springer Verlag, pp. 242-253:
5th Int. Workshop on Distributed Algorithms (WDAG), Delphi,
Greece, Oct. 7-9, 1991.
Talks,
Surveys and Other Publications
- Two stories about love
(A topological perspective on distributed computing) for Luis
Montejano’s 60th birthday, presented in Convexity, Topology
and beyond, Puerto Vallarta, October 2011.
- Recursion in
distributed computing, including join results with Eli
Gafni from SIROCCO 2010 and OPODIS 2010.
- Talks about what is theory of
computation (Spanish) (2009), and an introduction to
computer science and recursion(Spanish) (French)
for non-technical people of all ages using Towers of Hanoi
(2010).
- Presentation
(pdf in Spanish) at the Congreso 50
Años de la Computación en México,
Palacio de Minería, Ciudad de México, 12 al 14
de noviembore 2008.
- Presentation
(pdf in Spanish) for the Computer Science book of the series Conocimientos
Fundamentales
para la Enseñanza Media Superior del CAB: Una propuesta de la
UNAM para su bachillerato, Computación dentro
del Libro Azul.
- I was editor of the ACM
SIGACT News
Distributed Computing Column. See now the columns
of the new editor, Idit Keidar.
- Idit Keidar and S. Rajsbaum, Open
Questions
on
Consensus
Performance
in Well-Behaved Runs. In Future Directions in
Distributed Computing, Lecture Notes in Computer Science
Volume 2584, pages 35-39.
- Roy
Friedman, Achour Mostefaoui, S. Rajsbaum, Michel Raynal,
"Error-Correcting Codes: A Future Direction to
Solve Distributed Agreement Problems?" in
Workshop on Future Directions in Distributed Computing,
June 2002, Bertinoro, Italy.
- Idit
Keidar and S. Rajsbaum, "On the Cost of Fault-Tolerant
Consensus When There Are No Faults - A Tutorial," MIT
Technical Report MIT-LCS-TR-821, May 24 2001. Preliminary
version in SIGACT News 32(2), Distributed
Computing Column, pp.45-63, June 2001. Download from Idit's tutorial
page . One
part of this in Information Processing Letters
85(1), pages 47-52, January 2003, as "A Simple Proof of the Uniform
Consensus Synchronous Lower Bound."
- M. Herlihy, S. Rajsbaum, " New
Perspectives in Distributed Computing," Lecture Notes in
Computer Science 1672, Springer Verlag, 1999, p.
170-186, M. Kutylowski, L. Pacholski, T. Wierzbicki (Eds.):
Invited lecture to 24th International Symposium on
Mathematical Foundations of Computer Science (MFCS), Sept.
6-10, 1999. Paper. Abstract.
- S. Rajsbaum, “Breve Introduccion a
Criptografia y Seguridad,”
Publicaciones Preliminares 631, March 1999, Instituto de
Matematicas, UNAM, in Soluciones Avanzadas.
- S. Rajsbaum, "Dos Perspectivas del
Lema de Sperner," Carta Informativa, Sociedad Matematica
Mexicana, num. 17, June 1998, pp. 1-3.
- Ricardo Marcelin, S. Rajsbaum, “Un curso de principios
de computacion distribuida,”
Memorias del V Congreso Iberoamericano de Educacion Superior
en Computacion, Ciudad de Mexico, UNAM, 19-21 Sept. 1996,
pp. 203-211.
- M. Herlihy, S. Rajsbaum, "A Primer on Algebraic Topology and
Distributed Computing," Lecture Notes in Computer
Science, Vol. 1000, pp. 203-217, 1995.
Teaching (links in
Spanish)
Advice
for writing theses and papers by Ivan Stojmenovic
My former students.
I teach the following computer
science courses in UNAM, for graduate and undergraduate
students.
Technical writing advise and resources
Style:
Technical information and resources:
- Distributed
Algorithms
and Systems
- I have been using topological
methods to study distributed computing, from the complexity
and computability point of view; see the survey "New
Perspectives in Distributed Computing" cited above. A survey
of work in this area including the semantics point of view
is Geometry and
Concurrency by Eric Goubault.
The second workshop organized on the subject was in 2000,
Geometric and Topological Methods in Concurrency GETCO.
- Topology Atlas.
A multi-purpose center for electronic distribution of
information related to topology, a comprehensive attempt to
create a "global village" in topology.
- Links to
lecture
notes, surveys, and papers
maintained by the Theoretical Computer Science group of
the University of Paderborn.
- Parallel and
Distributed Algorithms of the GI
Special Interest Group 0.1.3
- Bibliographies on
Distributed Computing and Networking.
- Clock Synchronization: bibliography,
the U.S. Naval
Observatory Master Clock.
- Petri Nets.
- ACM Calendar of
Events.
- Computer Science
Research Index. Links to: General
Computer Science Professional Societies, Computer Science
Departments, Non-University Sites, Job Ads, Bibliographic
Services, Specific Areas, etc.
- Theoretical Computer
Science On The Web. Pointers to
papers and pages of general interest to the theory
community, theory related software available on the net,
upcoming conferences and attendees of previous conferences,
the genealogy of theoretical computer scientists, and some
other assorted stuff, maintained at Stanford.
- Theoretical Computer Science History
excerpted by Kirk Pruhs in part from a CS History written
by Jeffrey Shallit with pointers to other Web Resources for
History of Computer Science.
- Graphs: Theory - Algorithms - Complexity.
Related link collections, online forums, open problems,
software, books and lecture notes, people, etc.
- Computer
Museum of the University
of Virginia with many nice pictures
- The Virtual
Museum of Computing