Boaz Patt-shamir

Distributed Discovery of Large Near-Cliques (2009)

Abstract We study the scenario where a transient fault hit f of the n nodes of a distributed system by corrupting their state. We consider the basic problem of persistent bit, where the system is...

Brakerski, Zvika, Patt-Shamir, Boaz

Given an undirected graph and $0\le\epsilon\le1$, a set of nodes is called $\epsilon$-near clique if all but an $\epsilon$ fraction of the pairs of nodes in the set have a link between them. In this...

Asynchronous and Fully Self-Stabilizing Time-Adaptive Majority Consensus (extended version), http://tx.technion.ac.il/∼bjanna (2009)

Janna Burman, Shay Kutten, Boaz Patt-shamir

Abstract. We study the scenario where a batch of transient faults hits an asynchronous distributed system by corrupting the state of some f nodes. We concentrate on the basic majority consensus...

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. IEEE TRANSACTIONS ON DEPEDABLE AND SECURE COMPUTING A Time Optimal Self-Stabilizing Synchronize (2009)

Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-shamir, George Varghese

A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local ‘pulse counter ’ that simulates the...

(Extended Abstract) (2009)

Baruch Awerbuch, Boaz Patt-shamir, David Peleg

We consider a simple model for reputation systems such as the one used by eBay. In our model there are n players, some of which may exhibit arbitrarily malicious (Byzantine) behavior, and there are m...

Improved Recommendation Systems ∗ Extended Abstract (2009)

Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Mark Tuttle

1

Asynchronous and fully self-Stabilizing time-adaptive majority consensus (2008)

Janna Burman, Ted Herman, Shay Kutten, Boaz Patt-shamir

Abstract. We study the scenario where a batch of transient faults hits an asynchronous distributed system by corrupting the state of some f nodes. We concentrate on the basic majority consensus...

Abstract Collaboration of Untrusting Peers with Changing Interests Extended Abstract (2008)

Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Mark Tuttle

Electronic commerce engines like eBay depend heavily on reputation systems to improve customer confidence that electronic transactions will be successful, and to limit the economic damage done by...

Video Distribution Under Multiple Constraints (2008)

DOI 10.1007/s00446-005-0127-6 ORIGINAL ARTICLE (2008)

We consider the optimization problem of providing a set of video streams to a set of clients, where each stream has costs in m possible measures (such as communication bandwidth, processing bandwidth...

Zvi Lotker, Boaz Patt-shamir, David Peleg

Abstract This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for graphs of constant diameter in the bounded-messages model, where each message can...

Communication-Efficient Probabilistic Quorum Systems for Sensor Networks (Preliminary Abstract) (2008)

Gregory Chockler, Seth Gilbert, Boaz Patt-shamir

Communication-efficiency is of key importance when constructing robust services in limited bandwidth environments, such as sensor networks. We focus on communication-efficiency in the context of...

(Extended Abstract) (2008)

Baruch Awerbuch, Boaz Patt-shamir, David Peleg

We consider a simple model for reputation systems such as the one used by eBay. In our model there are n players, some of which may exhibit arbitrarily malicious (Byzantine) behavior, and there are m...

RENT, LEASE OR BUY: RANDOMIZED ALGORITHMS FOR MULTISLOPE SKI RENTAL (2008)

Zvi Lotker, Boaz Patt-shamir, Dror Rawitz

Abstract. In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of...

Zvika Brakerski, Aviv Nisgav, Boaz Patt-shamir

Abstract. In a perfectly periodic schedule, each job must be scheduled precisely every some fixed number of time units after its previous occurrence. Traditionally, motivated by centralized systems,...

Dispatching in perfectly-periodic schedules (2008)

Zvika Brakerski, Vladimir Dreizin, Boaz Patt-shamir

In a perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predefined number of time slots, called the period of that client. Periodic...

Exact analysis of exact change: the k-payment problem (2008)

Boaz Patt-shamir, Yiannis Tsiounis, Yair Frankel

Abstract. We introduce the k-payment problem: given a total budget of N units, the problem is to represent this budget as a set of coins, so that any k exact payments of total value at most N can be...

Amotz Bar-noy, Boaz Patt-shamir, Igor Ziper

Abstract. In broadcast disks systems, information is broadcasted in a shared medium. When a client needs an item from the disk, it waits until that item is broadcasted. Broadcast disks systems are...

Nearly optimal fifo buffer management for two packet classes (2008)

Zvi Lotker, Boaz Patt-shamir

We consider a FIFO buffer with finite storage space. An arbitrary input stream of packets arrives at the buffer, but the output stream rate is bounded, so overflows may occur. We assume that each...

Distributed Approximate Matching (2008)

Zvi Lotker, Boaz Patt-shamir, Adi Rosén

We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a (4+ǫ)-approximation distributed algorithm for weighted maximum matching, whose running...

Abstract Improved Recommendation Systems ∗ Extended Abstract (2008)

Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Mark Tuttle

We consider a model of competitive recommendation systems proposed by Drineas et al. [4]. In recommendation systems (e.g., for books or movies), the system tracks which product each user chose in the...

Abstract General Perfectly Periodic Scheduling Extended Abstract (2008)

Zvika Brakerski, Aviv Nisgav, Boaz Patt-shamir

In a perfectly-periodic schedule, time is divided into time-slots, and each client is scheduled precisely every some predefined number of slots, called the period of that client. Periodic schedules...

Asynchronous and fully self-Stabilizing time-adaptive majority consensus (2008)

Janna Burman, Ted Herman, Shay Kutten, Boaz Patt-shamir

Abstract. We study the scenario where a batch of transient faults hits an asynchronous distributed system by corrupting the state of some f nodes. We concentrate on the basic majority consensus...

Abstract Optimal Smoothing Schedules for Real-Time Streams ∗ EXTENDED ABSTRACT (2008)

Yishay Mansour, Boaz Patt-shamir, Ofer Lapid

We consider the problem of smoothing real-time streams (such as video streams), where the goal is to reproduce a variablebandwidth stream remotely, while minimizing bandwidth cost, space overhead,...

Abstract Collaboration of Untrusting Peers with Changing Interests Extended Abstract (2008)

Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Mark Tuttle

Electronic commerce engines like eBay depend heavily on reputation systems to improve customer confidence that electronic transactions will be successful, and to limit the economic damage done by...

Brief Announcement: Timing Games and Shared Memory (2008)

Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle

Abstract. We model a simple problem in advertising as a strategic timing game, and consider continuous and discrete versions of this game. For the continuous game, we completely characterize the Nash...

Categories and Subject Descriptors (2008)

Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle, The Israel

We consider a model with n players and m objects. Each player has a “preference vector ” of length m that models his grade for each object. The grades are unknown to the players. A player can...

Approximate Top-k Queries in Sensor Networks (Extended Abstract) (2008)

Boaz Patt-shamir, Allon Shafrir

Abstract. We consider a distributed system where each node has a local count for each item (similar to elections where nodes are ballot boxes and items are candidates). A top-k query in such a system...

www.elsevier.com/locate/tcs A note on efficient aggregate queries in sensor networks ✩ (2008)

A Time-Optimal Self-Stabilizing Synchronizer Using a Phase Clock (2008)

We consider a scenario where nodes in a sensor network hold numeric items, and the task is to evaluate simple functions of the distributed data. In this note we present distributed protocols for...

Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-shamir, George Varghese

Abstract—A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local “pulse counter ” that...

Reputation, Trust and Recommendation Systems in Peer-to-Peer Environments Position Paper (2008)

Abstract Tell Me Who I Am: An Interactive Recommendation System Extended Abstract (2008)

The tremendous popularity of the Internet has brought about the notion of peer-to-peer computing, whose reliance on a central authority (let alone a central server) is absolutely minimal. It seems...

Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-shamir, Neumann Fund

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...

Theory Comput Syst DOI 10.1007/s00224-007-9016-7 Collaborate with Strangers to Find Own Preferences (2008)

Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle, Springer Science+business Media, ...

Abstract We consider a model with n players and m objects. Each player has a “preference vector ” of length m, that models his grades for all objects. The grades are initially unknown to the...

Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental (2008)

Dispatching in perfectly-periodic schedules (2008)

In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists...

Zvika Brakerski, Vladimir Dreizin, Boaz Patt-shamir

In a perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predefined number of time slots, called the period of that client. Periodic...

Communication-Efficient Probabilistic Quorum Systems for Sensor Networks (Preliminary Abstract) (2008)

Gregory Chockler, Seth Gilbert, Boaz Patt-shamir

Communication-efficiency is of key importance when constructing robust services in limited bandwidth environments, such as sensor networks. We focus on communication-efficiency in the context of...

Optimal and Efficient Clock Synchronization Under Drifting Clocks (Extended Abstract) (2008)

Rafail Ostrovsky, Boaz Patt-Shamir

We consider the classical problem of clock synchronization in distributed systems. Previously, this problem was solved optimally and efficiently only in the case when all individual clocks are...

Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental (2008)

Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental (2008)

In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists...

High Entropy Random Selection Protocols (2008)

In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists...

Abstract (2008)

Noga Alon, Baruch Awerbuch, Johns Hopkins U, Yossi Azar, Boaz Patt-shamir

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...

Vereshchagin, Nikolai K., Buhrman, Harry, Cristandl, Matthias, Koucky, Michal, Lotker, Zvi, Patt-Shamir, Boaz

We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one...

44. Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental (2008)

In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists...

MIT (2007)

and AT&T Research Labs (2007)

Many important protocols in distributed computing have simple and elegant solutions if we allow the assumption of unbounded size registers. This assumption can be simulated in practice using...

We study jitter control in networks with guaranteed quality of service (QoS) from the competitive analysis point of view: We propose on-line algorithms that control jitter and compare their...

The (2007)

Buffer Overow Management in QoS Switches (2007)

We consider protocols which can withstand state-corrupting faults which arbitrarily flip the bits of the volatile memory in a system. The time which elapses since the protocol starts executing (with...

Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-shamir, Baruch Schieber, Maxim Sviridenko

We consider two types of buffering policies that are used in network switches supporting QoS (Quality of Service). In the FIFO type, packets must be released in the order they arrive; the difculty in...

Multiple Priority, Per Flow, Dual GCRA Rate Controller for ATM Switches (2007)

Avi Hagai, Boaz Patt-Shamir

We propose a rate controller for ATM switches. The rate controller supports multiple priorities, and dual leaky bucket (GCRA) traffic descriptors (such as VBR). While regulating each stream...

An Efficient Compiler for Adaptive Programs (2007)

College Of Computer, Karl Lieberherr, Boaz Patt-shamir, Salil Pradhan

We describe an extended language to express traversals in object oriented programs, give a compiler to generate code from traversal specifications, and prove it correct. The compiler generates better...

The Las-Vegas Processor Identity Problem (How and When to Be Unique) (2007)

Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir

We study the classical problem of assigning unique identifiers to identical concurrent processes. In this paper, we consider the asynchronous shared memory model, and the correctness requirement is...

Adapting to Asynchronous Dynamic Networks (2007)

Extend Ed, Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Michael Saks

Baruch Awerbuch Boaz Patt-Shamir y David Peleg z Michael Saks x Abstract The computational power of different communication models is a fundamental question in the theory of distributed computation....

The (2007)

We study the scenario where a transient batch of faults hit a minority of the nodes in a distributed system by corrupting their state. We concentrate on the basic persistent bit problem, where the...

The Technion (2007)

Average-case analysis of greedy packet scheduling (2007)

We study the classical problem of assigning unique identiers to identical concurrent processes. In this paper, we consider the asynchronous shared memory model, and the correctness requirement is...

Zvi Lotker, Boaz Patt-shamir

We study the average number of delays suered by packets routed using greedy (work conserving) scheduling policies. We obtain tight bounds on the worst-case average number of delays in a few cases as...

Dispatching in perfectly-periodic schedules (2007)

Zvika Brakerski, Vladimir Dreizin, Boaz Patt-shamir

In a perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predened number of time slots, called the period of that client. Periodic schedules...

y (2007)

Self-stabilizing protocols must begin operating correctly even when started from an arbitrary state. The end-to-end problem is to ensure reliable message delivery across an unreliable network under...

y (2007)

Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-shamir, Baruch Schieber, Maxim Sviridenko

A network protocol consists of a program for each network node. Each program consists of code and inputs as well as local state. The global state of the network consists of the local state of each...

x (2007)

yx

Evolution of software via adaptive programming (2007)

Principal Investigators, Karl J. Lieberherr, Boaz Patt-shamir, Additional Key, Personnel Jens Palsberg

We claim that our paradigm of adaptive programming is a good solution for the problem of software evolution. We outline the ideas behind our existing tools, and propose significant

New Stability Results for Adversarial Queuing (Extended Abstract) (2007)

Zvi Lotker, Boaz Patt-Shamir, Adi Rosén, Adi Ros En

We consider the model of "adversarial queuing theory" for packet networks introduced by Borodin et al. [6]. We show that the scheduling protocol First-In-First-Out (FIFO) can be unstable at...

ACM SIGACT News Distributed Computing Column 4 (2007)

Sergio Rajsbaum July, Sergio Rajsbaum, Boaz Patt-shamir

The Distributed Computing Column covers the theory of systems that are composed of a number of interacting computing elements. These include problems of communication and networking, databases,...

Approximate Distributed Top-k Queries ∗ (2007)

Boaz Patt-shamir, Allon Shafrir

We consider a distributed system where each node keeps a local count for items (similar to elections where nodes are ballot boxes and items are candidates). A top-k query in such a system asks which...

Asynchronous Recommendation Systems EXTENDED ABSTRACT (2007)

Baruch Awerbuch, Aviv Nisgav, Boaz Patt-shamir

We consider the following abstraction of recommendation systems. There are n players and m objects, and each player has an arbitrary binary preference grade (“likes ” or “dislikes”) for each...

High Entropy Random Selection Protocols (2007)

Harry Buhrman, Boaz Patt-shamir, Matthias Christandl, Zvi Lotker, Nikolai Vereshchagin

We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one...

Tell me who I am: An interactive recommendation system (2006)

Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-shamir

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...

A Time Optimal Self-Stabilizing Synchronizer Using A Phase Clock ∗ (2006)

Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-shamir, George Varghese

A synchronizer with a phase counter (sometimes called asynchronous phase clock) is an asynchronous distributed algorithm, where each node maintains a local ‘pulse counter ’ that simulates the...

A Game of Timing and Visibility (2006)

Zvi Lotker, Boaz Patt-Shamir, Mark R. Tuttle

We consider the following abstraction of competing publications. There are n players in the game. Each player i chooses a point xi in the interval [0, 1], and a player’s payoff is the distance from...

DOI 10.1007/s11276-006-6531-4 Jitter-approximation tradeoff for periodic scheduling (2006)

Zvika Brakerski, Boaz Patt-shamir

Abstract We consider an asymmetric wireless communication setting, where a server periodically broadcasts data items to different mobile clients. The goal is to serve items into a prescribed rate,...

Abstract (2006)

Noga Alon, Baruch Awerbuch, Johns Hopkins U, Yossi Azar, Boaz Patt-shamir

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...

Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds (2005)

Zvi Lotker, Boaz Patt-shamir, Elan Pavlov, David Peleg

Abstract. We consider a simple model for overlay networks, where all n processes are connected to all other processes, and each message contains at most O(log n) bits. For this model, we present a...

Collaborate With Strangers To Find Own Preferences (2005)

Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle

We consider a model with n players and m objects. Each player has a “preference vector ” of length m, that models his grades for all objects. The grades are initially unknown to the players. A...

Collaborate With Strangers To Find Own Preferences (2005)

Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle

We consider a model with n players and m objects. Each player has a “preference vector ” of length m, that models his grades for all objects. The grades are initially unknown to the players. A...

Collaborate With Strangers To Find Own Preferences (2005)

Baruch Awerbuch, Yossi Azar, Zvi Lotker, Boaz Patt-shamir, Mark R. Tuttle

We consider a model with n players and m objects. Each player has an unknown grade for each object, modeled by a “preference vector ” of length m. A player can learn his grade for an object by...

Buffer Overflow Management in QoS Switches (2004)

Kesselmann,Alexander, Lotker,Zvi, Mansour,Yishay, Patt-Shamir,Boaz, Schieber,Baruch, Sviridenko,Maxim

Buffer Overflow Management in QoS Switches (2004)

Kesselmann, Alexander, Lotker, Zvi, Mansour, Yishay, Patt-Shamir, Boaz, Schieber, Baruch, Sviridenko, Maxim

Adaptive stabilization of reactive protocols (2004)

Improved Recommendation Systems Extended Abstract (2004)

Abstract. A self-stabilizing distributed protocol can recover from any state-corrupting fault. A self-stabilizing protocol is called adaptive if its recovery time is proportional to the number of...

Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Mark Tuttle

We consider a model of competitive recommendation systems proposed by Drineas et al. [DKR02]. In recommendation systems (such as book or movie recommendations), the system tracks which product each...

Buffer Overflow Management in QoS Switches (2004)

Kesselmann, Alexander, Lotker, Zvi, Mansour, Yishay, Patt-Shamir, Boaz, Schieber, Baruch, Sviridenko, Maxim

Buffer overflows of merging streams (2003)

Alex Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-shamir

Abstract. We consider a network merging streams of packets with different quality of service (QoS) levels, where packets are transported from input links to output links via multiple merge stages....

Distributed error confinement (2003)

Yossi Azar, Shay Kutten, Boaz Patt-shamir

We initiate the study of error confinement in distributed applications, where the goal is that only nodes that were directly hit by a fault may deviate from their correct external behavior, and only...

Buffer overflows of merging streams (2003)

Alex Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-shamir

Abstract. We consider a network merging streams of packets with different quality of service (QoS) levels, where packets are transported from input links to output links via multiple merge stages....

New Stability Results for Adversarial Queuing (2002)

Zvi Lotker, Boaz Patt-shamir, Ros En

Abstract. We consider the model of "adversarial queuing theory " for packet networks introduced by Borodin et al. [J. ACM, 48 (2001), pp. 13--38]. We show that the scheduling...

New Stability Results for Adversarial Queuing (2002)

Zvi Lotker, Boaz Patt-shamir, Ros Én

Abstract. We consider the model of “adversarial queuing theory ” for packet networks introduced by Borodin et al. [7]. We show that the scheduling protocol First-In-First-Out (FIFO) can be...

Efficient Periodic Scheduling by Trees (2002)

Amotz Bar-noy, Vladimir Dreizin, Boaz Patt-shamir

Abstract — In a perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predefined number of time slots. The input to a schedule design...

Efficient Periodic Scheduling by Trees (2002)

Amotz Bar-noy, Vladimir Dreizin, Boaz Patt-shamir

Abstract—Ina perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predefined number of time slots. The input to a schedule design algorithm...

Efficient Periodic Scheduling by Trees (2002)

Amotz Bar-noy, Vladimir Dreizin, Boaz Patt-shamir

Abstract—Ina perfectly-periodic schedule, time is divided into time-slots, and each client gets a time slot precisely every predefined number of time slots. The input to a schedule design algorithm...

New Stability Results for Adversarial Queuing (2002)

Zvi Lotker, Boaz Patt-shamir, Ros Én

Abstract. We consider the model of “adversarial queuing theory ” for packet networks introduced by Borodin et al. [J. ACM, 48 (2001), pp. 13–38]. We show that the scheduling protocol...

Distributed Error Confinement EXTENDED ABSTRACT (2002)

Yossi Azar, Shay Kutten, Boaz Patt-shamir

We initiate the study of error confinement in reactive distributed applications, where the goal is that only nodes that were directly hit by a fault may deviate from their correct external behavior,...

Distributed Error Confinement EXTENDED ABSTRACT (2002)

Yossi Azar, Shay Kutten, Boaz Patt-shamir

We initiate the study of error confinement in reactive distributed applications, where the goal is that only nodes that were directly hit by a fault may deviate from their correct external behavior,...

Nearly Optimal FIFO Buffer Management for DiffServ (Extended Abstract) (2002)

Zvi Lotker, Boaz Patt-Shamir

Zvi Lotker Boaz Patt-Shamir zvilo@eng.tau.ac.il boaz@eng.tau.ac.il Dept. of Electrical Engineering Tel Aviv University Tel Aviv 69978 Israel Abstract We consider a FIFO buffer with finite storage...

Distributed MST for Constant Diameter Graphs (2001)

Zvi Lotker, Boaz Patt-shamir, David Peleg

This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for thatÇÐÓ�Ò graphs of constant diameter in the bounded-messages model, where each message...

Nearly Optimal Perfectly-Periodic Schedules (2001)

Amotz Bar-noy, Aviv Nisgav, Boaz Patt-shamir

We study the problem of scheduling infinitely ¢ often jobs, each with an associated demand probability, under the constraint that each job must be scheduled with a fixed period. That is, the number...

Buffer overflow management in QoS switches (2001)

Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-shamir, Baruch Schieber, Maxim Sviridenko

Abstract. We consider two types of buffering policies that are used in network switches supporting Quality of Service (QoS). In the FIFO type, packets must be transmitted in the order in which they...

Digital Object Identifier (DOI) 10.1007/s00446-003-0101-0 Optimal smoothing schedules for real-time streams ⋆ (2001)

Yishay Mansour, Boaz Patt-shamir, Ofer Lapid

Abstract. We consider the problem of smoothing real-time streams (such as video streams), where the goal is to reproduce a variable-bandwidth stream remotely, while minimizing bandwidth cost, space...

Distributed MST for Constant Diameter Graphs (2001)

Zvi Lotker, Boaz Patt-shamir, David Peleg

This paper considers the problem of distributively constructing a minimum-weight spanning tree (MST) for graphs of constant diameter in the bounded-messages model, where each message can contain at...

Adaptive Stabilization of Reactive Distributed Protocols. Extended Abstract. http: iew3.technion.ac.il:8080/ kutten/kp00.ps (2001)

Jitter Control in QoS Networks (2001)

A stabilizing distributed protocol is called adaptive if its recovery time from a state-corrupting fault is proportional to the number of processors hit by the fault. General adaptive protocols were...

Nearly Optimal Perfectly-Periodic Schedules (2001)

Abstract | We study jitter control in networks with guaranteed quality of service (QoS) from the competitive analysis point of view: We propose on-line algorithms that control jitter and compare...

Amotz Bar-noy, Aviv Nisgav, Boaz Patt-shamir

We study the problem of scheduling innitely often M jobs, each with an associated demand probability w i, under the constraint that each job must be scheduled with a xed period. That is, the number...

Buffer overflow management in QoS switches (2001)

Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, Maxim Sviridenko

We consider two types of buffering policies that are used in network switches supporting QoS (Quality of Service). In the FIFO type, packets must be transmitted in the order they arrive; the...

Abstract (2000)

Alexander Kesselman, Boaz Patt-shamir, Zvi Lotker, Baruch Schieber, Yishay Mansour, Maxim Sviridenko

We consider two types of buffering policies that are used in network switches supporting QoS (Quality of Service). In the FIFO type, packets must be released in the order they arrive; the difficulty...

Multiple priority, per flow, dual gcra rate controller for atm switches (2000)

Avi Hagai, Boaz Patt-shamir

Abstract—We propose a rate controller for ATM switches. The rate controller supports multiple priorities, and dual leaky bucket (GCRA) traffic descriptors (such as VBR). While regulating each...

Average-Case Analysis of Greedy Packet Scheduling (Extended Abstract) (2000)

Zvi Lotker, Boaz Patt-Shamir

Zvi Lotker Boaz Patt-Shamir zvilo@eng.tau.ac.il boaz@eng.tau.ac.il Dept. of Electrical Engineering Tel-Aviv University Tel-Aviv 69978 Israel January 19, 2000 Abstract We study the average number of...

Optimal Smoothing Schedules for Real-Time Streams (Extended Abstract) (2000)

Yishay Mansour, Boaz Patt-Shamir, Ofer Lapid

We consider the problem of smoothing real-time streams (such as video streams), where the goal is to reproduce a variable bandwidth stream remotely, while minimizing bandwidth cost, space overhead,...

Broadcast Disks with Polynomial Cost Functions (2000)

Boaz Patt-shamir, Igor Ziper

In broadcast disk systems, information is broadcasted in a shared medium. When a client needs an item from the disk, it waits until that item is broadcasted. The fundamental algorithmic problem for...

Broadcast Disks with Polynomial Cost Functions (2000)

Amotz Bar-noy, Boaz Patt-Shamir, Igor Ziper

In broadcast disk systems, information is broadcasted in a shared medium. When a client needs an item from the disk, it waits until that item is broadcasted. The fundamental algorithmic problem for...

Optimal smoothing schedules for real-time streams (2000)

Yishay Mansour, Boaz Patt-shamir, Ofer Lapid

We consider the problem of smoothing real-time streams (such as video streams), where the goal is to reproduce a variable-bandwidth stream remotely, while minimizing bandwidth cost, space overhead,...

Facilitating Schema Evolution With Automatic Program Transformation (1999)

Michael M Werner, Professors Betty Salzberg, Boaz Patt-shamir, David Lorenz, Gene Cooperman

ii Dedicated to my wife Linda and my children Jonathan and Daniel for their encouragment and support. iii Acknowledgements I thank my advisor, Kenneth Baclawski for his support over the years that it...

Optimal and Efficient Clock Synchronization under Drifting Clocks (1999)

Rafail Ostrovsky, Boaz Patt-shamir

We consider the classical problem of clock synchronization in distributed systems. Previously, this problem was solved optimally and efficiently only in the case when all individual clocks are...

A Note on Randomized Mutual Search (1999)

Zvi Lotker, Boaz Patt-Shamir

In Mutual Search, recently introduced by Buhrman et al. in [1], static agents are searching for each other: each agent is assigned one of n locations, and the computations proceed by agents sending...

Optimal and Efficient Clock Synchronization Under Drifting Clocks (Extended Abstract) (1999)

Rafail Ostrovsky, Boaz Patt-shamir

We consider the classical problem of clock synchronization in distributed systems. Previously, this problem was solved optimally and efficiently only in the case when all individual clocks are...

A note on randomized mutual search (1999)

Zvi Lotker, Boaz Patt-shamir

In Mutual Search, recently introduced by Buhrman et al. in [1], static agents are searching for each other: each agent is assigned one of n locations, and the computations proceed by agents sending...

Stabilizing Time-Adaptive Protocols (1998)

Shay Kutten, Boaz Patt-Shamir

We study the scenario where a transient batch of faults hit a minority of the nodes in a distributed system by corrupting their state. We concentrate on the basic persistent bit problem, where the...

Jitter Control in QoS Networks (1998)

The Refinement Relation of Graph-Based Generic Programs (1998)

We study jitter control in networks with guaranteed quality of service (QoS) from the competitive analysis point of view: We propose on-line algorithms that control jitter and compare their...

Karl Lieberherr, Boaz Patt-Shamir

. version 3, Sep. 3, 98 This paper studies a particular variant of Generic Programming, called Adaptive Programming (AP). We explain the approach taken by Adaptive Programming to attain the goals set...

Jitter Control in QoS Networks (Extended Abstract) (1998)

The Las-Vegas Processor Identity Problem (How and When to Be Unique) (1998)

We study jitter control in networks guaranteeing quality of service (QoS). Jitter measures variability of delivery times in packet streams. We propose on-line algorithms that control jitter and...

Shay Kutten, Rafail Ostrovsky, Boaz Patt-Shamir

We study the problem of assigning unique identifiers to identical concurrent processes. The model considered in this paper is the asynchronous shared memory model, and the correctness requirement is...

Traversals of Object Structures: Specification and Efficient Implementation (1998)

Karl Lieberherr, Boaz Patt-Shamir

We present a new approach, called strategies, to the task of traversing object structures. In our approach traversals are defined using a high-level directed graph description, which is compiled into...

Traversals of object structures: Specification and efficient implementation (1997)

Karl Lieberherr, Boaz Patt-shamir, Doug Orleans

Separation of concerns and loose coupling of concerns are important issues in software enginnering. In this paper we show how to separate traversal-related concerns from other concerns, how to...

Yair Frankel, Boaz Patt-Shamir, Yiannis Tsiounis

We consider the k-payment problem: given a total budget of N units, the problem is to represent this budget as a set of coins, so that any k exact payments of total value at most N can be made using...

Time-Adaptive Self Stabilization (1997)

Shay Kutten Dept, Shay Kutten, Boaz Patt-shamir

We study the scenario where a transient fault hit f of the n nodes of a distributed system by corrupting their state. We consider the basic persistent bit problem, where the system is required to...

Yair Frankel Certco, Boaz Patt-shamir, Yiannis Tsiounis

We consider the k-payment problem: given a total budget of N units, the problem is to represent this budget as a set of coins, so that any k exact payments of total value at most N can be made using...

Traversals of Object Structures: Specification and Efficient Implementation (1997)

Karl Lieberherr Boaz, Boaz Patt-shamir

We present a new approach, called strategies, to the task of traversing object structures. In our approach traversals are defined using a high-level directed graph description, which is compiled into...

Time-Adaptive Self Stabilization (1997)

Shay Kutten, Boaz Patt-Shamir

We study the scenario where a transient fault hit f of the n nodes of a distributed system by corrupting their state. We consider the basic problem of persistent bit, where the system is required to...

Yair Frankel, Boaz Patt-Shamir, Yiannis Tsiounis

We consider the k-payment problem: given a total budget of N units, represent this budget as a set of coins, so that any k exact payment requests of total value at most N can be made using k disjoint...

Yair Frankel, Boaz Patt-Shamir, Yiannis Tsiounis

We consider the k-payment problem: given a total budget of N units, the problem is to represent this budget as a set of coins, so that any k exact payments of total value at most N can be made using...

A new approach to compiling adaptive programs (1996)

Jens Palsberg, Boaz Patt-shamir, Karl Lieberherr

Abstract. An adaptive program can be understood as an object-oriented program where the class graph is a parameter, and hence the class graph may be changed without changing the program. The problem...

Attacking the Software Crisis Through Adaptive Object-Oriented Programming: Further Research and Technology Transfer (1995)

Karl J. Lieberherr, William Clinger, Jens Palsberg, Boaz Patt-Shamir, Mitchell Wand

The notorious software crisis is caused by the difficulty in evolving complex software. Therefore, our research and technology transfer program attacks the problem of evolutionary design of complex...

Bounding the Unbounded (Extended Abstract) (1994)

B. Awerbuch, Baruch Awerbuch, Boaz Patt-shamir, George Varghese

Baruch Awerbuch Lab. for Computer Science MIT Boaz Patt-Shamir y Lab. for Computer Science MIT George Varghese z Dept. of Computer Science Washington University Abstract Many important protocols in...

Self-Stabilization by Local Checking and Global Reset (Extended Abstract) (1994)

Baruch Awerbuch, Boaz Patt-shamir, George Varghese, Shlomi Dolev

Baruch Awerbuch 12 , Boaz Patt-Shamir 2 , George Varghese 3 and Shlomi Dolev 45 1 Dept. of Computer Science, Johns Hopkins University 2 Lab. for Computer Science, MIT 3 Dept. of Computer Science,...

Many-to-One Packet Routing on Grids (Extended Abstract) (1994)

A Theory of Clock Synchronization (Extended Abstract) (1994)

Yishay Mansour Department of Computer Science Tel-Aviv University mansour@math.tau.ac.il Boaz Patt-Shamir College of Computer Science Northeastern University boaz@ccs.neu.edu November 29, 1994...

Boaz Patt-Shamir, Sergio Rajsbaum

We consider the problem of clock synchronization with uncertain message delays and bounded clock drifts. To analyze this classical problem we introduce a characterization theorem for the tightest...

Many-to-One Packet Routing on Grids (Extended Abstract) (1994)

Time optimal self-stabilizing synchronization (extended abstract (1993)

Yishay Mansour Department of Computer Science Tel-Aviv University mansour@math.tau.ac.il Boaz Patt-Shamir College of Computer Science Northeastern University boaz@ccs.neu.edu Abstract We study the...

Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-shamir, George Varghese

In this paper we present a time optimal self-stabilizing scheme for network synchronization. Our construction has two parts. First, we give a simple rule by which each node can compute its pulse...

Greedy Packet Scheduling on Shortest Paths (1993)

How and When to Be Unique (Extended Abstract) (1993)

We investigate the simple class of greedy scheduling algorithms, that is, algorithms that always forward a packet if they can. Assuming that only one packet can be delivered over a link in a single...

Time Optimal Self-Stabilizing Synchronization (Extended Abstract) (1993)

Shay Kutten y Rafail Ostrovsky z Boaz Patt-Shamir x TR-93-074 November, 1993 Abstract One of the fundamental problems in distributed computing is how identical processors with identical local memory...

Baruch Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, George Varghese

In the network synchronization model, each node maintains a local pulse counter such that the advance of the pulse numbers simulates the advance of a clock in a synchronous network. In this paper we...

The Las-Vegas Processor Identity Problem (How and When to Be Unique) (Extended Abstract) (1993)

The Las-Vegas Processor Identity Problem (How and When to Be Unique (1993)

Shay Kutten Rafail Ostrovsky y Boaz Patt-Shamir z T.J. Watson Research Center UC Berkeley and Lab for Computer Science IBM ICSI MIT Abstract One of the fundamental problems in distributed computing...

The Las-Vegas Processor Identity Problem (How and When to Be Unique (1993)

We study the problem of assigning unique identi ers to identical concurrent processes. The model considered in this paper is the asynchronous shared memory model, and the correctness requirement is...

Greedy Packet Scheduling on Shortest Paths (1993)

We study the classical problem of assigning unique identifiers to identical concurrent processes. In this paper, we consider the asynchronous shared memory model, and the correctness requirement is...

The Las-Vegas Processor Identity Problem (How and When to Be Unique (1993)

We investigate the simple class of greedy scheduling algorithms, that is, algorithms that always forward a packet if they can. Assuming that only one packet can be de-livered over a link in a single...

Adapting to Asynchronous Dynamic Networks (Extended Abstract) (1992)

One of the fundamental problems in distributed computing is how identical processes with identical local memory can choose unique IDs provided they can flip a coin. The variant considered in this...

Baruch Awerbuch, Boaz Patt-shamir, David Peleg, Michael Saks

Baruch Awerbuch Boaz Patt-Shamir y David Peleg z Michael Saks x Abstract The computational power of different communication models is a fundamental question in the theory of distributed computation....

Self-Stabilization By Local Checking and Correction (Extended Abstract) (1991)