Older Publications by Boaz Patt-Shamir

Newer publications can be found here

Topics:

• Quality-of-Service Networking
• Periodic Scheduling
• Fault Resilience and Recovery
• Synchronization
• Packet Routing
• Adaptive Programs
• Others

---

Quality-of-Service Networking

• Nearly Optimal FIFO Buffer Management for DiffServ
• Abstract
• Paper (pdf) (PODC ’02)
• Buffer Overflow Management in QoS Switches (STOC ’01)
• Abstract
• Paper (pdf)
• STOC '01 ppt presentation (PDF)
• Optimal Smoothing Schedules for Real-Time Streams (PODC '00)
• Abstract
• Extended Abstract (pdf)
• Slides (old)
• Multiple Priority, Per Flow, Dual GCRA Rate Controller for ATM Switches (HPSR 2001)
• Abstract
• Extended abstract
• Full Paper
• Jitter Control in QoS Networks
• Abstract
• Full Paper (IEEE/ACM Trans. on Networking, 9(4):492-502, 2000)
• Proceedings version (FOCS '98)
• Slides (pdf)
• Competitive Analysis of QoS Networks
• Abstract
• Slides (talk given in Next Generation Internet Workshop, Jerusalem '99)

---

Periodic Scheduling

• General Perfectly Periodic Scheduling
• Abstract
• Paper (PODC ’02)
• Dispatching in Perfectly-Periodic Schedules
• Abstract
• Paper (PDF version)
• Efficient Periodic Scheduling by Trees
• Abstract
• Extended Abstract (INFOCOM ’02)
• Nearly Optimal Perfectly-Periodic Schedules
• Abstract
• Extended Abstract (PODC 2001)
• Full paper
• Broadcast Disks with Polynomial Cost Functions
• Abstract
• Paper (INFOCOM 2000)

---

Fault Resilience and Recovery

• Distributed Fault Confinement (2002)
• Abstract
• Extended Abstract (pdf)
• Stabilizing Time-Adaptive Protocols  (Theoretical Computer Science 220(1):93-111, 1999)
• Abstract
• Paper
• Self-Stabilizing End-to-End Communication (Journal of High-Speed Networks 5(4), 1996)
• Abstract
• Paper
• Self-Stabilization by Local Checking and Global Reset (WDAG '94)
• Abstract
• Paper
• Bounding the Unbounded (INFOCOM '94)
• Abstract
• Paper
• Slides
• Time Optimal Self-Stabilizing Synchronization (STOC '93)
• Abstract
• Paper
• Self-Stabilization by Local Checking and Correction (FOCS '91)
• Abstract
• Paper
• Asynchronous Time-Adaptive Self Stabilization (PODC '98)
• Brief Announcement
• Information Survivability by Self-Stabilization (ISW '97)
• Position paper
• Slides

---

Synchronization

• Optimal and Efficient Clock Synchronization Under Drifting Clocks (PODC'99)
• Abstract
• Proceedings version
• Slides
• A Theory of Clock Synchronization (PhD thesis)
• Abstract
• Thesis (312K compressed postscript)
• Talks (slides)
• General overview
• Complexity of clock synchronization
• A Theory of Clock Synchronization (STOC '94)
• Abstract
• Paper
• Adapting to Asynchronous Dynamic Networks (STOC '92)
• Abstract
• Paper

---

Packet Routing

• New Stability Results for Adversarial Queuing (SPAA ’02)
• Abstract
• Paper
• Average-Case Analysis of Greedy Packet Scheduling (Theory of Computing Systems, to appear)
• Abstract
• Proceedings version (PODC '00)
• Full Paper
• Greedy Packet Scheduling on Shortest Paths (Journal of Algorithms 14(3), 1993)
• Abstract
• Paper
• Many-to-One Packet Routing on Grids (STOC '95)
• Abstract
• Paper
• Slides

---

Adaptive Programs:

• A New Approach to Compiling Adaptive Programs
• Abstract
• Paper (ESOP '96)
• Full paper with additional results (Science of Computer Programming, 29(3):303-326)
• An Efficient Compiler for Adaptive Programs
• Abstract
• Paper
• Traversals of Object Structures: Specification and Efficient Implementation
• Abstract
• Paper
• The Refinement Relation of Graph-Based Generic Programs (Generic Programming 1998, LNCS 1766)
• Abstract
• Paper

---

Others:

• Distributed MST for Constant Diameter Graphs
• Abstract
• Extended Abstract (PODC 2001)
• A Note on Randomized Mutual Search (Information Processing Letters 71(5-6):187-192, 1999)
• Abstract
• Paper (pdf).
• Exact Analysis of Exact Change (SIAM Journal on Discrete Mathematics, 13(4):436-453, 2000)
• Abstract
• Full Paper
• Proceedings version (ISTCS '97)
• The Las-Vegas Processor Identity Problem (How and When to Be Unique)
• Abstract
• Proceedings version(ISTCS '93)
• Full paper (J.Alg., 2000) PDF version
• Time-Space Tradeoffs for Set Operations (Theoretical Computer Science 110, 1993)
• Abstract
• Paper