16 research outputs found
Maximal Dense Trees and Competitive On-line Selective Multicast (Extended Abstract)
No full text) Baruch Awerbuch 1;2 Yossi Azar 3 Rainer Gawlick 2 1 Johns Hopkins University 2 Laboratory for Computer Science, MIT 3 Tel-Aviv University Abstract In this paper we introduce the problem of selective multi-cast and develop the first on-line algorithm for general networks with provable performance guarantees. The essence of the problem is to maximize the number of accommodated users, in presence of bounded network resources. Our algorithm exhibits a poly-logarithmic competitive ratio in terms of the number of accepted users. The techniques and concepts used to develop the algorithm seem of interest in their own right. In particular, the new graph-theoretic concept of maximal dense subsets, introduced in this paper, motivated the first efficient approximation for the k-MST problem. Another interesting technique introduced in this paper is the aggregation of statistical information in networks, using sparse network decompositions and Chernoff bounds. 1 Introduction Motivati..
Competitive On-line Selective Multicast via Dense Trees Construction (Extended Abstract)
No full text) Baruch Awerbuch 1;2 Yossi Azar 3 Rainer Gawlick 2 1 Johns Hopkins University 2 Laboratory for Computer Science, MIT 3 Tel-Aviv University May 3, 1994 Abstract This paper introduces the problem of selective online multicast and presents an log O(1) n thruput competitive solution, which handles issues of route selection and admission control, in general networks with n nodes. For each node and each multi-cast (broadcast) group, we assume that the node has an arbitrary probability with which it wishes to join the group. 1 Introduction Motivation. The introduction of fiber technology gives rise to new applications, such as interactive TV and video-conferencing, that feature multi-point communication. Applications with multi-point communication can be modeled as sources that broadcast information to subscribing nodes along a spanning (Steiner) tree. In modern networks, (e.g., ATM networks [deP91, Bou92], high-speed networks [ACG + 90, CG88, ACG91, CGG91], or private vi..
Admission control and routing : theory and practice
No full textThesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1995.Includes bibliographical references (leaves 183-190).by Rainer Gawlick.Ph.D
Concurrent Timestamping Made Simple
No full textConcurrent Timestamp Systems (CTSS) allow processes to temporally order concurrent events in an asynchronous shared memory system. Bounded memory constructions of a CTSS are extremely powerful tools for concurrency control, and are the basis for solutions to many coordination problems including mutual exclusion, randomized consensus, and multiwriter multireader atomic registers
Liveness in Timed and Untimed Systems
No full text. We present a coordinated pair of general labeled transition system models for describing timed and untimed concurrent systems. Both of the models incorporate liveness properties as well as safety properties. The models are related via an embedding of the untimed model into the timed model, which preserves all the interesting attributes of the untimed model. Both models include notions of environment-freedom, which express the idea that the liveness properties can be guaranteed by the system, independently of the behavior of the environment in which it operates. These environment-freedom conditions are used to prove compositionality results for both models. This pair of models, which generalize several existing models, is intended to comprise a general formalism for the verification of timed and untimed concurrent systems. 1 Introduction The increasing need for reliable software has led the scientific community to develop many formalisms for verification. Particularly important are ..
On-line Admission Control and Circuit Routing for High Performance Computing and Communication
No full textThis paper considers the problems of admission control and virtual circuit routing in high performance computing and communication systems. Admission control and virtual circuit routing problems arise in numerous applications including, video-servers, real-time database servers, and the provision of permanent virtual channels in large-scale communications networks. The paper describes both upper and lower bounds on the competitive ratio of algorithms for admission control and virtual circuit routing in trees, arrays, and hypercubes (the networks most commonly used in conjunction with high performance computing and communication). Our results include the first optimal algorithms for admission control and virtual circuit routing in trees, as well as the first competitive algorithms for these problems on non-tree networks. A key result of our research is the development of on-line algorithms that substantially outperform the greedybased approaches that are used in practice
