Emulators that translate algorithms from the shared-memory model to two different message-passing models are presented. Both achieved by implementing a wait-free, atomic, single-writer multi-reader register in unreliable, asynchronous networks. The considered complete network with processor failures and an arbitrary dynamic link failures. These results make it possible view as higher-level language for designing distributed systems. Any wait-free algorithm based on registers can be...

We present a general framework for solving resource allocation and scheduling problems. Given of fixed size, we algorithms that approximate the maximum throughput or minimum loss by constant factor. Our approximation factors apply to many problems, among which are: (i) real-time jobs on parallel machines, (ii) bandwidth sessions between two endpoints, (iii) caching, (iv) dynamic storage allocation, (v) optical line ring topologies. For some these problems provide first factor algorithm. are...

This paper is concerned with the solvability of problem processor renaming in unreliable, completely asynchronous distributed systems. Fischer et al. prove [8] that “nontrivial consensus” cannot be attained such systems, even when only a single, benign failure possible. In contrast, this shows problems can solved presence up to t < n /2 faulty processors, contradicting widely held belief no nontrivial system. The deal processors so as reduce size initial name space. When uniqueness new...

One of the main goals sensor networks is to provide accurate information about a sensing field for an extended period time. This requires collecting measurements from as many sensors possible have better view surroundings. However, due energy limitations and prolong network lifetime, number active should be kept minimum. To resolve this conflict interest, selection schemes are used. In paper, we survey different that used select sensors. Based on purpose selection, classify into (1) coverage...

Article Free Access Share on Designing broadcasting algorithms in the postal model for message-passing systems Authors: Amotz Bar-Noy View Profile , Shlomo Kipnis Authors Info & Claims SPAA '92: Proceedings of fourth annual ACM symposium Parallel and architecturesJune 1992 Pages 13–22https://doi.org/10.1145/140901.140903Published:01 June 1992Publication History 76citation498DownloadsMetricsTotal Citations76Total Downloads498Last 12 Months26Last 6 weeks2 Get Citation AlertsNew Alert...

We consider the following fundamental scheduling problem. The input to problem consists of n jobs and k machines. Each is associated with a release time, deadline, weight, processing time on each goal find nonpreemptive schedule that maximizes weight meet their respective deadlines. give constant factor approximation algorithms for four variants problem, depending type machines (identical vs. unrelated) arbitrary). All these are known be NP-hard, two involving unrelated also MAX-SNP hard....

We study the problem of scheduling activities several types under constraint that, at most, a fixed number can be scheduled in any single time slot. Any given activity type is associated with service cost and an operating that increases linearly slots since last this type. The to find optimal schedule minimizes long-run average per Applications such model are maintenance machines, multi-item replenishment stock, minimizing mean response Broadcast Disks. Disks recently gained lot attention...

Tracking strategies for mobile wireless networks are studied. A cellular architecture in which base stations that interconnected by a wired network communicate with units via links is assumed. The cost of utilizing the actual tracking users considered. strategy subset all selected and designed as reporting centers proposed. Mobile transmit update messages only upon entering cells centers, while every search user restricted to vicinity center last reported. It shown that, an arbitrary...

Tracking strategies for mobile users in wireless networks are studied. In order to save the cost of using links should not update their location whenever they cross boundaries adjacent cells. The paper focuses on three natural which make decisions when and where update: time-based strategy, number movements-based distance-based strategy. authors consider both memoryless movement patterns movements with Markovian memory along a topology cells arranged as ring. They analyze performance each...

Article Free Access Share on Shifting gears: changing algorithms the fly to expedite Byzantine agreement Authors: Amotz Bar-Noy Hebrew University UniversityView Profile , Danny Dolev Cynthia Dwork IBM Almaden Research Center CenterView H. Raymond Strong Authors Info & Claims PODC '87: Proceedings of sixth annual ACM Symposium Principles distributed computingDecember 1987 Pages 42–51https://doi.org/10.1145/41840.41844Online:01 December 1987Publication History...

Suppose that a road map is given in which each associated with the time it takes to traverse it. However, this unreliable; some of roads might be unsuitable for travel at certain times, and such blockage would revealed only upon reaching an adjacent site. The Canadian Traveller Problem devise strategy guarantee good path between two sites uncertainty. l?apadirnitriou Yannakakis proved if number blocked not fixed, then devising guarantees competitive ratio PSPACEcompIete. In paper, we study...

Tracking strategies for mobile wireless networks are studied, assuming a cellular architecture where base stations interconnected by wired network communicate with units via links. The cost of utilizing the links actual tracking users is investigated. A strategy in which subset all selected and designated as reporting centers proposed. Mobile transmit update messages only upon entering cells centers, while every search user restricted to vicinity center last reported. It shown that an...

In a hierarchical server environment jobs are to be assigned in an on-line fashion collection of servers which form hierarchy capability: each job requests specific meeting its needs, but the system is free assign it either that or any other higher hierarchy. Each carries certain load, imparts to. The goal find competitive assignment maximum total load on minimized. We consider linear totally ordered terms their capabilities. investigate several variants problem. unweighted (as opposed...

This paper studies the problem of dedicating routes to connections in optical networks. In networks, vast bandwidth available an fiber is utilized by partitioning it into several channels, each at a different wavelength. A connection between two nodes assigned specific wavelength, with constraint that no sharing link network can be same considers networks and without switches, types routing these It presents optimal or near-optimal constructions cases algorithms for connections, specifically...

In designing a routing scheme for communication network it is desirable to use as short possible paths messages, while keeping the information stored in processors' local memory succinct possible. The efficiency of measured terms its stretch factor - maximum ratio between cost route computed by and that cheapest path connecting same pair vertices.

The paper deals with achievability of fault tolerant goals in a completely asynchronous distributed system. Fischer, Lynch, and Paterson [FLP] proved that such system "nontrivial agreement" cannot be achieved even the (possible) presence single "benign" fault. In contrast, we exhibit two pairs are achievable up to t ≪ n/2 faulty processors, contradicting widely held assumption no nontrivial attainable first pair renaming processors so as reduce size initial name space. When only uniqueness...