Home > What's New? > Events > 2011 > Trade-offs in Implementing Atomic Multi-Writer, Multi-Reader Registers in Asynchronous Message-passing Systems

Trade-offs in Implementing Atomic Multi-Writer, Multi-Reader Registers in Asynchronous Message-passing Systems

Dr. Chryssis Georgiou, Assistant Professor at Department of Computer Science, University of Cyprus
17 May 2011 - 1:00pm

Room 3. 3.B01, "Sala de Juntas", Rey Pastor Building, University Carlos III of Madrid, Avda. Universidad, 30, 28911 Leganes – Madrid

​The technological advancement and information overload in recent years increased the popularity of Distributed Storage Systems where the data is replicated and maintained at multiple disks or servers residing at different network locations. While replication is sufficient to ensure data survivability, it raises an important question: "How can we efficiently maintain consistency among the replicas, despite system asynchrony and failures?"

Researches have investigated this challenging problem by studying implementations of atomic read/write registers in asynchronous message-passing systems. An atomic read/write register allows concurrent processes to share information through a common variable, as if they were accessing this variable in a sequential manner. Algorithms implementing atomic registers comprise building blocks for more complex Distributed Storage Systems. Also, they can be used directly to implement distributed file systems, which are interesting on their own right.

The efficiency of atomic read/write register implementations is measured in terms of the latency of the read and write operations. Traditional implementations of atomic Multi-Writer/Multi-Reader (MWMR) registers under crash-prone processes require two communication round-trips between the read/write clients and the servers. It has been shown that atomic MWMR implementations are not possible if all read or write operations would complete in one-round communication.

In this talk I will present two recently developed algorithms that implement atomic MWMR registers that allow some fast operations, that is, operations that complete in a single-round communication. The first algorithm allows only fast read operations, while the second algorithm allows also fast write operations. The comparison of these algorithms reveals interesting trade-offs between efficiency and deployability.

This talk in mainly based on the article “On the Efficiency of Atomic Multi-Reader, Multi-Writer Distributed Memory”, by B. Englert, C. Georgiou, P. Musial, N. Nicolaou and A. Shvartsman, which appears in the Proceedings of the 13th International Conference on Principles of Distributed Systems (OPODIS 2009).

This work is supported in part by the Cyprus Research Promotion Foundation grant ΠΕΝΕΚ/0609/31 and the European Regional Development Fund.

Who is Dr. Chryssis Georgiou?

Chryssis Georgiou is an Assistant Professor in the Department of Computer Science at the University of Cyprus. He holds a Ph.D. (December 2003) and M.Sc. (May 2002) in Computer Science and Engineering from the University of Connecticut and a B.Sc. (June 1998) in Mathematics from the University of Cyprus. He has worked as a Teaching and Research Assistant at the University of Connecticut, USA (1998-2003) and as a Visiting Lecturer (2004) and a Lecturer (2005-2008) at the University of Cyprus.
His research interests span the Theory and Practice of Fault-tolerant Distributed and Parallel Computing. He has published in top journals and conference proceedings in his area of study and he has co-authored a book on Distributed Cooperative Computing. He served on Program Committees of top conferences in Distributed Computing and he is on the Steering Committee (2010-2012) of the International Symposium on Distributed Computing (DISC).

Personal website: http://www.cs.ucy.ac.cy/~chryssis

The conference will be conducted in English

Organization: 

NETCOM Research Group (Telematics Department, University Carlos III of Madrid, Spain); Institute IMDEA Networks (Madrid, Spain)