CS Other Presentations

Department of Computer Science - University of Cyprus

Besides Colloquiums, the Department of Computer Science at the University of Cyprus also holds Other Presentations (Research Seminars, PhD Defenses, Short Term Courses, Demonstrations, etc.). These presentations are given by scientists who aim to present preliminary results of their research work and/or other technical material. Other Presentations serve as a forum for educating Computer Science students and related announcements are disseminated to the Department of Computer Science (i.e., the csall list):

RSS Directions

Presentations Coordinator: Demetris Zeinalipour

Seminar: Seeking Fastness in Multiple-Writer Multiple-Reader Atomic Register Implementations, Dr. Nicolas Nicolaou (University of Cyprus, Cyprus), Tuesday, September 13, 2011, 18:00-19:00 EET.

The Department of Computer Science at the University of Cyprus cordially invites you to the Seminar entitled:

Seeking Fastness in Multiple-Writer Multiple-Reader Atomic Register Implementations

Abstract:
In this work we explore the communication and computation costs of multiple-writer multiple-reader (MWMR) atomic read/write register implementations in asynchronous message-passing systems with crash-prone processors. We consider algorithms that use quorum systems, collections of subsets of replica hosts with pairwise intersection, called quorums. A quorum system has intersection degree n (also called n-wise quorum system), if every n quorum members of this system have a non-empty intersection. <br/><br/> We introduce a new technique we call server side ordering (SSO), that transfers partial responsibility of the ordering of write operations to the replica hosts. Using this idea we design algorithm SFW that uses n-wise quorum systems and relies on predicates to allow fast read and write operations. The algorithm uses tag-value pairs to order the write operations and combines a global ordering imposed by the servers with a local ordering established by each writer participant. <br/><br/> We formulate a new combinatorial problem that captures the computational burden of evaluating the predicates in algorithm SFW and we show that it is NP-Complete. To make the evaluation of the predicates feasible, we present a polynomial log-approximation algorithm for this problem and we show how to use it with algorithm SFW. <br/><br/> We then identify that SFW allows fast operations under restrictions on the construction of the underlying quorum system. So we design an algorithm that allows some single round reads but trades the speed of write operations for removing any constraints on the quorum system construction. The new algorithm, called CwFr, incorporates Quorum Views, algorithmic techniques presented in the SWMR model to enable fast read operations. <br/><br/> Lastly we implement our algorithms in the single-processor simulator, NS2, and on the planetary-scale network platform Planetlab. NS2 helped us evaluate our algorithms under a fully controlled environment, whereas Planetlab helped the evaluation of the algorithms on real-time network infrastructures. In this talk we will present a set of representative plots that illustrate the performance of the proposed algorithms in both environments. <br/><br/> <font><b>Notice:</b>The presentation is part of the final dissemination seminar of the Research Promotion Foundation funded Project ΠΕΝΕΚ/0609/31. <br/> Refreshments will be served!</font> </b>

Short Bio:
Dr. Nicolas Nicolaou received his BSc from the Computer Science Department at the University of Cyprus in 2003 and he obtained an MSc (2006) and a Ph.D. (2011) from the Computer Science and Engineering Department at the University of Connecticut. His research interests focus in analysis, design and implementation of practical and robust distributed and parallel algorithms, algorithms in ad-hoc mobile and sensor networks and evaluation and security of voting technologies. His PhD research has been partially funded by the Cyprus Research Promotion Foundation and co-funded by the Republic of Cyprus and the European Regional Development Fund under the project ΠΕΝΕΚ/0609/31. As of September 2011, Nicolas Nicolaou will be a Visiting Lecturer at the Department of Computer Science at the University of Cyprus.

	Other Presentations Web: https://www.cs.ucy.ac.cy/colloquium/presentations.php
	Colloquia Web: https://www.cs.ucy.ac.cy/colloquium/
	Calendar: http://testing.in.cs.ucy.ac.cy/louispap/XCS-3.0/schedule/cs.ucy.pres.2011.nicolaou.ics