or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
Generalize Synchronization Mechanisms for Analyzing Properties Trade-offs and Exploring New Mechanisms
泛化同步機制以分析屬性權衡及探索新機制
(Link to the paper: https://arxiv.org/abs/2309.11972)
Introduction
The synchronization of shared resources.
The origin
Existed sync. mechanism
No perfect sync. mechanism
The proposed framework
Related works
Note:
這頁應該可以跳過
Why framework?
Our framework
Synchronization Framework
System Model
Give context
Shared memory
A register \(r\) is a sequence of memory location
\(r=\{a_1, a_2,...\}\)
Distributed memory
A valid synchronization
Synchronization is a process of Multi-writer to Single-writer convergence
How synchronization mechanisms work in general.
Properties in Synchronization Mechanisms
Properties
Consistency
ref: consistency in non-transactional Distributed storage system
The order guarantee of the result from \(read\)
Writing freedom
The amount of writers that can propose values: 1~\(n\)
Latency
Loading
Fault tolerance
At most \(f\) can fail at any moment during the sync.
If exceed, no progress or end up incorrectly
The framework
Synchronization is a process of Multi-writer to
Single-writer convergence
A valid pass of sync.
Horizontal
\(write(v, m)\)
Note:
拿 Paxos 舉例
Vertically
\(ROLL\) theorem: \(2F + f - 1 \leq n\)
Model and Analyze
Raft / Multi-Paxos
EPaxos
CRDTs
(The simplest one)
Trade-offs and limits
Observation
Analysis
Lemma 1. In the context of linearizability, the amount of fault does not exceed \(\lfloor \frac{n-1}{2} \rfloor\)
\(proof.\) By contradiction. Having half or more failed may end up with two different projection result.
Theorem 1. Under n writing freedom, one round trip is optimal for deciding to write or abort.
\(proof.\) The arbitration rule determines to response negative message to all the other writers except the converged writer as positive.
Theorem 2. To decide a dynamic arbiter, \(2(n − |Q|) + f − 2 < n\) needs to be satisfied
\(proof.\) Writers without facts: \(2(n − |Q|)\), faulty writers: \(f\). Exclude 2 writer for having additional facts.
Theorem 3. To decide a static arbiter, \((n − |Q|) + f \leq \lceil \frac{n-1}{2} \rceil\) needs to be satisfied.
\(proof.\) Writers without facts: \((n − |Q|)\), faulty writers: \(f\). According to Lemma 1, to have sufficient writers to fail, the combination should not exceed \(\lceil \frac{n-1}{2} \rceil\)
The Discussion
Extra findings and details
Exploring New Mechanism
Use priority tree to resolve conflict locally. Order conflict writes by applying fixed priority.
Future work
The end
Special Thanks
Thanks Prof. Chen for allowing me to research the topic I've been looking forward to studying.
Thanks Prof. Hsieh for emphasizing the importance of simplicity during graph theory course.
FAQ
Without the guarantee on both correctness and progression, the mechanisms can easily be designed to have any property at optimal level. Correctness and progression come at a price only when they are guaranteed, so that there are trade-offs and limits.