1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
Architecture
TMCast (stands for Transaction MultiCast) is an implementation of a
transactional multicast protocol. In essence, the idea is to represent
message delivery to members of a multicast group as a transaction -
atomic, consistent and isolated action. Multicast transaction can
be viewed as an atomic transition of group members to a new state.
If we define Mo as a set of operational (non-faulty) members of the
group, Mf as a set of faulty members of the group, Ma as a set of
members that view transition Tn as aborted and Mc as a set of members
that view transition Tn as committed, then this atomic transition Tn
can be described as one of the following:
Mo(Tn-1) = Ma(T) U Mf(T)
Mo(Tn-1) = Mc(T) U Mf(T)
Or, in other words, after transaction T has been committed (aborted),
all operational (before transaction T) members are either in
committed (aborted) or failed state.
Thus, for each member of the group, outcome of the transaction can
be commit, abort or member failure. It is important for a member
to exhibit a failfast (error latency is less than transaction cycle)
behavior. Or, in other words, if the member transitioned into a wrong
state, it is guaranteed to fail instead of delivering wrong result.
In order to achieve such error detection in decentralized environment,
certain limitations should be imposed. One of the most user-visible
limitation is the fact that the lifetime of the group with only
one member is very short. This is because there is not way for a
member to distinguish "no members yet" case from "my link to the
group is down". In such situation, the member assumes the latter case.
There is also a military saying that puts it quite nicely: two is one,
one is nothing.
State of Implementation
Current implementation is in prototypical stage. The following parts
are not implemented or still under development:
* Handling of network partitioning (TODO)
* Redundant network support (TODO)
* Member failure detection (partial implementation)
Examples
There is a simple example available in examples/TMCast/Member with
corresponding README.
--
Boris Kolpackov <boris@dre.vanderbilt.edu>
|
