Transcript Document

Scheduling of parallel processes
Antal Iványi and Rudolf Szendrei
Department of Computer Algebra, Eötvös Loránd University
[email protected] and [email protected]
Scheduling of parallel processes








Introduction
Basic concepts
Aims of the investigations
Algorithms
Mathematical results
Results of simulation
Summary
References
3
4
10
11
24
32
39
40
2
Introduction

Our problem originates in physics: percolation is the physical
process when liquid flows through a porous media (see
percolator in US)

Our mathematical model describes also parallel processes
using a resource requireing mutual exclusion

A simple interpretation: two philosophers (A and B) have a
conversation. Both have a plan (A a sequence a and B a
sequence b) of zeros and ones, where ai=1 means that A
wishes to speak in the i-th time unit and aj=0 means that A do
not wish to speak in the j-th time unit
An important property of our philosophers is that they are
ready to delay their silent periods to the end of the
conversation.
3
Basic concepts/1
A binary matrix A of size m×n is called
 r-good, if it contains at most r 1’s in each column;
 r-safe, if for any k (k = 1, 2, …, n) holds, that the first k
columns of the matrix contains at most kr 1’s;
 r-schedulable (or Winkler-schedulable or compatible), if it can be transformed into an r-good matrix
repeating the following operation: we remove any zero
element aij=0, shift the elements ai,j+1 , …, ai,n to left and
add a new element ain=0 to the i-th row of the matrix
4
Basic concepts/2
Example of a good matrix: [m = 2, n = 4, r = 1]
1
0
0
1
0
0
1
0
Example of a safe but not good matrix:
1
0
0
0
1
1
0
1
5
Basic concepts/3
The previous matrix is not only a safe, but at the same time
also a schedulable matrix too:
1
0
1
0
0
0
1
1
Shifting the second element of the first row results the
following good matrix:
1
1
0
0
0
0
1
1
6
Basic concepts/4
Let m és n be positive integers, let r (0 ≤ r ≤ m) be a
real number and let
Z
z 11
z 21
...
z m1
z 12
z 22
...
z m2
...
...
...
...
z 1n
z 2n
...
z mn
be a matrix containing independent random variables zij having
joint distribution
P zi j k
p,
q 1
p,
k 1, 1
k 0, 1
i
i
m, 1
m, 1
j
j
n,
n
7
Basic concepts/5
Let matrix A be a concrete realization of the matrix Z.
 Let the number of different m×n sized r-good matrices
by Gr(m, n), and the probability that Z is r-good by
gr(m, n, p).
 Let the number of different m×n sized r-safe matrices
denoted by Sr(m,n), and the probability that Z is r-safe
by sr(m, n, p).
 Let the number of different m×n sized r-schedulable
matrices be denoted by Wr(m,n), and the probability
that matrix Z is r-schedulable by
wr(m,n,p). The
function wr(m,n,p) is called r-schedulability function.
8
Basic concepts/6

The functions gr(m,n,p), wr(m,n,p) and sr(m,n,p) functions are
called density functions. The asymptotic density functions of the
good, safe and schedulable matrices are defined as
gr m, p lim gr m,n, p ,
n
sr m, p lim sr m,n, p ,
n
.
wr m, p limwr m,n, p
n

The following supremums are called critical probabilities:
w crit , r m
sup p w r m , p
0 ,
g crit , r m
sup p g r m , p
0 ,
s crit , r m
sup p s r m , p
0
9
AIMS OF THE INVESTIGATIONS
Starting point of our investigations is a paper of Péter Gács [7], containing
the proof of the assertation that if p is small enough, then w1(2, p) > 0.
According to the proof of the theorem wcrit,1(2) ≥ 10-400 . The aims of our
work are as follows:




To propose quick algorithms to decide whether a given matrix A is r-good, r-
safe or r-schedulable;
To determine the number of different types of matrices for different parameters;
To determine (or at least to estimate) the different important probabilities –
among others the critical probability for two processes wcrit,1(2).
Remark. The special case m = 1 and r = 1 is the well-known ticket problem or
ballot problem, and the special case m = 2 and r = 1 represents the Winklermodel of percolation.

Az m ≥ 1 esetben a jó mátrixok segítségével alsó, a biztos mátrixok segítségével
felső korlátok adhatóak annak aszimptotikus valószínűségére, hogy a Z mátrix egy
konkrét realizációja 1-ütemezhető, és megadható az a kritikus valószínűség,
amelynél kisebb p-re a Z mátrix pozitív valószínűséggel 1-biztos.

Gács algoritmusánál gyorsabb algoritmust javaslunk a két dimenziós esetre, és ezt
az algoritmust kiterjesztettük tetszőleges dimenziós mátrixok vizsgálatára.
10
Algorithms/1
Good matrices

Csak azt kell megvizsgálnunk, hogy az oszlopok elemeinek
összege kisebb-e kettőnél – és csak az első olyan oszlopig
kell elmennünk, amelyre a feltétel nem teljesül.
GOOD(n)
1 for i = 1 to n
2
s := 1
3
for j = 1 to m
4
s := s + a[i, j]
5
if s > 1
6
then return „column j is black”
7 return „the matrix is good”

Rögzített m esetén ez az algoritmus legrosszabb esetben
Θ(n) ideig fut, legjobb és várható esetben pedig Θ(1) ideig.
11
Algorithms/2
Safe matrices

Oszlopfolytonosan számoljuk az egyeseket és számukat
oszloponként összehasonlítjuk az adott oszlop indexével.
SAFE(n)
1 s := 0
2 for i = 1 to n
3
for j = 1 to m
4
s := s + a[i, j]
5
if s > j
6
then return „túl sok 1-es van a j-edik oszlopban”
7 return „a mátrix biztos”

Ez az algoritmus legrosszabb esetben Θ(n) időben fut,
legjobb esetben pedig Θ(1) a futási idő.
12
Algorithms/3
Schedulability/1


Let x = (x1,…,xn) be the first, and y = (y1,…,yn) be the
second row of a binary matrix A.
At first we define a directed graph G(A)=(V,E) as follows. Let
V be the set of points (i,j) (0 ≤ i ≤ n, 0 ≤ j ≤ n) and vertices
of G(A) are as follows:
1.
if xi=yj=1, then the vertex (i - 1, j - 1) is not a starting
vertex of any edge;
2.
if xi=yj=0, then two edges start from vertex (i - 1,
j -1), one to (i, j - 1) and the other edge to (i - 1, j);
1.
if xi = 0 and yj = 1, then two edges start from vertex
(i - 1, j - 1), one to (i, j) and the other edge to
(i, j - 1);
1.
if xi=1 and yj=0, then two edges start from vertex
(i - 1, j - 1), one to (i, j) and the other edge to
(i - 1, j);
13
Algorithms/4
Schedulability/2
0
1
1
0
0
1
0
0
14
Algorithms/5
Schedulability/3

It is known [7], that a matrix A is schedulable if and only if when
the graph G(A) contains a directed path from the vertex (0,0) to a
board vertex (n, i) or (i, n).
A simple method to decide whether such directed path exists is the
following. We use a queue Q and investigate the vertex (0,0). If
vertex (0,0) is not a starting point of an edge, then matrix A is not
schedulable. Otherwise we put the endpoints of the edges starting
at (0,0) to Q.
In the following we investigate the head elements of Q: we delete
the head element from Q and put the endpoints of the vertices of
the headpoint (if there are) into Q – until we put a board vertex
(n, i) or (i, n) or the Q will be empty.
We proposed a quicker algorithm having the same quadratic
running time in the worst case, but better average running time
than the previous method. The difference between the graph G(A)
and our graph H(A) is that if xi≠yj then we put only vertex (i, j) the endpoint of the diagonal edge - into Q.
15
Algorithms/6
Schedulability

A lemma alapján megvalósított a TERMÉSZETES algoritmus,
segítségével n = 1, 2, … , 17 értékekre meghatároztam a jó
G1(2, n), a biztos S1(2, n) és az ütemezhető mátrixok W1(2,
n) számát, valamint – a p = 0.5, p = 0.3 és p = 0.25
értékek mellett – a G1(2, n, p), S1(2, n, p) és W1(2, n, p)
valószínűségeket.
16
Algorithms/7
Schedulability - NATURAL
NATURAL(m,n,p)
1
2
3
4
5
6
7
8
9
10
11
OSZLOPOSAN-ELLENŐRÍZ(m, n)
G1(m, n) := jo_matrix
S1(m, n) := biztos_matrix
W1(m, n) := komp_matrix
G1(m, n, p) := 0
S1(m, n, p) := 0
W1(m, n, p) := 0
for i = 0 to n*m
G1(m, n, p) := G1(m, n, p) + (pi + (1–p)n*m-i) * jo_szam[i]
S1(m, n, p) := S1(m, n, p) + (pi + (1–p)n*m-i) * biztos_szam[i]
W1(m, n, p) := W1(m, n, p) + (pi + (1–p)n*m-i) * komp_szam[i]
17
Algorithms/8
Schedulability - OSZLOPOSAN-ELLENŐRÍZ
OSZLOPOSAN-ELLENŐRÍZ(
m, n )
1 jo_matrix := 0
2 biztos_matrix := 0
3 komp_matrix := 0
4 for i := 0 to n*m
5
do jo_szam[i] := 0
6
bizt_szam[i] := 0
7
komp_szam[i] := 0
8 for i = 0 to n - 1
9
do oszlopok[i] := 0
10
egyesek_az_oszlopban[i] := 0
11
egyesek_idaig[i] := 0
12 STOP := 0
13 for i = 0 to m - 1
14
do STOP := (STOP << 1) + 1
...
18
Algorithms/9
Schedulability – Column-Check
...
15 while oszlopok[0] < STOP
16
do biztos_matrix := biztos_matrix + 1
17
bizt_szam[egyesek_idaig[n-1]] := bizt_szam[egyesek_idaig[n-1]] + 1
18
JO := igaz
19
i := 0
20
while i < n és JO
21
do if 1 < egyesek_az_oszlopban[i]
22
then JO ← hamis
23
i := i + 1
24
if JO
25
then jo_matrix := jo_matrix + 1
26
komp_matrix := komp_matrix + 1
27
jo_szam[egyesek_idaig[n-1]] := jo_szam[egyesek_idaig[n-1]] + 1
28
komp_szam[egyesek_idaig[n-1]] := komp_szam[egyesek_idaig[n-1]] + 1
29
else if Ütemezhető( oszlopok, m, n )
30
then komp_matrix := komp_matrix + 1
31
komp_szam[egyesek_idaig[n-1]] := komp_szam[egyesek_idaig[n-1]] + 1
...
19
Algorithms/10
Schedulability – Column-Check
...
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
for i = n - 1 downto 0
do BIZTOS := hamis
while oszlopok[i] < STOP
do egyesek := 0
oszlopok[i] := oszlopok[i] + 1
oszlop := oszlopok[i]
while oszlop ≠ 0
do if oszlop & 1
then egyesek := egyesek + 1
oszlop = oszlop >> 1
if egyesek_idaig[i] + egyesek – egyesek_az_oszlopban[i] <= i + 1
then BIZTOS := igaz
egyesek_idaig[i] := egyesek_idaig[i] + egyesek –
egyesek_az_oszlopban[i]
egyesek_az_oszlopban[i] := egyesek
for j = i + 1 to n - 1
do egyesek_idaig[j] := egyesek_idaig[i]
if i < n – 1
then for j = i + 1 to n
do oszlopok[j] := 0
egyesek_az_oszlopban[j] := 0
exit do
if BIZTOS
then exit for
20
Algorithms/11
Schedulability - Schedulable
Schedulable(
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
oszlopok, m, n )
if m < 2
then return igaz
if n < 2
then return igaz
koord1 := (0,...,0)
H := {}
H := H U koord1
while H ≠ {}
do koord1 := min(H)
H := H \ koord1
iranyok_szama := 0
hataron := 0
for i = 0 to m – 1
do leptetes = koord[i]
egyes = (oszlopok[leptetes] >> i) & 1
if leptetes >= n
then hataron = hataron + 1
if egyes ≠ 0
then iranyok_szama = iranyok_szama + 1
...
21
Algoritmhms/12
Schedulability - Schedulable
- cont.
...
20
if hataron > m – 2
21
then return igaz
22
if iranyok_szama = 0
23
then for i = 0 to m – 1
24
do if koord1[i] < n
25
then koord2 := koord1
26
koord2[i] := koord2[i] + 1
27
H := H U koord2
28
else if iranyok_szama = 1
29
then koord2 := koord1
30
for i = 0 to m – 1
31
do if koord2[i] + 1 < n
32
then koord2[i] := koord2[i] + 1
33
else koord2[i] := n
34
H := H U koord2
35 return hamis
22
Algorithms/13
Schedulability

In the graph G(A) in average (2+2+2+0)/4 = 1.5 edges per
vertex. In our H(A) graph, when xi-1 and yj-1 are different,
then it is sufficient only the edge going to the vertex (i, j).
Therefore the graph H(A) contains in average (2+1+1+0)/4
= 1 edge per vertex.

We investigated the m-dimensional generalization of the
Winkler model and the mentioned two-dimensional
algorithms.

Since our m-dimensional algorithms extends the (n + 1)m
vertices at most ones (and at each extentions investigates
at most m outgoing edges), so its running time in worst
cases O(mnm). If all elements of the investigated matrix
equals to zero, then our algorithms extend about the half of
the vertices therefore. The worst case running time is
Θ(mnm).
23
Mathematical results/1


Using different methods we investigated the asymptotic
density of the safe matrices as the function of the probability p
and number of rows m.
Some properties of the functions gr(m, n, p), wr(m, n, p) and
sr(m, n, p):
, r 0, m , p
1. n
,r
, p 0,1 ;
2.
monotone decreasing as a function of n;
monotone decreasing as a function of p;
3.
monotone decreasing as a function of m;
4.
monotone decreasing as a
5.
function of r.
+

We suppose in the following r = 1, therefore we omit the index
r.
24
Mathematical results/2
In the following we need some lemmas.

Let Cn (where n is a positive integer) the number of such binary
sequences a1, a2, … , a2n containing n zeroes and n ones so that for all
prefix a1, a2, … ak (1 ≤ k ≤ 2n) contains at most so many ones as
zeroes.

Lemma. If n ≥ 0, then
Cn
1
2n .
n 1 n
where Cn is the n’th Catalan-number.

Lemma. If 0 ≤ x ≤ 1, then
x
f x
1
x
k
0
k
2k
1 k
x 1 x
k
1
x
1,
, if
0
x
1
2
if
1
2
x
1.
25
Mathematical results/3

Lemma. If m ≥ 2, then the good matrices are schedulable,
and the schedulable matrices are safe.

Corollary. If m ≥ 2, then
g(m, n, p) ≤ w(m, n, p) ≤ s(m, n, p),
g(m, p) ≤ w(m, p) ≤ s(m, p),
gcrit(m) ≤ wcrit(m) ≤ scrit(m).


Analysis of m×n sized safe matrices in the case of m ≥ 4 is
similar to the case m = 3.
In our research we used the close connection between the
properties of safe matrices and some walking across the xaxis. If a column of A contains at least b ≥ 2 1’s then the
walking point jumps (b-2) to left; if the column contains one 1
then the point stays; and finally if the column contains m
zeroes then the walking point steps to right.
26
Mathematical results/4

Probability of the (b - 2)-sized jump to left:
m p b 2 qn
b

Probability of the step to left:
m pm 2 q2
2

Probability of the staying:
m pq m
1

And the probability of the step to right:
m qm
0
b 2
1
Taking into account the results received earlier before m = 2 and m =
3-ra we get the following general assertation.
Theorem. If m ≥ 2 and 0 ≤ p ≤ 1, then
m
s m, p
1
i 2
and
s crit
m
i
p
1 p
i
i 1
1
m
27
Mathematical results/5
Matrices with 2 rows

For the simplicity we analyse the function u(2, n, p) = 1 – s(2, n, p)
instead of s(2, n, p).

Lemma. If n ≥ 1, then
n
i 1 2
u 2, n , p
2
i 1

j
i 1 2j
C
0
j
i 1 4n i .
2j
Lemma. If 0 ≤ p ≤ 1, then
2
u 2, p
p
if
2 ,
q
1,
if
0 p
1
2
1
2
p 1.
28
Mathematical results/6
Matrices with two rows

The following figure shows the curve of the function s(2, p) in the
interval [0, ½]:

Our results imply the following estimations of the critical probability for
two rows:
1
0 g crit 2 w crit 2 s crit 2
.
2
29
Mathematical results/7
Matrices with three rows

If m = 3, then the ratio of the zeros and ones is 3:0, 2:1, 1:2 or 0:3.

In this case we order to the investigated matrix such a random walk
where

we jump to left with the probability of the column p3 of the column
containing three 1’s,

we make a step to lerft with the probability 3p2q vof the column
containing two 1’s,

we remain in the same point with the probability 3p2 of the column
containing one 1and

we make a step to right with the probability
containing threee zeros.
q3 of the column
30
Mathematical results/8
General case

If r = 1 and m ≥ 2, then the investigation of the safe matrices lets to
an asymmetric random walk starting at the origo, having sink at x=-1
and random walk is controlled by the columns of the matrix:

If the column contains one 1, then the walking point steps to right – the
corresponding probability equals to
m pq m
1

1
If the column contains k > 1 1’s, then the walking point jumps k–1 positions
to right – the corresponding probability equals to
m pk qm
k


If the column contains only zeroes, then the walking point steps to left – the
corresponding probability equals to qm.
In [9] was published the following general formula for the asymptotic
and critical probabilities of the safe matrices.
m

q
Theorem. If m ≥ 2 and 0 ≤ p ≤ 1, then
s m, p
1
i 2
m
i
p
1 p
i
i 1
s crit
1
m
31
Results of simulation/1
Matrices with two rows
Rounded data for p = 0.5 (Table 1)
n
G 2, n
T 2, n
G(2, n)
W 2,n
T 2,n
W(2, n)
S 2, n
T 2, n
S(2, n)
W 2, n
S 2, n
1
3
0.750
3
0.750
3
0.750
1
2
9
0.562
10
0.625
10
0.625
1
3
27
0.452
35
0.547
35
0.547
1
4
81
0.316
124
0.484
126
0.492
0.984
5
243
0.237
444
0.434
462
0.451
0.961
6
729
0.178
1 592
0.389
1716
0.419
0.927
7
2 187
0.133
5 731
0.350
6435
0.393
0.890
8
6 561
0.100
20 671
0.315
24310
0.371
0.850
9
19 683
0.075
74 722
0.285
92378
0.352
0.808
10
59 049
0.056
270 521
0.258
352716
0.336
0.767
11
177 147
0.042
980 751
0.234
1352078
0.322
0.725
12
531 441
0.032
3 559 538
0.212
5200300
0.310
0.684
13
1 594 323
0.022
12 931 155
0.193
20058300
0.299
0.646
14
4 782 969
0.018
47 013 033
0.175
77558760
0.289
0.606
15
14 348 907
0.013
171 036 244
0.159
300540195
0.280
0.568
32
Results of simulation/2
Matrices with two rows

According to Péter Gács [7] wcrit(2) ≥ 10-400.

Table one contains the absolute and relative frequency of good, schedulable
and safe matrices. These frequencies correspond to the probability p = 0.5
The number of the columns in the investigated matrices was 1, 2, …, 15.

Let the number of m×n sized binary matrices be denoted by T(m, n). Then
T(m, n) = 2mn.

According to the known theoretical results all the relative frequencies
G(m, n) / T(m, n), W(m, n) / T(m, n) and S(m, n) / T(m, n) have to tend to
zero as n tends to infinity. An open question is the behaviour of the fraction
W(2, n) / S(2, n).

In table two in the column of s(2, n, 0.4) the sequence has to tend to the
limit 5/9. The concrete values are far from 5/9. In table three in the column
of s(2, n, 0.35) the sequence has the limit 120/169 ~ 0.7101.
33
Results of simulation/3
Matrices with two rows
Rounded data for p = 0.4 (Table 2)
n
T(2, n)
g(2, n, 0.4)
w(2, n, 0.4)
s(2, n, 0.4)
w 2,n,0.4
s 2,n,0.4
1
4
0.8400
0.8400
0.8400
1
2
16
0.7056
0.7632
0.7632
1
3
64
0.5929
0.7171
0.7171
1
4
256
0.4979
0.6795
0.6862
0.9902
5
1 024
0.4182
0.6487
0.6639
0.9771
6
4 096
0.3513
0.6206
0.6470
0.9592
7
16 384
0.2951
0.5957
0.6339
0.9397
8
65 536
0.2479
0.5731
0.6234
0.9193
9
262 144
0.2082
0.5524
0.6149
0.8984
10
1 048 576
0.1749
0.5332
0.6078
0.8773
11
4 194 304
0.1469
0.5155
0.6019
0.8565
12
16 777 216
0.1234
0.4988
0.5967
0.8359
13
67 108 864
0.1037
0.4832
0.5924
0.8157
14
268 435 456
0.0871
0.4685
0.5886
0.7960
15
1 073 741 824
0.0731
0.4545
0.5854
0.7764
16
4 294 967 296
0.0644
0.4412
0.5825
0.7574
17
17 179 869 184
0.0516
0.4286
0.5800
0.7390
34
Results of simulation/4
Matrices with two rows
Rounded data for p = 0.35 (Table 3)
n
T(2, n)
g(2, n, 0.35)
w(2, n, 0.35)
s(2, n, 0.35)
w 2, n , 0.35
s 2, n , 0.35
1
4
0.8775
0.8775
0.8775
1
2
16
0.7700
0.8218
0.8218
1
3
64
0.6757
0.7901
0.7901
1
4
256
0.5929
0.7645
0.7699
0.9930
5
1 024
0.5203
0.7441
0.7561
0.9841
6
4 096
0.4565
0.7255
0.7462
0.9723
7
16 384
0.4006
0.7094
0.7389
0.9601
8
65 536
0.3515
0.6949
0.7334
0.9475
9
262 144
0.3085
0.6817
0.7291
0.9350
10
1 048 576
0.2707
0.6696
0.7258
0.9226
11
4 194 304
0.2375
0.6585
0.7231
0.9107
12
16 777 216
0.2048
0.6481
0.7210
0.8989
13
67 108 864
0.1839
0.6383
0.7192
0.8875
14
268 435 456
0.1605
0.6291
0.7178
0.8764
15
1 073 741 824
0.1401
0.6204
0.7166
0.8658
16
4 294 967 296
0.1236
0.6122
0.7156
0.8555
35
Results of simulation/5
Matrices with three rows
Rounded data for m = 3 és p = 0.5 (Table 4)
n
T(3, n)
G(3, n)
g(3, n, 0.5)
W(3, n)
w(3, n, 0.5)
S(3, n)
s(3, n, 0.5)
w 3,n,0.5
s 3,n, 0.5
1
8
4
0.5000
4
0.5000
4
0.5000
1
2
64
16
0.2500
19
0.2969
19
0.2969
1
3
512
64
0.1250
98
0.1914
98
0.1914
1
4
4 096
256
0.0625
525
0.1282
531
0.1296
0.9892
5
32 768
1 024
0.0312
2 884
0.0880
2 974
0.0907
0.9702
6
262 144
4 096
0.0156
16 043
0.0612
17 060
0.0651
0.9401
7
2 097 152
16 384
0.0078
90 091
0.0429
99 658
0.0475
0.9032
8
16 777 216
65 536
0.0039
507 520
0.0303
590 563
0.0352
0.8594
36
Results of simulation/6
Matrices with 3 rows
Rounded data for m = 3 and p = 0.3 (Table 5)
n
T(3, m)
g(3, n, 0.3)
w(3, n, 0.3)
s(3, n, 0.3)
w 3, n ,0.3
s 3, n, 0.3
1
8
0.7840
0.7840
0.7840
1
2
64
0.6147
0.6795
0.6795
1
3
512
0.4819
0.6153
0.6153
1
4
4 096
0.3778
0.5682
0.5710
0.9951
5
32 768
0.2962
0.5313
0.5380
0.9875
6
262 144
0.2322
0.5004
0.5125
0.9764
7
2 097 152
0.1821
0.4739
0.4919
0.9634
37
Results of simulation/7
Matrices with 3 rows
Rounded data for m = 3 and p = 0.25 (Table 6)
n
T(3, m)
1
8
2
g(3, n, 0.25)
w 3, n ,0.25
s 3, n, 0.25
w(3, n, 0.25)
s(3, n, 0.25)
0.8437
0.8437
0.8437
1
64
0.7119
0.7712
0.7712
1
3
512
0.6009
0.7286
0.7286
1
4
4 096
0.5068
0.6981
0.7004
0.9967
5
32 768
0.4276
0.6748
0.6804
0.9917
38
Summary





We determined the explicite form of the schedulability function and
determined the critical values scrit(m) for m ≥ 2. The value of
scrit(2) equals to ½ (this is a characteristic value for several
percolation model), the value of the further critical probabilities
decreases as the value of m increases.
According to our simulation experiments the critical probabilities of
the safe and schedulable matrices are near to each other and the
proved upper bounds. Table 1. contains the results for p = 0.5,
Table 2. for p = 0.4, and Table 3. for p = 0.35.
On the base of the results of the simulation we suppose that the
bound in [7] can be improved: if p < 0.4, then w(2, p) > 0.
Behaviour of the fractions w(m, p) / s(m, p) requires further
analyses.
One can be give better lower bounds than our ones, but they imply
also only the trivial lower bound zero, therefore if we wish to
improve the lower bounds of the critical probabilities of the
schedulable matrices then we need more useful matrices, than the
good matrices.
39
References/1
1.
P. Balister, B. Bollobás, M. Walters (2004), Continuum percolation with steps in
an annulus. Ann. Appl. Probab. 14/4 1869—1879. http://arxiv.org/find
2.
A. Bege and Z. Kása (2001), Coding objects related to Catalan numbers, Studia
Univ.
Babeş-Bolyai,
Informatica,
Volume
XLVI
(1),
31—39.
http://www.cs.ubbcluj.ro/~studia-i/contents.php
3.
B. Bollobás, O. Riordan (2005), A short proof of the Harris-Kesten theorem.
Electronic manuscript, http://arxiv.org/find.
4.
I. Derényi, G. Palla, T. Vicsek (2005), Clique percolation in random networks.
Phys. Rev. Lett. 94 160—202. http://arxiv.org/find.
5.
W. Feller, (1968), An Introduction to Probability Theory and its Applications.
John Wiley and Sons, New York.
6.
P. Gács (2002), Clairvoyant scheduling of random walks (submitted to Electronic
Journal of Probability). Short version: Clairvoyant scheduling of random walks.
In: Proc. of the Thirty-Fourth Annual ACM Symposium on Theory of Computing,
99—108
(electronic),
ACM,
New
York,
2002.
http://www.cs.bu.edu/fac/gacs/recent-publ.html
7.
P. Gács (2004), Compatible sequences and a slow Winkler percolation. Combin.
Probab. Comput. 13/6, 815—856. http://www.cs.bu.edu/fac/gacs/recentpubl.html.
40
References/2
8.
T. E. Harris (1960), A lower bound for the critical probability in a certain
percolation process. Proc. of the Cambridge Phil. Soc. 56 13—20.
9.
A. Iványi, Density of 2-safe matrices (manuscript)
10.
Z. Kása (2003), Combinatorică cu aplicaţii. Presa Universitară Clujeană, ClujNapoca.
11.
Z. Kása (2004), Rekurzív egyenletek. Informatikai algoritmusok. 1 (Szerk.
A. Iványi). ELTE Eötvös Kiadó, Budapest, 14—37. http://elek.inf.elte.hu/
12.
H. Kesten (1982), Percolation Theory for Mathematicians. Birkhäuser, Boston
13.
D. Schauffer (1985), Introduction to Percolation Theory. Taylor and Francis,
London.
14.
R. P. Stanley (1999), Enumerative Combinatorics, Volume 2. Cambridge Studies
in Advanced Mathematics, 62. Cambridge University Press, Cambridge
P. Winkler (2000), Dependent percolation and colliding random walks, Random
Structures & Algorithms 16/1 58—84.
http://www.math.dartmouth.edu/~pw/papers/pubs.html
15.
16.
A. Hunt (2005), Percolation Theory for Flow in Porous Media. Lecture Notes in
Physics, Vol. 674.
41