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
each message delivery to members of a multicast group as a transaction -
an atomic, consistent and isolated action. A multicast transaction can
be viewed as an atomic transition of the 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]
should satisfy one of the following equations:
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 the
committed (aborted) or failed state.
Thus, for each member of the group, outcome of the transaction can
be commit, abort or a 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 a member transitioned into a wrong
state, it is guaranteed to fail instead of delivering a wrong result.
In order to achieve such an error detection in a decentralized
environment, certain limitations were 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 a 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
The current implementation is in a 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
the corresponding README.
--
Boris Kolpackov <boris@dre.vanderbilt.edu>
|
