共享資源同步是一個在共享記憶體環境或分散式記憶體環境中都被深入研究的問題。許多同步機制被提出，各自以自己的方式達到某種一致性級別。本論文進一步發現，並不存在完美的同步機制。每種機制都有其屬性在不同的級別上。例如，要強制強一致性，寫入者可能會喪失寫入自由，或者需要花費更多的時間進行協調。因此限制使同步機制並無法讓每一個屬性在其最佳水平上，而先前已有作品提出CAP與ROLL定理來說明。CAP定理說明只能實現一致性，可用性和分區容錯性屬性中的兩種。ROLL定理使用一個框架來模擬無領導者的SMR協議，並聲稱quorum大小和容錯能力是互相取捨的。本論文提出一個框架，以一種正規的方式將所有同步機制泛化，以便從多寫入者到單一寫入者收斂的角度，對屬性進行更好的推理。除此之外，本論文中以更容易理解的方式涵蓋五個屬性，並透過分析來改進現有同步機制。

Shared resources synchronization is a well studied problem, in both shared memory environment or distributed memory environment. Many synchronization mechanisms are proposed, with their own way to reach certain consistency level. This thesis further found that there is no perfect synchronization mechanism. Each of them has its properties at different level. For example, to enforce strong consistency, writers may loose writing freedom or it would take more time to coordinate. This thesis proposes a framework to generalize all synchronization mechanism in a formal way for better reasoning on properties, from the perspective of multi-writer to single-writer convergence. Therefore, limitations prevent a synchronization mechanism from achieving every property at its optimal level. CAP and ROLL were proposed in previous works to explain such. CAP theorem states that it can only achieve two of Consistency, Availability and Partition tolerance properties. ROLL Theorem uses a framework to model leaderless SMR protocol and states quorum size and fault tolerance are trading off. The thesis covers five properties in a more understandable way and improves existed mechanisms by analyzing with the framework.

[1] James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. Spanner: Google’s globally distributed database. ACM Trans. Comput. Syst., 31(3), aug 2013.
[2] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382, apr 1985.
[3] ISO. ISO/IEC 9899:2011: Programming Languages — C. December 2011. Available in electronic form for online purchase at https://www.iso.org/standard/74528.html.
[4] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558–565, jul 1978.
[5] Leslie Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133–169, may 1998.
[6] Leslie Lamport. Generalized consensus and paxos. 2005.
[7] Iulian Moraru, David G. Andersen, and Michael Kaminsky. There is more consensus in egalitarian parliaments. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, SOSP ’13, page 358–372, New York, NY, USA, 2013. Association for Computing Machinery.
[8] Brian M. Oki and Barbara H. Liskov. Viewstamped replication: A new primary copy method to support highly-available distributed systems. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC ’88, page 8–17, New York, NY, USA, 1988. Association for Computing Machinery.
[9] Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In 2014 USENIX Annual Technical Conference (USENIX ATC 14), pages 305–319, Philadelphia, PA, June 2014. USENIX Association.
[10] Tuanir Fran ̧ca Rezende and Pierre Sutra. Leaderless state-machine replication: Specification, properties, limits (extended version), 2020.
[11] Marc Shapiro, Nuno Pregui ̧ca, Carlos Baquero, and Marek Zawirski. Conflict-free replicated data types. In Xavier D ́efago, Franck Petit, and Vincent Villain, editors, Stabilization, Safety, and Security of Distributed Systems, pages 386–400, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
[12] Sarah Tollman, Seo Jin Park, and John Ousterhout. EPaxos revisited. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21), pages 613–632. USENIX Association, April 2021.
[13] Paolo Viotti and Marko Vukoli ́c. Consistency in non-transactional distributed storage systems. ACM Comput. Surv., 49(1), jun 2016.