Technical Report CS0662

TR#:CS0662
Class:CS
Title: APPROXIMATED COUNTERS AND RANDOMIZED CONSENSUS
Authors: Gabi Bracha and Ophir Rachman
PDFCS0662.pdf
Abstract: This paper introduces a new shared data-type, approximated counter. This data-type offers a tradeoff between time and accuracy in operations on shared counters in distributed shared-memory wait-free environments. We use approximated counter to improve existing solutions for a classic problem in distributed. computation- wait-free randomized consensus. Complexity analysis of this problem considers two parameters: n, the total number of processes, and p, the number of processes actively participating in the consensus algorithm. We improve the best known results for this problem from expected total time of O(np(p'l +n)) to O(n(p'l +n)) register operations.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1990/CS/CS0662), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1990
To the main CS technical reports page

Computer science department, Technion
admin