^January February – 2005 ^March

Counting is a well-studied distributed problem. It is central to many basic distributed coordination problems. Some examples are dynamic load-balancing, queues and barrier synchronization.

Many attempts have been made to devise efficient distributed algorithms for counting. For all known algorithms, the time taken to read & increment the counter is at least $n$ in the worst case, where $n$ is the number of processes that share the counter. Time includes both the number of accesses to shared memory and waiting caused by contention with other processes that are accessing the same memory location at the same time.

In this talk we present two lower bound results for implementations of distributed counters. Both lower bounds are for general classes of distributed objects that contain counters.

The first result, from 2002, was the first time lower bound for implementations of counters, stacks and queues that can use arbitrary synchronization primitives. It establishes an $\Omega(\sqrt n)$ bound for implementations of these objects.

The second, recent, result proves a lower bound of $n$ on a somewhat more restricted set of objects. This lower bound matches the best algorithms for distributed counting and also holds for implementations that can use arbitrary synchronization primitives. The result implies that distributed counting is inherently sequential, at least in terms of worst case time complexity.

The presentation is for a general audience and no prior knowledge of distributed systems is assumed.

Joint work with Faith Ellen Fich and Nir Shavit

http://www.cs.toronto.edu/~hendler/

Short Bio:

Danny Hendler is a post-doctoral fellow in the University of Toronto. Since being released from the IDF in 1983, he has been working in the Israeli high-tech industry, serving in both technical and managerial positions in companies such as Elscint, Telrad, National Seminconductor and Sun Microsystems. In 2001 he returned to Academy to pursue his Ph.D. in Tel-Aviv University under the supervision of Prof. Nir Shavit. His current research focuses on lower bounds and algorithms for distributed systems and dynamic load balancing.

Recent years have seen the emergence of huge distributed systems such as peer-to-peer systems, sensor and ad-hoc networks, and grid systems. Often, these systems produce and store huge amounts of data. Therefore, data access is one of the main services they need to support. More often then not, a user of such a system would access the data in order to analyze it rather than to review it. In such cases, it would make sense to employ data mining algorithms which will analyze the data in-network and only report the result.

This presentation will outline some of the progress we have made as to the development of data mining algorithms suitable for large-scale distributed systems. Specifically, new work on facility location in peer-to-peer and sensor networks. The basic approach we take is to develop local algorithms for these problems. Local algorithms are ones in which each processor typically computes the result based on data it gathers from just a handful of nearby processors. Yet, the algorithms still provide a strong correctness guarantee – that eventually each processor will compute the exact result. The algorithms we develop are entirely asynchronous, pose modest memory requirements, and seamlessly support fail-safe failures and dynamic changes to the data.

This research extends previous work on association rule mining in peer-to-peer networks, which will be briefly reviewed. Other than that it is self contained.

The research is joined work with Denis Krivitski and Prof. Assaf Schuster of the Technion.

Bio:

Ran Wolff has graduated his B.A. and his Ph.D. in computer science from the Technion - Israel. He has numerous publications in the area of data mining and local algorithms for peer-to-peer, Grid, and sensor networks. Currently he is holding a post doctoral position in the University of Maryland, Baltimore County under the supervision of Prof. Hillol Kargupta.

Further details and publication list can be found at http://www.cs.technion.ac.il/~ranw

This talk surveys the state-of-the-art in advanced techniques for probabilistic performance evaluation models of various computer systems. The performance evaluation model is considered as a set of some "particular" models, both descriptive and numerical ones. which are used during a target CS designing process. This particular model set includes informal conceptual models of the target system, a formal specification of the target system by using of some modeling language (e.g., Stocahstic Petri Net (SPN), stochastic Process Algebra, etc.), some mathematical models derived from the specifications. Difference aspects of subordination and compatibility of various components of a whole performance evaluation model will be considered.

As the real performance evaluation process deals usually with a benchmarking, some aspects of a benchmarks choice methodology which is based on a probabilistic performance measure will be considered too.

Senior Researcher of the Institute of Informatics Problems, Russian Academy of Science (IPIRAN),Docent of the Faculty of Computer Science of the Moscow State Technical University "MIREA".

Research Interest:

probabilistic and statistic methods in scientific and applied researches;

performance evaluation;

computer-aided verification-and-testing of software and hardware;

probabilistic methods of testability analysis;

mathematical issues of computer graphics.

Teaching:

1. Mathematical methods of computer graphics.

2. Performance evaluation for graphical systems.

We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of $O(m+n\log n)$ and a worst-case query time of $O(n)$, where $m$ is the (current) number of edges in the graph, and $n$ is the number of vertices in the graph. Each update operation either inserts a set of edges that touch the same vertex, or deletes an arbitrary set of edges. The algorithm is deterministic and uses fairly simple data structures. This is the first algorithm that breaks the $O(n^2)$ update barrier for all graphs with $o(n^2)$ edges.

One of the ingredients used by this new algorithm may be interesting in its own right. It is a new dynamic algorithm for strong connectivity in directed graphs with an interesting persistency property. Each insert operation creates a new version of the graph. A delete operation deletes edges from all versions. Strong connectivity queries can be made on each version of the graph. The algorithm handles each update in $O(m\alpha(m,n))$ amortized time, and each query in $O(1)$ time. Note that the update time of $O(m\alpha(m,n))$, in case of a delete operation, is the time needed for updating all versions of the graph.

This is a joint work with Uri Zwick

Bio:
Liam Roditty is a PhD student under the supervision of Prof. Uri Zwick in Tel-Aviv university. His research is focused on graph algorithms.