Information Technology Reference
In-Depth Information
w7
3
14
w3
w4
w5
w6
13
12
9
6
2
2
w2
3
w1
3
4
3
1
0
11 1
2
1 11 1
1
1
211
2
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
v11
v12
v13
v14
FIGURE 3.2
Example of rank-based skip list.
data. They used rank-based authenticated skip lists (Figure 3.2) and aggre-
gate signatures [6]. Before discussing the scheme, we discuss authenticated
skip lists and aggregate signatures.
Skip lists [29] are a probabilistic alternative to balanced trees. Balancing
a data structure probabilistically is easier than explicitly maintaining the
balance and is easy to implement. Skip lists are also space efficient. In a skip
list, each node
v
stores two pointers, denoted
rgt
(
v
) and
dwn
(
v
), that are used
for searching.
l
(
v
) is the level of the node
v
;
l
= 0 denotes the leaf nodes.
An authenticated skip list that uses a collision-resistant hash function can be
used to check the integrity of file blocks.
3.4.2 Rank-Based Skip Lists
Let
F
be a file consisting of
n
blocks
m
1
,
m
2
, … ,
m
n
. At the
i
ith bottom-level
node of the skip list, the signature
x
(
m
i
) of block
m
i
is stored. Block
m
i
is stored
separately at the cloud. Each node
v
of the skip list stores the number of
nodes at the bottom level that can be reached from
v
. This value is called the
rank
of
v
and is denoted by
r
(
v
).
The top leftmost node of a skip list is referred to as the start node. For a
node
v
,
low
(
v
) and
high
(
v
) denote the indices of the leftmost and rightmost
nodes at the bottom level reachable from
v
, respectively. Clearly, for the start
node
S
of the skip list,
r
(
S
) =
n
,
low
(
S
) = 1, and
high
(
S
) =
n
. Using the ranks
stored at the nodes, the
i
ith node of the bottom level can be reached by tra-
versing a path that begins at the start node as follows: For the current node
v
,
assume that
low
(
v
) and
high
(
v
) are known.
Let
w
=
rgt
(
v
) and
z
=
dwn
(
v
).The following values are set:
()
=
() ()
=
()
−
()
+
()
=
high w ighv
,
loww
high vrw
1
()
+
()
−
()
=
()
high zlo
wwv
rz
1,
lowz
lowv
Search WWH ::
Custom Search