Boaz Patt-Shamir: Publications 2000-2008

See DBLP for publications since 2008.

1. Journal papers
2. Papers submitted to journals
3. Conference papers

Journal Papers

S. Kutten, R. Ostrovsky and B. Patt-Shamir. The Las-Vegas Processor Identity Problem (How and When to Be Unique). In Journal of Algorithms, 37:468–494, 2000.

Y. Frankel, B. Patt-Shamir and Y. Tsiounis. Exact Analysis of Exact Change. In SIAM Journal of Discrete Mathematics, 13(4):436–453, 2000.

Y. Mansour and B. Patt-Shamir. Jitter Control in QoS Networks. In IEEE/ACM Transactions on Networking 9(4):492–502, 2000.

B. Patt-Shamir. Transmission of Real Time Streams. Survey article in SIGACT News, 32(3):53–62, September 2001.

Z. Lotker and B. Patt-Shamir. Average-Case Analysis of Greedy Packet Scheduling. In Theory of Computing Systems 35(6):667–683, 2002.

A. Bar-Noy, A. Nisgav and B. Patt-Shamir. Nearly Optimal Perfectly Periodic Schedules. In a special issue of Distributed Computing 15:207–220, 2002.

Z. Lotker and B. Patt-Shamir. Nearly Optimal FIFO Buffer Management for Two Packet Classes. InComputer Networks, 42(4):481–492, 2003.

Z. Brakerski, V. Dreizin and B. Patt-Shamir. Dispatching in Perfectly-Periodic Schedules. In Journal of Algorithms 49(2):219–239, 2003.

A. Bar-Noy, B. Patt-Shamir and I. Ziper. Broadcast Disks With Polynomial Cost Functions. In Wireless Networks 10(2):157–168, 2004.

Y. Mansour, B. Patt-Shamir and O. Lapid. Optimal Smoothing Schedules for Real-Time Streams. In Distributed Computing 17(1):77–89, 2004.

Z. Lotker, B. Patt-Shamir and A. Rosén. New Stability Results for Adversarial Queuing. In SIAM Journal on Computing 33(2):286–303, 2004.

K. Lieberherr, B. Patt-Shamir and D. Orleans. Efficient Traversals of Object Systems. In ACM Transactions on Programming Languages and Systems 26(2): 370–412, 2004.

A. Kesselman, Z. Lotker, Y. Mansour, B. Patt-Shamir, B. Schieber and M. Sviridenko. Buffer Overflow Management in QoS Switches. In SIAM Journal on Computing 33(3):563–583, 2004.

A. Bar-Noy, V. Dreizin and B. Patt-Shamir. Efficient Algorithms for Periodic Scheduling. In Computer Networks 45(2):155–173, 2004.

Z. Lotker, B. Patt-Shamir, E. Pavlov and D. Peleg. Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds. In SIAM Journal on Computing 35(1):120–131, 2005.

Z. Brakeski, A. Nisgav and B. Patt-Shamir. General Periodic Scheduling. In Algorithmica 45(2):183–208, 2006.

Z. Lotker, B. Patt-Shamir and D. Peleg. Distributed MST for Constant Diameter Graphs. In Distributed Computing 18(6):453–460, 2006.

Z. Brakerski and B. Patt-Shamir. Jitter-Approximation Tradeoff for Periodic Scheduling. In “Best papers of WMAN 2004” issue of Wireless Networks, 12(6):723–731, 2006.

B. Patt-Shamir. A Note on Efficient Aggregate Queries in Sensor Networks. In Theoretical Computer Science 370:254–264, 2007.

B. Awerbuch, Y. Azar, Z. Lotker, B. Patt-Shamir and M. Tuttle. Collaborate With Strangers To Find Own Preferences. In Theory of Computing Systems special issue on SPAA ’05, 42(1): 27–41, 2008.

Z. Lotker, B. Patt-Shamir and M. Tuttle. A Game of Timing and Visibility. In Games and Economic Behavior, 62(2):643–660, 2008..

B. Awerbuch, S. Kutten, Y. Mansour, B. Patt-Shamir and G. Varghese. Time Optimal Self-Stabilizing Synchronizers Using Phase Clocks. In IEEE Transactions on Dependable and Secure Computing, 4(3): 180–190, 2007.

N. Alon, B. Awerbuch, Y. Azar and B. Patt-Shamir. Tell Me Who I Am: An Interactive Recommendation System. Accepted to a special issue of Theory of Computing Systems devoted to SPAA ’06.

B. Patt-Shamir and A. Shafrir. Approximate Distributed Top-k Queries. Accepted to Distributed Computing.

Papers Submitted to Journals

Y. Azar, S. Kutten and B. Patt-Shamir. Distributed Error Confinement. Submitted to ACM Transactions on Algorithms. Under revision.

Papers in Conferences

A. Bar-Noy, B. Patt-Shamir and I. Ziper. Broadcast Disks with Polynomial Cost Functions. In Proc. of the 19th IEEE INFOCOM, pages 575–584, March 2000.

Y. Mansour, B. Patt-Shamir and O. Lapid. Optimal Smoothing Schedules for Real-Time Streams. Appeared in 19th ACM Symp. on Principles of Distributed Computing, pages 21–29, July 2000.

Z. Lotker and B. Patt-Shamir. Average-Case Analysis of Greedy Packet Scheduling. In 19th ACM Symp. on Principles of Distributed Computing, pages 31–40, July 2000.

A. Hagai and B. Patt-Shamir. Multiple Priority, Per Flow, Dual GCRA Rate Controller for ATM Switches. Appeared in Proc. of IEEE Workshop on High Performance Switching and Routing, pages 169–174, May 2001.

A. Kesselman, Z. Lotker, Y. Mansour, B. Patt-Shamir, B. Schieber and M. Sviridenko. Buffer Overflow Management in QoS Switches. In Proc. of the 33rd Ann. ACM Symp. on Theory of Computing, pages 520–529, July 2001.

A. Bar-Noy, A. Nisgav and B. Patt-Shamir. Nearly Optimal Perfectly-Periodic Schedules. In 20th ACM Symp. on Principles of Distributed Computing, pages 107–116, August 2001.

Z. Lotker, B. Patt-Shamir and D. Peleg. Distributed MST for Constant Diameter Graphs. In 20th ACM Symp. on Principles of Distributed Computing, pages 63–71, August 2001.

A. Bar-Noy, V. Dreizin and B. Patt-Shamir. Efficient Periodic Scheduling by Trees. In IEEE INFOCOM ’02, June 2002.

Z. Lotker and B. Patt-Shamir. Nearly Optimal FIFO Buffer Management for DiffServ. In 21st ACM Symp. on Principles of Distributed Computing, pages 134–143, July 2002.

Z. Brakeski, A. Nisgav and B. Patt-Shamir. General Periodic Scheduling. In 21st ACM Symp. On Principles of Distributed Computing, pages 163–172, July 2002.

Z. Lotker, B. Patt-Shamir and A. Rosén. New Stability Results for Adversarial Queuing. In 14th ACM Symp. on Parallel Algorithms and Architectures, pages 192–199, August 2002.

Z. Lotker, B. Patt-Shamir, E. Pavlov and D. Peleg. MST Construction in O(log log n) Communication Rounds. In 15th ACM Symp. on Parallel Algorithms and Architectures, pages 94–100, June 2003.

Y. Azar, S. Kutten and B. Patt-Shamir. Distributed Error Confinement. In 22nd ACM Symp. On Principles of Distributed Computing, pages 33–42, July 2003.

A. Kesselman, Z. Lotker, Y. Mansour and B. Patt-Shamir. Buffer Overflows of Merging Streams. In 11th Annual European Symposium on Algorithms, pages 349–360, September 2003.

Z. Brakerski and B. Patt-Shamir. Jitter-Approximation Tradeoff for Periodic Scheduling. In 4th Int. Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks, April 2004.

B. Awerbuch, B. Patt-Shamir, D. Peleg and M. Tuttle. Collaboration of Untrusting Peers with Changing Interests. In 5th ACM Conference on Electronic Commerce, pages 112–119, May 2004.

B. Patt-Shamir. A Note on Efficient Aggregate Queries in Sensor Networks. In 23rd ACM Symp. on Principles of Distributed Computing, pages 283–289, July 2004.

S. Kutten and B. Patt-Shamir. Adaptive Stabilization of Reactive Protocols. In 24th Conf. on Foundations of Software Technology and Theoretical Computer Science, pages 396–407, December 2004.

B. Awerbuch, B. Patt-Shamir, D. Peleg and M. Tuttle. Improved Recommendation Systems. In 16th ACM-SIAM Symposium on Discrete Algorithms, pages 1174–1183, January 2005.

B. Awerbuch, B. Patt-Shamir, D. Peleg and M. Tuttle. Adaptive Collaboration in Peer-to-Peer Systems. In 25th International Conference on Distributed Computing Systems, pages 71–80, June 2005.

B. Awerbuch, Y. Azar, Z. Lotker, B. Patt-Shamir, D. Peleg and M. Tuttle. Collaborate With Strangers To Find Own Preferences. In 17th ACM Symposium on Parallelism in Algorithms and Architectures, pages 263–269, July 2005.

J. Burman, T. Herman, S. Kutten and B. Patt-Shamir. Asynchronous and Fully Self-Stabilizing Time-Adaptive Majority Consensus. In 9th Int. Conf. on Principles of Distributed Systems, pages 146–160, December 2005.

G. Chockler, S. Gilbert and B. Patt-Shamir. Communication-Efficient Probabilistic Quorum Systems for Sensor Networks. In 4th IEEE Conference on Pervasive Computing and Communications Workshops, pages 111–117, March 2006.

B. Patt-Shamir and A. Shafrir. Approximate Top-k Queries in Sensor Networks. In 13th Colloquium on Structural Information and Communication Complexity, pages 319–333, July 2006.

N. Alon, B. Awerbuch, Y. Azar and B. Patt-Shamir. Tell Me Who I Am: An Interactive Recommendation System. In 18th ACM Symposium on Parallelism in Algorithms and Architectures, pages 11–10, July 2006.

Z. Lotker, B. Patt-Shamir and M. Tuttle. Publish and Perish: Definition and Analysis of an n-Person Publication Impact Game. In 18th ACM Symposium on Parallelism in Algorithms and Architectures, pages 11–18, July 2006.

Z. Lotker, B. Patt-Shamir and Adi Rosén. Distributed Approximate Matching. In 26th ACM Symp. On Principles of Distributed Computing, pages 167–174, August 2007.

H. Buhrman, M. Christandl, M. Koucký, Z. Lotker, B. Patt-Shamir and N. Vereshchagin. High Entropy Random Selection Protocols. In 11th International Workshop on Randomization and Computation, pages 366–379, August 2007.

B. Awerbuch, A. Nisgav and B. Patt-Shamir. Asynchronous Recommendation Systems. In 11th International Conference on Principles Of Distributed Systems, December 2007.

Z. Lotker, B. Patt-Shamir and D. Rawitz. Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental. In 25th International Symposium on Theoretical Aspects of Computer Science, pages 503–514, February 2008.

B. Patt-Shamir and D. Rawitz. Video Distribution Under Multiple Constraints (Extended Abstract). To appear in 28th International Conference on Distributed Computing Systems, June 2008.