Technion web site Industrial Engineering and Management  
Hebrew     English
 
Home Faculty Research Courses & Programs Students Library Alumni About Us
 
 

Professor Shay Kutten

 
 
General Information
Shay Kutten received his Master degree (on "scheduling of radio broadcasts", receiving the Gutwirth Fellowship) and his PhD ("on distributed network algorithms", receiving the fellowship of the Chief Scientist in the Ministry of Communication in Israel) in Computer Science from the Technion, Israel, in 1984 and 1987 respectively. 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's 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's 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. 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's journal on Selected Topics in Mobile Networks and Applications (MONET). He was also a member of the editorial board of the ACM's Wireless Networks and of the Elsevier journal Computer Networks. He served on program committees for several conferences and workshops, was the chair of the program committee of the 1998 DISC conference and of the ACM PODC'04 conference, was awarded several additional awards and research grants, and published extensively in scientific journals and in refereed conferences. He is a senior member of the IEEE, and a member of ACM-SIGACT.


Calculating Citations Impact (e.g. H-Index).


CV (February 2008).


Research statement (October 2007).

 
 
Research Summary
Prof. Shay Kutten (SM' 96) Research has concentrated on protocols, modeling and architectural design for communication networks and distributed systems. In particular he concentrated on using theory in order to obtain practical systems and solutions. Most of the theory utilized in communication research until recently, came from fields that were traditionally associated with Electrical Engineering. The research of Dr Kutten has been concentrated on utilizing Computer Science.

This led to his work on modeling the new generation of networks: the broadband networks, and to the membership in the first team that designed IBM NBBS (this is IBM's ATM), utilizing this model, as well as protocols Dr. kutten with others designed for the network. This approach of applying theory of computer sceince to practice also led to founding and leading the network security project in IBM T.J. Watson Research center, including detecting security problems in established standards, modeling what correct protocols should provide, and designing and proving the correctness of protocols to replaced the erroneous ones. This included the design of several IBM security products (e.g.) and parts of products, as well as consulting to IBM units about networks and distributed systems security. The Internet payment protocol is based, to a large degree, on a protocol patented by Dr. Kutten and others in this project, so that IBM had to grant a royalty free license for this patent for the Internet to adopt this protocol. In IBM, Dr. Kutten also contributed to group services , a key piece of clustering technology in IBM's SP line of computers.

Theoretical research subjects include:
Dynamic Networks, including the design of the first optimal algorithms the heavily investigated problem of learning and adjusting to the changing topology of the network
multicasting, including the design of the , multicast protocol of IBM NBBS,
distributed fault tolerance and distributed Self Stabilization, including the the introduction of the Local Detection paradigm , the first algorithm for spanning tree construction in general dynamic networks (and thus for derived tasks, such as token passing and reset), self stabilizing synchronization and the notion of scalable fault tolerance in the form of Fault Locality and Tight Fault Locality; for his work on fault tolerance, Shay Kutten received the Michner Second Award in Quality Sciences and Quality Management;
distributed scheduling,
message routing,
Leader Election , including a modular technique to solve the problem efficiently in different networks, taking advantage of the network special properties in a modular way, and including the introduction of the programming paradigm of programming the mobile process, instead of programming the nodes, and
wireless networks.

 
 
Current Research Projects

(Selected Current Research Projects)

  • Distributed Algorithms

  • Peer to Peer applications and computing

  • Electronic Commerce

  • Wave Division Multiplexing Networks

  • Scalability of Distributed Fault Tolerance, and Faulg Isolation

  • Internet Search, interaction, and efficiency

 
 
Selected Publications
Copyrights for some of the papers below have been transferred, or will be transferred to various publishers of journals, conferences proceedings, etc. For such papers I am required to post the following notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons Copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be re-posted without the explicit permission of the copyright holder. In the case that a paper appeared in a conference or a journal, the original can be found in the jorunal, or the proceedings, or the Web site of the publisher, and the version here is a prepress (or, in some cases, an expanded version). More information can be found e.g. in the IEEE Copyrights Policies , the ACM Interim Copyright Policy , the SIAM Copyright Assignment Agreement, or see Elsevier's copyrights policy, Springer copyrights form, Kluwer's (Springer) copyrights policy etc.

  1. I. Chlamtac and S. Kutten, "On Broadcasting in Radio Networks: Problem Analysis and Protocol Design", IEEE Transactions on Communications, Vol. COM-33, No. 12, December 1985.

  2. I. Chlamtac and S. Kutten: "A Spatial-Reuse TDMA/FDMA for Mobile Multi-Hop Radio Networks", IEEE INFOCOM 85, Washington, DC, USA, March 1985.

  3. I. Chlamtac and S. Kutten: "Tree Based Broadcasting in Multihop Radio Networks", IEEE Transactions on Computers, Vol. C-36, No. 10, October 1987.

  4. R. Bar-Yehuda, S. Kutten, Y. Wolfstahl and S. Zaks: "Making Distributed Spanning Tree Algorithms Fault-Resilient". STACS 1987: 432-444.

  5. R. Bar-Yehuda and S. Kutten: "Fault-Tolerant Majority Commitment", Journal of Algorithms, Vol. 9, 1988: 568-582.

  6. S. Kutten: "Optimal Fault-Tolerant Distributed Construction of a Spanning Forest", Information Processing Letters, Vol. 27, May 1988: 299-307.

  7. S. Kutten: "Stepwise construction of an efficient distributed traversing algorithm for general strongly connected directed networks or: Traversing one way streets with no map". ICCC'88 , Tel Aviv, Israel, 1988: 446-452.
    (Josef Raviv (Ed.): Computer Communication Technologies for the 90's, Proceedings of the Ninth International Conference on Computer Communication, Tel Aviv, Israel, 30 October - 3 November 1988. International Council for Computer Communication Elsevier 1988, ISBN 0-444-70539-2).

  8. A. Herzberg and S. Kutten: "Efficient Detection of Message Forwarding Faults" PODC 1989: 339-353.

  9. E. Korach, S. Kutten and S. Moran: "A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms", ACM Transactions on Programming Languages and Systems, Vol. 12, No. 1, 1990: 84-101.

  10. A. Itai, S. Kutten, Y. Wolfstahl and S. Zaks: "Optimal Distributed $t$-Resilient Election in Complete Networks", IEEE Transactions on Software Engineering, Vol. 16, No. 4, April 1990: 415-420.

  11. B. Awerbuch, I. Cidon and S. Kutten: "Optimal Maintenance of Replicated Information", Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science (FOCS 90), St.\ Louis, MO, USA, October 1990: 492-502.

  12. B. Awerbuch, I. Cidon, I. S. Gopal, M. Kaplan and S. Kutten: "Distributed Control For PARIS". PODC 1990: 145-159.

  13. I. Cidon, I. S. Gopal and S. Kutten: "Optimal Computation of Global Sensitive Functions in Fast Networks". WDAG 1990: 185-191.

  14. B. Awerbuch, I. Cidon, S. Kutten, Y. Mansour and D. Peleg: "Broadcast with Partial Knowledge" (Preliminary Version). PODC 1991: 153-163.

  15. B. Awerbuch, S. Kutten and D. Peleg: "Deadlock Free Routing", Proceedings of the 10th ACM Annual Symposium of Principles of Distributed Computing (PODC 91), Montreal, Quebec, Canada, August 1991.

  16. B. Awerbuch, S. Kutten and D. Peleg: "Competitive Distributed Job Scheduling", STOC 92, , Victoria, BC, Canada, May 1992.

  17. R. Bird, I. Gopal, A. Herzberg, P. Janson, S. Kutten, R. Molva and M. Yung: "Systematic Design of Two Party Authentication Protocols", IEEE J. on Selected Areas in Communications, Vol. 11, No. 5, June 1993: 679-693.

  18. S. Aggarwal and S. Kutten: "Time-Optimal Self-Stabilizing Spanning Tree Algorithms", The Thirteenth Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Bombay, India, December 15-17, 1993.

  19. B. Awerbuch, S. Kutten, Y. Mansour, B. Patt-Shamir and G. Varghese: "Time Optimal Self Stabilizing Synchronization", 1993 ACM STOC, San Diego, CA, USA, May 1993: 652-661.

  20. J. A. Garay, S. Kutten and D. Peleg: "A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees" (Extended Abstract). FOCS 1993: 659-668.

  21. R. Bird, I. S. Gopal, A. Herzberg, P. A. Janson, S. Kutten, R. Molva and M. Yung: "Systematic Design of a Family of Attack-Resistant Authentication Protocols". IEEE Journal on Selected Areas in Communications, 11(5), 1993: 679-693.

  22. B. Awerbuch, S. Kutten and D. Peleg: "On Buffer Economical Store and Forward Deadlock Prevention", IEEE Transactions on Communications, Vol. 42, No. 11, November 1994: 2934-2937.

  23. A. Bar-Noy, F.K. Hwang, I. Kessler and S. Kutten: "A New Competitive Algorithm for Group Testing", Discrete Applied Math.,Vol. 52, 1994: 29-38.

  24. I. Cidon, S. Kutten, Y. Mansour and D. Peleg: "Greedy Packet Schedulin", SIAM J. on Computing, Vol. 24, No. 1, February 1995: 148-157.

  25. I. Cidon, I. Gopal, M. Kaplan and S. Kutten: "Distributed Control for Fast Networks", IEEE Transactions on Communications,Vol. 43, No. 5, May 1995: 1950-1960.

  26. R. Bird, I. Gopal, A. Herzberg, P. Janson, S. Kutten, R. Molva and M. Yung: "The KryptoKnight Family of Light-Weight Protocols for Authentication and Key Distribution", IEEE/ACM Transactions on Networking, Vol. 3, No. 1, February 1995: 31-42.

  27. I. Cidon, I. Gopal and S. Kutten: "New Models and Algorithms for Future Networks", IEEE Transactions on Information Theory, Vol. 41, No.3, May 1995: 769-780.

  28. B. Awerbuch, S. Kutten, Y. Mansour and D. Peleg: "Optimal Broadcast with Partial Knowledge" (Extended Abstract). WDAG 1995: 116-130.

  29. S. Kutten: "Scalable Fault Tolerance". SOFSEM 1996: 286-306.

  30. J. Garay, I. Gopal, S. Kutten, Y. Mansour and M. Yung: "Efficient On-Line call Control Mechanism" Journal of Algorithms , Volume 23, Number 1, April 1997: 180-194.

  31. Y. Afek, S. Kutten and M. Yung: "Local Detection for Global Self Stabilization" Theoretical Computer Science Vol 186 No. 1-2, October 1997: 199-230.

  32. C. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro and M. Yung: "Perfectly-Secure Key Distribution for Dynamic Conferences" Information and Computation, Vol. 146, Num. 1, October 10, 1998: 1-23.

  33. J. Garay, S. Kutten and D. Peleg: "A Sub-Linear Time Distributed Algorithm for Minimum Weight Spanning Trees, SIAM J. on Computing 27(1), 1998: 302-316.

  34. B. Awerbuch, I. Cidon, S. Kutten, Y. Mansour and D. Peleg: "Optimal broadcast with Partial Knowledge", SIAM J. on Computing Volume 28, Number 2, 1998: 511-524.

  35. S. Kutten and D. Peleg: "Fast Distributed Construction of Small k-Dominating Sets and Applications", Journal of Algorithms Vol 28, July 1998: 40-66. Also appeared in Proceedings of the Fourteenth Annual ACM Symposium on Principle of Distributed Computing (PODC 95),Ottawa, Canada, August 1995: 238-249.

  36. A. Gopal, I. Gopal and S. Kutten: "Fast Broadcast in High Speed Networks", IEEE/ACM Transactions on Networking 7(2), 1999: 262-275.

  37. S. Kutten and B. Patt-Shamir: "stabilizing Time Adaptive Protocols", Theoretical Computer Science 220(1), 1999: 93-111.

  38. S. Kutten and D. Peleg: "Fault-Local Mending", Journal of Algorithms, Vol. 30, No. 1, January 1999: 144-165. Also appeared in Proceedings of the Fourteenth Annual ACM Symposium on Principle of Distributed Computing (PODC 95) , Ottawa, Canada, August 1995: 20-27.

  39. A. Bar-Noy, R. Canetti, S. Kutten, Y. Mansour and B.Schieber: "Bandwidth Allocation with Preemption", SIAM Journal on Computing 28 , 1999: 1806-1828.

  40. O. Gerstel, S. Kutten, G. Sasaki and R. Ramaswami: "Worst Case Analysis of Wavelength Allocation for Optical Networks". IEEE/ACM Transactions on Networking Vol. 7, No. 6, December 1999: 818-832. A previous version ("Dynamic Wavelength Allocation in WDM Ring Networks") appeared in IEEE International Conference on Communications (ICC 97), 8 - 12 June 1997 Montreal, Quebec, Canada.

  41. J. Beauquier, C. Genolini and S. Kutten: "Optimal Reactive k??Stabilization: the case of Mutual Exclusion". Proceedings of ACM PODC 1999.

  42. S. Kutten and A. Porat "Maintainance of a Spanning Tree in Dynamic Networks". Proceedings of the 13th Internation Symposium on DIStributed Computing (DISC'99) Bratislava, Slovak Republic, September 1999.

  43. S. Kutten and D. Peleg: "Tight Fault-Locality" SIAM J. on COMPUTING 30(1), 2000: 247-268.

  44. A. Herzberg and S. Kutten: "Early Detection of Message Forwarding Faults", SIAM Journal on Computing , Vol. 30, No. 4, 2000: 1169-1196. A preliminary version appeared in the Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing (PODC 89), Edmunton, Canada, August 1989: 349-353.

  45. E. Jennings and S. Kutten: "Evaluating Scheduling Algorithms for Packet Switches with Multiple Input Queues by Simulation". The Society for Computer Simulation International Annual Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS 2000),Vancouver BC, Canada July 16-20.

  46. S. Kutten, B. Patt-Shamir and R. Ostrowski: "The Las-Vegas Processor Identity Problem (How and When to be Unique)". Journal of Algorithms, 37(2), 2000: 468-494.

  47. S. Kutten, D. Peleg and U. Vishkin: "Deterministic Resource Discovery in Distributed Networks", in Proc. of the 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA'2001) Crete Island, Greece, July 2001: 77-83. To appear in Theory of Computing Systems (TOCS) special issue devoted to SPAA 2001.

  48. I. Cidon, S. Kutten and R. Soffer: "Optimal allocation of electronic content in networks". Proceedings of IEEE INFOCOM'2001. Computer Networks Volume 40, Issue 2, 7 October 2002: 205-218.

  49. S. Kutten and D. Peleg: "Asynchronous Determnistic Resource Discovery", in the Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02) October 13 - 16, 2002, Osaka University, Suita, Japan.

  50. D. Sadot, Y. Nachmani, A. Bar-Noy and S. Kutten: "Next generation Tbit/sec routers and switches: traffic modeling, scheduling algorithms, and simulations". Journal of High Speed Networks 2002, 11, no. 2: 89-102.

  51. J. Auerbach, M. Gopal, M. Kaplan and S. Kutten: "Multicast Group Membership Management in High Speed Wide Area Networks", IEEE/ACM Transactions on Networking Vol. 11, No 1, February 2003: 166-175.

  52. Y. Azar, S. Kutten and B. Patt-Shamir: "Distributed Error Confinement". To appear in the Proceedings of (ACM PODC'03), Boston, MA, USA, July 2003.

  53. O. Gerstel, S. Kutten, R. Matichin and D. Peleg: "Hotlink Enhancement Algorithms for Web Directories", Proceedings of ISAAC'2003: 68-77.

  54. S. Kutten and B. Patt-Shamir: "Adaptive Stabilization of Reactive Distributed Protocols". In the Proceedings of FSTTCS 2004.

  55. A. Korman, S. Kutten and D. Peleg: "Proof Labeling Schemes". PODC 2005. Annual ACM Symposium on Principles of Distributed Computing, 2005: 9-18.

  56. S. kutten, J. Burman, T. Herman and B. Patt-Shamir: "Asynchronous and Fully Self-stabilizing Time-Adaptive Majority Consensus", OPODIS 2005: 146-160.

  57. S. kutten, H. Ono, D. Peleg, K. Sadakane and M. Yamashita: "Energy-Optimal Online Algorithms for Broadcasting in Wireless Networks", WONS 2005: 125-130.

  58. A. Korman and S. Kutten: "Distributed Verification of Minimum Spanning Trees", to appear in Distributed Computing: 253-266, (in the special issue that will be devoted to ACM PODC 2006).

  59. B. Awerbuch, I. Cidon and S. Kutten: "Optimal Maintenance of a Spanning Tree", to appear in JACM ,2006 (jacm in italic). (Based on Optimal Maintenance of Replicated Information, above).

  60. S. kutten and D. Hendler: "Constructing Shared Objects That Are Both Robust and High-Throughput",DISC 2006: 428-442.

  61. S. kutten and A. Korman: "On Distributed Verification", ICDCN 2006: 100-114.

  62. S. kutten, S. DAS and A. Yifrach: "Improved Distributed Exploration of Anonymous Networks", ICDCN 2006: 306-318.

  63. S. kutten,J. H. Hoepman and Z. Lotker: "Efficient Distributed Weighted Matchings on Trees", SIROCCO 2006: 115-129.

  64. S. Das, P. Flocchini, S. Kutten, A. Nayak and N. Santoro: "Map construction of unknown graphs by multiple agents". Theoretical Computer Science 385, 1-3, Oct. 2007: 34-48.

  65. S. kutten and J.Burman: "Time Optimal Asynchronous Self - Stabilizing Spanning Tree", DISC 2007: 92-107.

  66. S. kutten and T. Masuzawa: "Output Stability Versus Time Till Output", Disc 2007: 343-357.

  67. S. kutten and A. Korman: "Controller and estimator for Dynamic Networks", PODC 2007: 175-184.

  68. S. kutten, B. Awerbuch, Y. mansour, B. Patt-Shamir and G. Varghese: "A Time-Optimal Self-Stabilizing Synchronizer Using A Phase Clock", IEEE Trans. Dependable Sec. Comput. 4(3), July-September 2007: 180-190.

  69. S. kutten and J. A. Korman: "Labeling Schemes with Queries", submitted for publication, SIROCCO 2007: 109-123.

  70. O. Ori Gerstel, S. Kutten, E. S. Laber, R. Matichin, D. Peleg, A.A. Pessoa and C. de Souza: "Reducing Human Interactions in Web Directory Searches". ACM Trans. Inf. Syst. 2007: 25(4).

  71. A. Korman, S. Kutten: A Note on Models for Graph Representations. DOI information: 10.1016/j.tcs.2008.10.036. A preliminary version of this paper was presented in SIROCCO`2007. Theoretical Computer Science (2008).

No live animals were harmed in composing this list.

Edit page


 
Return to the Faculty Members List Return to the main page
Home | Faculty | Research | Courses & Programs | Students | Library | Alumni | About UsTop of page
Copyright © 1998 - 2012  IEM faculty, Technion             Please, send your questions to webmaster  -  Israel Bravo         Disclaimer
http://ie.technion.ac.il         Total hits: 951015        Users online: 1                 Last updated at 10:05 - Monday Mar,26th, 2012