Kalite Fonksiyon Yayılımı için Yeni Bir Yaklaşım

Görevdeş (P2P) Ağlarda Sık Bulunan Öğelerin Belirlenmesine
Dağıtık Yaklaşım
Emrah Çem1, Öznur Özkasap2
Koç Üniversitesi, Bilgisayar Mühendisliği Bölümü, İstanbul
1,2
[email protected], [email protected]
Özet: Birçok geniş ölçekli P2P uygulama, veri erişim sıklığı, sorgu ve olay sayısı gibi sistem
genelindeki bilgileri kullanmaya gereksinim duymaktadır. Sistem genelinde belirli bir eşik
değerinden daha fazla bulunan öğeler sık ya da popüler öğeler olarak adlandırılır. Popüler
öğelerin etkin şekilde belirlenmesi görevdeş ağlar için önemli bir servis olacaktır. Ayrıca, bu
problem veritabanı uygulamaları, algılayıcı ağlar ve güvenlik mekanizmalarına uyarlanabilir
olmasından dolayı önemlidir. Bu bildiride görevdeş ağlarda popüler öğelerin belirlenmesinin
önemi, kullanım alanları, ortaya konan çalışmaların özellikleri ve önerdiğimiz dağıtık yaklaşım
anlatılmaktadır.
Anahtar Sözcükler: Dağıtık Sistemler, Görevdeş (P2P) ağlar, Kümeleme,
Popüler öğeler.
A Distributed Approach for Discovering Frequent Items in Peer-to-Peer (P2P) Networks
Abstract: Several P2P applications require a global view of the information such as data
access frequencies, query and event counts, that are available locally and partially at peers.
Items that globally occur more than a threshold value are referred as frequent or popular.
Efficiently discovering frequent items would be a valuable service for peers. Being significant
for P2P systems, frequent item discovery problem is also applicable to distributed database
applications, sensor networks, and security mechanisms in which identifying frequently
occurring items in the entire system is very useful. In this study, application areas and
importance of discovering frequent items, related works and proposed distributed approach are
introduced.
Keywords: Distributed Systems, Peer-to-peer networks, Aggregate computation,
Popular items.
1. Giriş
Ağlardaki bilgi hacmi arttıkça bilginin
tamamının tek bir bilgisayarda merkezi
olarak tutulması olanaksız hale gelmiştir.
Bilgi hacmindeki bu artış görevdeş ağlar ve
kablosuz algılayıcı ağları gibi dağıtık
sistemlerin ortaya çıkmasının nedenlerinden
biridir. Bunun sonucunda,dağıtık sistemlerde,
özellikle geniş ölçekli P2P ağlarda, bilgi
ağdaki eşlere yayılmış durumda olduğu için,
sistem hakkında genel bilgi sahibi olma
konusu önemli bir problem haline gelmiştir.
Görevdeş ağlarda sık bulunan öğelerin
belirlenmesi
genel
bilgiye
ulaşma
problemlerinden bir tanesidir. Sık bulunan
öğeler, kullanıcının seçtiği eşik değerine göre
belirlenir. Bu eşik değerinden daha sık
rastlanan öğeler „popüler öğe‟ olarak
adlandırılır. Eşik değeri 2 türlü tanımlanabilir
[9]. Birinci yöntem, eşik değerini sitemdeki
öğelerin sayısı ve dağılımından bağımsız,
sabit bir sayı olarak belirlemektir. Bu yöntem
sabit eşik yöntemi olarak adlandırılır. İkinci
yöntem ise, eşik değerini sistemdeki öğelerin
dağılımına
ve
yoğunluğuna
göre
belirlemektir. Bu yöntem ise göreli eşik
yöntemi olarak adlandırılır.
Popüler öğelerin belirlenmesi problemi
sadece görevdeş ağlarda değil, ayrıca
veritabanı uygulamalarında, algılayıcı ağlarda
[4]; hatta bazı gerçek senaryolarda da
kullanilabilir. Örneğin, bir anayoldaki araç
sayısı eşik değerini geçtiğinde veya bir
bölgede sınırı geçen asker sayısının eşik
değerinin üstüne çıktığında uyarı verilmesi
[8].
Ayrıca
bir
bölgedeki
sıcaklık
algılayıcıları sayesinde o bölgedeki atmosfer
bozukluklarının
belirlenmesinde
de
kullanılabilir [5]. Bu örneklerin ortak
özellikleri yerel verilerin eşlerde bulunması
ancak istenilen bilginin bu verilerin
yorumlanmasıyla elde edilebilecek bir sistem
bilgisi olmasıdır. Bunların dışında önbellek
yönetimi, internet solucanlarının ve DOS
ataklarının belirlenmesi, ağ ilinge eniyilemesi
(network
topology
optimization)
gibi
uygulamalara da uyarlanabilir [10].
Bu yöntemde eşlerin hepsine aynı görev
verilir. Özelleşmiş görevlere sahip veya
herhangi bir sıradüzen içerisinde yer alan
eşler bulunmaz. Epidemik yönteme dayalı
algoritmalar devirlerden (round) oluşmaktadır
ve her devirde her eş ya kendinde bulunan
bilgiyi hedeflediği diğer bir kaç eşe bildirir
(push-based) ya da hedeflediği eşlerden
içerikleri hakkında bilgi alırlar (pull-based).
Her ikisinin de tek bir devirde yapılması
da(pull-push based) mümkündür. Algoritma
belirli bir devir sayısına ulaştığı zaman her eş
kendi bilgisini tüm sisteme yaymış olur.
Yöntem ne kadar fazla devirden oluşursa,
bütün bilgilerin tüm sisteme yayılma olasılığı
o kadar artar. Bu yöntem eşlerin sistemden
ayrılmasına veya kopmasına karşı esnek bir
yöntemdir. Bu nedenle görevdeş ağlarda veya
bağlantı kopma oranı yüksek olan kablosuz
ağlarda sık tercih edilen bir yöntemdir.
Epidemik yöntemler işlevselliği açısından üç
gruba ayrılabilir:
Bu bildiri, şu şekilde düzenlenmiştir. 2.
bölümde kümeleme ve sık öğelerin 1. Eşlerin
içeriklerinin
tüm
sisteme
belirlenmesi
konusunda
literaturdeki
dağıtılması
çalışmalardan bahsedilmiştir. 3. Bölümde ise 2. Yinelenmiş verilerin (replicated data)
kendi önerdiğimiz dağıtık yaklaşım anlatılıp
tamir edilmesi
yaklaşımın uygulandığı bir örnek senaryo 3. Kümeleme
gösterilmiştir.
Epidemik yöntemlerin belli başlı yararları
2.Yöntemler
basitliği, ölçeklenebilirliği, hataya karşı
dayanıklılığının yüksek olmasıdır [1]. Bu
2.1 Kümeleme
yöntemde elde edilen sonuçlar sıradüzensel
Kümeleme
işlemi,
toplam,
aritmetik yöntemin aksine olasılıklıdır (probabilistic),
ortalama, minimum, maksimum gibi sistem belirleyici (deterministic) değildir.
geneli bilgilerini belirleme işlemlerine verilen
genel bir isimdir. Kümeleme işlemi sık Bir çok araştırmacı epidemik yönteme dayalı
öğelerin belirlenmesinde önemli bir işlemdir dağıtık kümele işlemi hakkında çalışmalar
çünkü öğelerin sık olup olmaması kararı yapmıştır. Kempe [7] bir ağda dağıtılmış
verilirken kümeleme işleminin sonucu direk olarak bulunan değerlerin epidemik yöntem
olarak kullanılmaktadır. Kümeleme yöntemi ile kümeleme değerlerinin hesaplanması için
ağdaki eşlerin haberleşme türüne göre 2 merkezi olmayan bir yöntem önermiştir.
gruba ayrılabilir.
Örneğin, toplam ve aritmetik ortalama
hesaplamalarını O(log n) devirde ve O(n log
Epidemik (Gossip) Tabanlı Kümeleme
n) mesaj ile gerçekleştiren bir teknik ortaya
koymuştur. Bunun yanı sıra, derecelendirme
(rank)
ve
örnekleme
(sampling)
hesaplamaları da önerilen teknik ile O(log2 n)
devirde ve O(n log2 n) mesaj ile
gerçekleştirilmektedir.
Kashyap
[6]
minimum, maximum, toplam,
aritmetik
ortalma ve derecelendirme(rank) gibi
kümeleme işlemlerini O(n log log n) mesaj
ile ve O(log n log log n) devirde
hesaplayabilen ilk algoritmayı geliştirmiştir.
Boyd [2] ise düzensiz epidemik yönteme
dayalı kümeleme işlemi yapan bir teknik
geliştirmiştir. Bu çalışmaya göre eş i nin
komşusu j ile haberleşmesi ihtimali Pij dir.
Chen [3] kablosuz sensör ağlarda kümeleme
hesaplaması için epidemik yönteme dayalı bir
algoritma geliştirmiştir. Bu algoritmanın
performansının diğer algoritmalara göre daha
iyi olmasına rağmen, algoritmada kablosuz
sensör ağlara has yayım (broadcasting)
yöntemi kullanıldığı için uygulama alanı
kısıtlıdır.
Sıradüzensel Kümeleme
Bu yöntemde eşler arasında bir sıradüzen
oluşturulur. Ancak bu yöntemin en önemli
problemi, sıradüzenin üst katmanlarında yer
alan eşlerden birinin ağdan ayrılması veya
ağdan kopması durumunda hesaplamalarda
büyük kayıplar oluşmasıdır (single point of
failure). Başka bir deyişle, tek bir eşin bile
ağdan ayrılması durumunda çok büyük bir
bilgi kaybına uğraması problemidir. Gossip
yöntemi ile karşılaştırıldığında bu yöntem
ölçeklenirlik açısından geride kalmaktadır.
Li [10] kümeleme bilgisini hesaplamak için
eşler arasında bir sıradüzen oluşturmuştur ve
bu sıradüzenin en üst katmanına ağdaki en
dayanıklı eş konulur. Bu eşin komşuları bir
alt katmanda yer alır. Onların komşuları ise
bir sonraki katmanda yer alır ve bütün eşler
sıradüzene dahil olduğu zaman bu işlem
sonlanmış olur. Bir eşin sıradüzene
katılabilmesi
için
dayanıklı
olarak
nitelendirilmiş olması gerekir. Dayanıklı
olmayan eşler yerel bilgilerini ait oldukları eş
grubunun lideri konumunda olan dayanıklı
eşe iletmekle görevlidir. Bu çalışmada, diğer
çalışmalardan farklı olarak teorik olarak kesin
hata payı olmayan bir çözüm sunulmuştur.
Manjhi [11] de veri akışında sık bulunan
öğeleri belirlerken aynı şekilde bir sıradüzen
oluşturmuştur. Bu sıradüzende bir kaç haberci
(monitor) eş ve bir temel eş bulunmaktadır.
Haberci eşler, kendilerine gelen bilgileri
belirli aralıklarla temel eşe haber verirler.
Temel eş ise gelen bilgileri kullanarak belirli
bir doğruluk payı içerisinde kümeleme
hesaplamasını gerçekleştirir. Keralapura [8]
uzak mevki (remote site) diye adlandırdığı
ağdaki bazı eşlere belirli bir eş grubunun
bilgilerini toplama görevi vermistir. Ağda bir
de eşgüdümcü mevki (coordinator site)
mevcuttur, eşgüdümcü mevki
uzak
mevkilerden, belirli koşullar sağlandığında (
örn. eşik değerinin aşılması) güncel bilgileri
alır. Sıradüzensel yöntemlerin hepsinde de
özelleşmiş bir eşin sistemden ayrılması veya
kopması durumunda önemli bir bilgi kaybı
olacağından, hesapların güvenilirliği ciddi bir
şekilde azalır o yüzden eş giriş çıkışlarının sık
olduğu ağlarda sıradüzensel yöntemin
kullanımı güvenilir olmamaktadır.
2.2 Sık Öğelerin Belirlenmesi
Önceki
çalışmalar
gözönünde
bulundurulduğunda görevdeş ağlarda popüler
öğelerin belirlenmesinde „epidemik‟ yöntem
„sıradüzensel‟ yönteme nazaran daha nadir
kullanılmıştır. Misra ve Gries [13] veri
akışında sık bulunan öğelerin belirlenmesi
konusunda
ilk
belirleyici
çalışmayı
yapmışlardır. Veri akışında n/k den fazla
bulunan öğelerin belirlenmesi için üç tane
algoritma önerisinde bulunmuşlardır. Burada
n veri yapısının büyüklüğü, k ise kullanıcı
tarafından tanımlanan bir parametredir ve
2≤ k ≤ n eşitsizliğini sağlamak zorundalar. Bu
çalışmada ayrıca problemin O(n log k)
zamanda çözülebilmesi için uygun olan veri
yapısının AVL ağaç yapısı olduğunu ve bu
zamanın da bu problem için bir alt sınır
olduğu göstermişlerdir. Manku and Motwani
[12] ise kullanıcı tarafından belirlenen eşik
değerinden
fazla
bulunan
öğelerinin
belirlenmesi için iki farklı algoritma ortaya
koymuşlardır. Bu algoritmalarda öğelerin
yaklaşık sıklık değerleri hesaplanır ve hata
payı kullanıcı tarafından belirlenen bir
parametre ile sınırlanır. Birinci algoritma
yapışkan örnekleme (sticky sampling)
kullanıcı tarafından belirlenen parametreler
ile kontrol edilir. Bu parametreler destek
değeri s , hata oranı ε, ve bozukluk olasılığı
 dır.
hesaplanıyormuş gibi olmaktadır. Sistemde
sık bulunan öğeler listelenirken sıklık değeri
(s-ε)N ve üzerinde olan öğeler seçilir.
Diğer algoritma ise kayıplı sayım (lossy
counting) olarak adlandırılır. Yapışkan
örneklemeden en belirgin farkı, bu
algoritmanın olasılıklı değil deterministik
olmasıdır. Bu algoritmada veri akışı, genişliği
w= ceil(1/e)
olan kovalar kümesi olarak
algılanır. Kullanılan veri yapısı D (e,f,  )
üçlülerinden oluşmaktadır.  , f teki en
büyük hata oranını temsil eder. Toplam
ceil(N/w)
tane kova mevcuttur ve
yürürlükteki kova bcurrent ile temsil edilir.
Algoritma 2-Kayıplı Sayım
Algoritma 1- Yapışkan Örnekleme
Veri akışının uzunluğunun N, kullanılan veri
yapısınn isminin S ve içeriğinin öğe-sıklık
ikililerinden oluştuğunu varsayalım. İlk
olarak S boştur ve örnekleme oranı1 1 dir.
Algoritmada (Algoritma-1) belirtilen r
değerinin
hesaplanması
şu
şekilde
olmaktadır: t= 1/(ε log(s-1δ-1)) olduğunu
varsayalım. İlk 2t öğe için r=1, sonraki 2t öğe
için r=2, sonraki 4t öğe için r=4, ve bu
şekilde devam etmektedir. Bunun dışında,
örnekleme oranında herhangi bir değişiklik
olduğunda her bir öğenin sıklık değeri k
değeri kadar azaltılır, burada k değeri
geometrik dağılıma sahip bir değişkendir. Bu
azaltma işlemi sayesinde öğelerin örnekleme
oranı sanki başından beri o anki r oranı ile
Bu algoritmada kovanın sınırında yer alan 2
öğeler aşağıdaki eşitsizliği sağlıyorsa, o
öğeler silinir.
Manku ve Motwani ayrıca bu problemi tek
bir devirde çözecek bir algoritma da ortaya
koymuşlardır. Ancak, öğelerin dağılımının
çarpık (skewed) olması durumunda algoritma
büyük
hatalar
yapmaktadır.
Önerilen
algoritmalar
verimli
olsada
dağıtık
olmamasından dolayı görevdeş ağlarda
uygulanabilir olduğu söylenemez.
Veri akışlarındaki sık öğelerin belirlenmesi
alanındaki diğer bir çalışma da Manjhi [11]
tarafından yapılmıştır. Bu çalışmada [12] den
farklı olarak, öğeler dağıtık bir sistemde
1
Örnekleme oranının r olması, bir öğenin seçilme
ihtimalinin 1/r olduğu anlamına gelir.
2
Sınırda yer almak N=0 mod w anlamına gelir.
mevcut olduğu için önerilen algoritmanın
görevdeş ağlara uygulanabilirliği vardır.
Çalışmanın amacı sistem genelinde belirli bir
eşik değerinden fazla sıklık değerine sahip
öğelerin kullanıcı tarafından belirlenen
maksimum bir hata payı dahilinde belirli
periyotlar (T) ile belirlenmesidir. T değeri
s*N olarak hesaplanır, s [0,1] değişkeni
kullanıcının belirlediği destek değerini temsil
eder. Sistemde m adet S1 ,S2, ..., Sm veri akımı
olduğunu, ve veri akımı Si nin (oi1, ti1),( oi2,
ti2), gibi öğe-frekans ikililerinden oluştuğunu
varsayalım. Sistemde ayrıca her bir veri
akımını izleyen toplam m adet monitör eşler
olduğunu da varsayalım. Monitör eşler
sistemde bir adet bulunan temel eşi
bilginlendirmek ile görevlidir. Öğelerin sıklık
değeri aşağidaki gibi hesaplanır:
tnow şuanki zamanı temsil ederken,
a
dengelem katsayısının agresifliğini temsil
eder. Bu çalışmanın diğer çalışmalardan farkı,
yakın zamanda görülmüş olan öğelerin sıklık
değeri üzerindeki etkisi daha eski öğelere
göre daha fazla olmasıdır. Bu çalışmada da
eşler arasında sıradüzensel bir yapı
mevcuttur. Temel eş ağacın en tepesinde yer
alırken, onun komşuları bir alt seviyede,
komşularının komşuları ise daha alt seviyede
yer alır. Bütün eşler bu sıradüzene dahil olana
kadar bu yordam devam eder. Bu sıranın en
alt katmanında bulunan düğümler yaprak
düğümler (leaf nodes), orta katmanda yer
alan öğeler ise ara düğümler (intermediate
nodes) olarak adlandırılırlar. Her bir katmana
ait bir hata oranı εi vardır. Sonucun doğru bir
şekilde temel eşe iletilmesi için bu hata
oranının sıradüzenin alt katmanından üst
katmanına doğru azalması gerekmektedir. Bu
yaklaşıma duyarlık meğili
(precision
gradient) adı verilmektedir.
Bir grup çalışma [2,14] eşikli sayımları
dağıtık izleme konusunda bir algoritma
önerisinde bulunmuşlardır. Dağıtımlı izleme
probleminin, sonucun tek bir eşte toplanması
açısından
sık
öğelerin
belirlenmesi
problemine uyarlanması mümkün değildir.
Popüler öğelerin belirlenmesi probleminde
her eşin sistem genelindeki sık öğeleri
bilmesi
gerekir.
Bu özelliğe
sahip
algoritmalar tedbirli (proactive) algoritmalar
olarak adlandırılırken, [8] ve [14] teki
çalışmalarda önerilen algoritmalar tepkili
(reactive)
algoritmalar
olarak
adlandırılmaktadır.
Diğer bir çalışmada [10], görevdeş ağlarda
sık
bulunan
öğelerin
belirlenmesine
sıradüzensel bir yaklaşım ile in-network
filtering adında bir algoritma önerilmektedir.
Bu algoritma 2 aşamadan oluşmaktadır.
Birinci aşama aday süzme (candidate
filtering) olarak adlandırılır ve bu aşamada
eşler arasında gruplar oluşturulur ve bu
gruplarda sık görülen öğeler ilk elemeden
geçerler. İlk elemeden geçen öğeler ikinci
aşama olan aday doğrulama (candidate
verification) aşamasına geçer. Bu aşamada ise
her bir öğenin sıklık değeri, oluşturulan
sıradüzen aracılığı ile hesaplanır ve kulanıcı
tarafından belirlenen eşik değerinin üstünde
sıklık değeri olan öğeler sık öğeler olarak
belirlenir.
Lahiri ve Tirthapura [9] bu alanda epidemik
yöntemi kullanan tek çalışmayı yapmışlardır.
Bu çalışmada „birörnek (uniform) epidemik
algoritma kullanılmıştır ve ağdaki her bir eşin
sadece bir öğe bulundurabileceği baz
alınmıştır.
Bu
durum
algoritmanın
uygulanabilirliğini azaltmaktadır.
3. Önerdiğimiz Dağıtık Yaklaşım
N eşten oluşan tasarsız bağlantılı (connected)
bir görevdeş ağın olduğunu varsayalım ve
ağdaki eşleri
P={P1, P2,...,PN}
kümesi olarak, öğeleri ise
D={d1, d2, d3,..., dt}
kümesi ile adlandıralım. Burada t değeri tüm
ağda kaç farklı öğe olduğunu gösterir. Her bir
öğenin
sistem
genelinde
kaç
adet
bulunduğunu ise g(di), i={1,2,...,t} olarak
gösterelim. Ayrıca Pj‟nin öğe içeriğini de
Sj={sj1, sj2,..., sjm,..., sjk } olarak gösterelim,
burada k değeri, o eşte kaç tane farklı öğe
bulunduğunu gösterir ve Sj  D dir. Eş j‟de
bulunan herhangi bir öğenin, sm olduğunu
varsayalım, yerel sıklık değerini v(sjm) ve
tanımlayıcısını da id(sjm) olarak gösterelim.
Bu durumda öğelerin sıklık değerleri şu
şekilde yazılabilir.
N
g (d i )   v( s ji ), i  {1,2,..., t}
j 1
Elde etmeye çalıştığımız sonuç, algoritma
sonucunda her eşin, sistem genelindeki tüm
öğelerin sayısını( g(di) , i={1,2,...,t} )
hesaplamış olmasıdır. Çünkü, amacımız tek
bir eşin değil, her eşin sistemdeki sık öğeleri
tespit edebilmesidir. Sık öğeyi tanımlarken de
bir eşik değeri belirlenmesi gerekir. Bu eşik
değerini T olarak gösterelim. Buna göre
sistemdeki
sık
öğeleri
şu
şekilde
tanımlayabiliriz:
F (t )  {d i g (d i )  T } ,
i  {1,2,..., t}
Önerdiğimiz yöntemin diğer çalışmalardan en
önemli farkı sık öğelerin tanımında öğenin
sıklık değerini değil, onun sistem genelindeki
ortalamasını temel almamızdır.
Bunun
nedeni ise epidemik yöntemde eşler arası
haberleşme
belirli
bir
hiyerarşiye
dayanmadığından dolayı, aynı eşler birden
fazla haberleşmiş olabilirler. Bu durumda her
eşin yerel değerlerini toplayarak onların
sistem genelindeki sıklık değerini elde
etmemiz
mümkün
değildir.
Bizim
önerdiğimiz yaklaşımda sık öğeler şu şekilde
tanımlanır:
F (t )  {d i ga(d i )  } i  {1,2,..., t}
ga(d i ) 

g (d i ) 1

N
N
N
 v( s
j 1
ji
)
T
N
Burada ek olarak hesaplamamız gereken
sistemde kaç tane eş bulunduğunun tahmin
edilmesidir.Ancak, bu hesaplama da herhangi
bir öğenin sistem genelindeki sıklık değerinin
hesaplanmasıyla paralel olduğu için ayrı bir
işlem gerektirmeyecektir. Tek yapılması
gereken, sistemdeki eşlerden her birine aynı
öğeden ekleyip o öğenin sıklık değerini tek
bir eş hariç sıfıra eşitlemek, tek eşte (başlatıcı
eş) ise 1 e eşitlemek olacaktır. Böylelikle, bu
eklediğimiz öğenin sistem genelindeki
ortalamasını hesapladığımızda 1/N değerine
yaklaşacağız.
Algoritmanın İşleyişi
Önerdiğimiz algoritma belirli periyotlarda
eşlerin
birbiri
ile
haberleşmesine
dayanmaktadır. Her bir periyotta, eşler
komşuları arasından rastgele haberleşeceği
eşi seçer ve kendi içeriğini gönderir. Bu
içeriği alan eş, gelen her öğeye bakar. Eğer
bir öğe kendinde bulunmuyorsa o öğeyi sıklık
değerini sıfıra eşitleyip içeriğine ekler. Daha
sonra öğenin kendisindeki ve öğeyi aldığı
eşteki değerlerin ortalmasını hesaplayıp kendi
içeriğine kaydeder. İçeriğini güncelleyen eş,
sadece o periyotta güncellemiş olduğu içeriği
geri
gönderir.
Her
eş
bu işlemi
gerçekleştirdikten
sonra
ilk
periyot
tamamlanmış olur. Sistem genelinde her
öğenin sıklık değeri korunduğu için ve de her
eşte belli bir periyottan sonra aynı değere
yakınsayacağı için, bu değer o öğenin
ortalaması olacaktır.
Bu yaklaşımı
açıklamaka için herhangi bir öğenin her
eşteki yerel sıklık değerlerinin ilk durumunu
düşünelim. Bu değerlerden en büyüğü ile en
küçüğünün değeri Vmin, Vmax olsun. Vmin yerel
sıklık değerini içeren eş ilk periyottan sonra
Vmin değerini Vmin den daha büyük bir değerle
değiştirecektir, çünkü kendisinden daha
büyük bir değerle ortalamasını hesaplayıp
içeriğine kaydedecektir. Aynı şekilde Vmax
değeri de her periyotta azalacaktır. Bir öğenin
eşlerdeki sıklık değerleri Vmin ile Vmax arasında
olduğu için ve bu değerler gittikçe birbirine
yaklaştığı için, en sonunda tüm eşlerdeki
değerler
gerçek
ortalama
değere
yakınsayacaktır.
Örnek Senaryo
Ağımızda üç eş olduğunu varsayalım ve
herbirinin diğer iki eşle komşu olduğunu
varsayalım (tam çizge). Başlangıç içerikleri
de şöyle olsun:
S1
S2
S3
Toplam
{(id1, 2),(id2, 7)}
{(id1, 4)}
{(id1, 4)}
{(id1, 10), (id2, 7)}
Eşlerin başlangıç içerikleri
Eşik değerinin de 8 olduğunu varsayalım.
Algoritmanın sık öğe olarak sadece id1
öğesini dönmesi gerekir.
XY : X eşinin içeriğini paylaşmak için Y
eşini seçtiği anlamına gelir.
1.Periyot
Başlatıcı eş: P1
S1S2, S3S1, S2S1 olduğunu varsayalım.
Bu durumda
S1={(id1, 2),(id2, 7),(id, 1)}
S2={(id1, 4), (id, 0)}
S1S2 sonucunda
S1={(id1, (2+4)/2),(id2, (0+7)/2),(id, 0.5) }
S2={(id1, (2+4)/2),(id2, (0+7)/2),(id, 0.5)}
Step1
S3={(id1, 4),(id, 0)}
S1={(id1, 3),(id2, 3.5),(id, 0.5)}
S3S1 sonucunda
S2={(id1, 3),(id2, 3.5),(id, 0.5)}
S1={(id1, 3.5),(id2, 3.5),(id, 0.25)}
S2S1 sonucunda
S2={(id1, 3.25),(id2, 3.5),(id, 0.375)}
S1={(id1, 3.25),(id2, 3.5),(id, 0.375)}
Step3
İlk periyot sonunda eşlerdeki içerik şu şekilde
olur:
S1
{(id1, 3.25),(id2, 3.5),(id, 0.375)}
S2
{(id1, 3.25), (id2, 3.5),(id, 0.375)}
S3
{(id1, 3.5), (id, 0.25)}
Top
{(id1, 10), (id2, 7), ((id, 1))}
Birinci periyot sonunda içerikler
Tabloda görüldüğü gibi, öğelerin yerel sıklık
değerleri değişmesine rağmen, toplam
satırındaki öğelerin sistem genelindeki sıklık
değerlerinde
herhangi
bir
değişiklik
gözlemlenmemiştir.
Bu
durum
bize
yakınsanan değerinin öğelerin ortalama
değeri olduğunu göstermektedir.
Birinci periyot sonunda her bir eşe sık
öğelerin listesini sorduğumuzda aldığımız
cevaplar ise şöyle olacaktır:
S1 için
S2 için
S3 için
 =8*0.375=3, F={id1,id2}
 =8*0.375=3, F={id1,id2}
 =8*0.25=2, F={id1}
2. Periyot
S1S3, S2S1, S3S2 olduğunu varsayalım.
Bu durumda, 2. Periyot sonunda eşlerin
içeriği şu şekilde olacaktır.
S3={(id1, 3.5),(id, 0.25)}
S1
{(id1, 3.3125),(id2, 2.625),(id, 0.34375)}
S1={(id1, 3.5),(id2, 3.5),(id, 0.25)}
S2
{(id1, 3.34375), (id2, 2.1875),(id, 0.328125)}
S3
{(id1, 3.34375), (id2, 2.1875),(id, 0.328125)}
Top
{(id1, 10), (id2, 7), ((id, 1))}
Step2
İkinci periyot sonunda içerikler
Birinci periyot sonunda her bir eşe sık
öğelerin listesini sorduğumuzda aldığımız
cevaplar ise şöyle olacaktır:
S1 için
S2 için
S3 için
 =8*0.34375=2.75, F={id1}
 =8*0.328125=2.625, F={id1}
 =8*0.328125=2.625, F={id1}
Sonuç olarak her bir eş dağıtık yaklaşım ile
sistem genelinde sık bulunan öğenin id1
olduğuna karar verdi. Sistem geneline
baktığımız zaman sıklık değeri eşik değerinin
üstünde olan tek öğenin id1 olduğu da
görülmektedir.
4. Sonuç
Bu çalışmada, görevdeş ağlarda popüler
öğelerin
belirlenmesinin
öneminden,
uygulama alanlarından ve literatürde bu
konudaki önemli çalışmalardan bahsettik. Bu
çalışmaların bir özetini yapıp, pozitif ve
negatif yönlerini belirleyip, birbirleri ile
karşılaştırdık. Ayrıca, görevdeş ağlarda
popüler öğelerin belirlenmesinde epidemik
tabanlı dağıtık bir çözüm önerisinde
bulunduk. Önceki çalışmalardan farklı olarak,
bu yaklaşım sık öğelerin belirlenmesinde
ortalama fonksiyonunu kullanarak tamamen
dağıtık şekilde ilerlemektedir. Sistem
modelinin P2P ağ benzetim (PeerSim) ve test
(PlanetLab)
platformları
üzerinde
geliştirilmesi, konunun enerji verimliliği
boyutunun dikkate alınması ve literatürdeki
diğer çözümlerle başarım karşılaştırması
hedeflenmektedir.
5.Kaynaklar
[1] Birman, K., “The promise, and
limitations, of gossip protocols”, Operating
Systems Review, vol. 41, no. 5, pp. 8–13,
2007.
[2] Boyd, S. P., Ghosh, A., Prabhakar, B. and
Shah, D., “Gossip algorithms: design,
analysis and applications”, INFOCOM,
2005, pp. 1653–1664.
[3] Chen, J.-Y., Pandurangan, G. and Xu, D.,
“Robust computation of aggregates in
wireless sensor networks: Distributed
randomized algorithms and analysis”, IEEE
Trans. Parallel Distrib. Syst., vol. 17, no. 9,
pp. 987–1000, 2006.
[4] Chitnis, L., Dobra, A., Ranka, S.,
“Aggregation methods for large-scale sensor
networks”, ACM Transactions on Sensor
Networks (TOSN), v.4 n.2, p.1-36, March
2008
[5] Jelasity, M., Montresor, A., Babaoglu, O.,
“Gossip-based aggregation in large dynamic
networks”,
ACM
Transactions
on
Computer Systems (TOCS), v.23 n.3,
p.219-252, August 2005
[6] Kashyap, S., Deb, S., Naidu, K., Rastogi,
R., and Srinivasan, A., “Efficient gossipbased aggregate computation.”, Proceedings
of ACM SIGMOD-SIGACT-SIGART
Symposium on Principles of Database
Systems (PODS), June 2006.
[7] Kempe, D., Dobra, A., and Gehrke, J.,
“Gossip-based computation of aggregate
information”, Proceedings of Symposium on
Foundations of Computer Science (FOCS),
pages 482–491, October 2003.
[8] Keralapura, R., Cormode, G., and
Ramamirtham, J., “Communication-efficient
distributed monitoring of thresholded
counts”, SIGMOD Conference, June 2006,
pp. 289–300.
[9] Lahiri, B. and Tirthapura, S., “Computing
frequent elements using gossip”, SIROCCO,
2008, pp. 119–130.
[10] Li, M. and Lee, W.-C., “Identifying
frequent items in peer-to-peer systems.”,
Pennsylvania State University Technical
report, July 2006.
[11]
Manjhi,
A.,
Shkapenyuk,
V.,
Dhamdhere, K. and Olston, C., “Finding
(recently) frequent items in distributed data
streams”,
Proc. of International
Conference on Data Engineering (ICDE),
Apr. 2005, pp. 767–778.
[12] Manku, G.S. and Motwani, R.,
“Approximate frequency counts over data
streams”, VLDB, 2002, pp. 346–357.
[13] Misra, J. and Gries, D., “Finding
repeated elements”, Sci. Comput. Program.,
vol. 2, no. 2, pp. 143–152, 1982.
[14] Olston, C., Jiang, J. and Widom, J.,
“Adaptive filters for continuous queries over
distributed
data
streams”,
SIGMOD
Conference, 2003, pp. 563–574.