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 .

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

Biography

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.

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.

Selected Publications. See copyright notice.

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

Research Publications

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.

Idit Keidar and S. Rajsbaum, "A Simple Proof of the Uniform Consensus Synchronous Lower Bound," in Information Processing Letters, Vol. 85, pp. 47-52, 2003.

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

A talk about what is theory of computation in Spanish.
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.
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:

Elements of Style by Strunk and White, Macmillan Publishing Co., New York, 1979. "you can read in a few hours. Your writing style will never be the same afterwards."
Guide to Grammar and Style by Jack Lynch
Advice for writing theses and papers by Ivan Stojmenovic
Writing a research paper in mathematics by Ashley Reiter based on "How to Write Mathematics," Steenrod, N.E. Steenrod, Amer. Math. Soc. 1983.
Some self-evident (yet often ignored) remarks about how to write a paper by Oded Goldreich.
How to Have Your Abstract Rejected - Mary-Claire van Leunen and Richard Lipton.

Technical information and resources:

CTAN, The Comprehensive TeX Archive Network, including style files (.sty and .cls files) and other TeX-related software
Using LaTeX to Create Quality PDF Documents for the World Wide Web by D.P. Story of the University of Akron
Recommendations for anyone who wants to use TeX/LaTeX to put scientific papers on the Web: Effective Scientific Electronic Publishing by Markus G. Kuhn
Latex and TeX Frequently Asked Questions, including format conversions, books, packages, etc.
Making a Compact Beautiful PostScript or PDF from a TeX Source
Creating PDF and PostScript files by Amir Herzberg including how to create a Postscript file using a Windows Wordprocessor
How to create a Postscript or PDF File including advise for Macintosh users

Events

I was coorganizer of the Taller de Vinculacion en Sistemas Distribuidos.
I was Local Arrangements Chair for PODC98.
I was coorganizer of the workshop Aspectos Combinatorios y Computacionales de Optimizacion, Topologia y Algebra, ACCOTA'96, ACCOTA'98, and ACCOTA'00, ACCOTA'06.
I was organizer of the Taller de Teoría de la Computación 2009 for the Computer Science Graduate School at UNAM.

Some links related to my research

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

Links to places

The Instituto de Matemáticas is one of the research institutes of UNAM, located in Mexico City, Mexico. Other related institutes of UNAM are the Instituto de Ingeniería and the Instituto de Investigación en Matemáticas Aplicadas y Sistemas (IIMAS). Teaching is done at the various departments or "Facultades". Some of the undergraduate Mathematics and Computer Science degrees are offered by the Facultad de Ciencias and the Facultad de Ingeniería. There is a graduate program in Computer Science and Engineering that offers Master's and PhD's, where various "facultades" and "institutos" participate.
Computer Science Department of Technion
Joanne Talbot , 617 253-6054, joanne@theory.lcs.mit.edu, is the Administrative Assistant of the Theory of Distributed Systems Group , part of the Theory of Computation Group at the MIT's Laboratory for Computer Science in Cambridge.
Cambridge Research Laboratory of HP (formerly of Digital then Compaq).
Centro de Estudios Martin Buber