Fast Collect in the absence of contention
Tóm tắt
We present a generic module, called Fast Collect. Fast Collect is an implementation of single-writer multi-reader (SWMR) shared-memory in an asynchronous system in which a processor updates its cell and then reads in any order all the other cells. Our simple implementation of Fast Collect uses some multiwriter multi-reader (MWMR) variables and one local Boolean per processor, such that eventually, in the absence of contention, i.e. if only a single processor repeatedly performs collect, the amortized cost per each collect is a constant. With the example of Disk Paxos we show how Fast Collect can be used as a building block in wait-free algorithms.
Từ khóa
#Concurrent computing #Costs #Software algorithms #Adaptive algorithm #Chromium #Distributed algorithms #Computer bugs #Mathematics #Computer science #Steady-stateTài liệu tham khảo
gafni, 2000, Disk Paxos.In Maurice Herlihy, Proceedings of the 14th International Conference on Distributed Computing (DISC 2000), 1914, 330
10.1145/7351.7352
10.1145/279227.279229
lampson, 1996, How to build a highly available system using consensus, Distributed Algorithms, 1151, 1, 10.1007/3-540-61769-8_1
10.1145/237090.237157
10.1016/0020-0190(93)90015-2
chandramohan, 1997, Frangipani: A scalable distributed file system, Proceedings of the 16th ACM Symposium on Operating System Principles, 224
afek, 1997, Disentangling multi-object operations, Proc 6th Annu ACM Symp Principles Distributed Comput, 111
10.1145/301308.301338
10.1145/248052.248097
10.1109/SFFCS.1999.814598
de prisco, 1997, Revisiting the Paxos algorithm. In Marios Mavronico-las and Philippas Tsigas, Proceedings of the 11th International Workshop on Distributed Algorithms (WDAG 97) volume 1320 of Lecture Notes in Computer Science, 111
attiya, 1998, Adaptive wait-free algorithms for lattice agreement and renaming, Proc 7th Annual ACM Symp on Principles of Distributed Computing, 277
10.1145/225058.225271
10.1145/301308.301335
10.1145/3149.214121