Publications

@article{ARESTOS22,

title = {ARES: Adaptive, Reconfigurable, Erasure coded, Atomic Storage},

author = {Nicolas Nicolaou and Viveck Cadambe and N Prakash and Andria Trigeorgi and Kishori Konwar and Muriel Medard and Nancy Lynch},

url = {https://projects.algolysis.com/collaborate/wp-content/uploads/2022/03/2020_ACM_TOS_ARES_final.pdf},

year  = {2022},

date = {2022-06-30},

urldate = {2022-06-30},

journal = {Transactions on Storage},

keywords = {},

pubstate = {forthcoming},

tppubtype = {article}

}

@article{GEORGIOU202297,

title = {Implementing three exchange read operations for distributed atomic storage},

author = {Chryssis Georgiou and Theophanis Hadjistasi and Nicolas Nicolaou and Alexander A. Schwarzmann},

url = {https://www.sciencedirect.com/science/article/pii/S0743731522000314},

doi = {https://doi.org/10.1016/j.jpdc.2022.01.024},

issn = {0743-7315},

year  = {2022},

date = {2022-01-01},

journal = {Journal of Parallel and Distributed Computing},

volume = {163},

pages = {97-113},

abstract = {Communication latency typically dominates the performance of message-passing systems, and consequently defines the efficiency of operations of algorithms implementing atomic read/write objects in asynchronous, crash-prone, message-passing systems. Here latency is measured in terms of the number of communication exchanges (or simply exchanges) involved in each operation. We present four algorithms, two for the single-writer/multiple-reader (SWMR) and two for the multi-writer/multiple-reader (MWMR) settings, that allow reads to take two or three exchanges, advancing the state-of-the-art in this area. Writes take the same number of exchanges as in prior works (i.e., two for SWMR and four for MWMR settings). In contrast with existing efficient implementations, ours come with no constraints on reader participation in both settings, and on the number of writers in the MWMR setting. Correctness of algorithms is rigorously argued. We conclude with an empirical study demonstrating the practicality of the algorithms, and identifying settings in which their read performance, is clearly superior compared to relevant algorithms.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{anta_tractable_2020,

title = {Tractable low-delay atomic memory},

author = {Antonio Fernández Anta and Theophanis Hadjistasi and Nicolas Nicolaou and Alexandru Popa and Alexander A Schwarzmann},

url = {https://projects.algolysis.com/collaborate/wp-content/uploads/2020/06/main.pdf},

doi = {10.1007/s00446-020-00379-y},

issn = {0178-2770},

year  = {2020},

date = {2020-05-26},

journal = {Distributed Computing},

pages = {1--26},

abstract = {Communication cost is the most commonly used metric in assessing the efficiency of operations in distributed algorithms for message-passing environments. In doing so, the standing assumption is that the cost of local computation is negligible compared to the cost of communication. However, in many cases, operation implementations rely on complex computations that should not be ignored. Therefore, a more accurate assessment of operation efficiency should account for both computation and communication costs. This paper focuses on the efficiency of read and write operations in emulations of atomic read/write shared memory in the asynchronous, message-passing, crash-prone environment. The much celebrated work by Dutta et al. presented an implementation in this setting where all read and write operations could complete in just a single communication round-trip. Such operations where characterized for the first time as fast. At its heart, the work by Dutta et al. used a predicate to achieve that performance. We show that the predicate is computationally intractable by defining an equivalent problem and reducing it to Maximum Biclique, a known NP-hard problem. We derive a new, computationally tractable predicate, and an algorithm to compute it in linear time. The proposed predicate is used to develop three algorithms: ccFast, ccHybrid, and OhFast. ccFast is similar to the algorithm of Dutta et al. with the main difference being the use of the new predicate for reduced computational complexity. All operations in ccFast are fast, and particular constraints apply in the number of participants. ccHybrid and OhFast, allow some operations to be “slow”, enabling unbounded participants in the service. ccHybrid is a “multi-speed” version of ccFast, where the reader determines when it is not safe to complete a read operation in a single communication round-trip. OhFast, expedites algorithm OhSam of Hadjistasi et al. by placing the developed predicate at the servers instead of clients and avoiding excessive server communication when possible. An experimental evaluation using NS3 compares algorithms ccHybrid and OhFast to the classic algorithm ABD of Attiya et al., the algorithm Sf of Georgiou et al. (the first “semifast” algorithm, allowing both fast and slow operations), and algorithm OhSam. In summary, this work gives the new meaning to the term fast by assessing both the communication and the computation efficiency of each operation.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}