SGLC: A logical clock using succinct graphs
SGLC: Öz çizge gösterimleri ile bir mantıksal saat
- Tez No: 749580
- Danışmanlar: PROF. DR. ERTAN ONUR
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 72
Özet
Bu tez, dağıtık sistemlerde nedensellik ilişkilerini yakalayabilen yeni bir mantıksal saat olan SGLC'yi sunmaktadır. SGLC, grafları tamsayı olarak depolarken polinom zamanda kodlanabilen ve çözülebilen özlü bir grafik gösterimine dayanır. SGLC'yi uygulanabilir kılan şey, yönlendirilmiş grafların mantıksal saatleri uygulamak için kullanılabilmesidir. Sonuç olarak, SGLC'yi tanıtmanın temel amacı, olayların nedensellik ilişkilerini alıcı süreçte kodu çözülen grafikler olarak kapsülleyerek nedensel geçmiş grafiklerinin taşınmasının iletişim yükünü azaltmaktır. Yeni protokolü bir ad hoc hesaplama çerçevesinde uyguladık ve en köklü mantıksal saat türü olan vektör saati ile karşılaştıran kapsamlı bir kıyaslama kampanyası yürüttük. Buna ek olarak, önerilen saatin iletişim yükünü ve genel depolama karmaşıklığını daha da azaltmanın diğer yollarını değerlendirdik. Son olarak, SGLC'nin iki dağıtık algoritmada uygulanmasını da inceledik. SGLC'nin çıplak uygulaması üzerinde yapılan deneylerden elde edilen sonuçlar, vektör saatine kıyasla değiş tokuş edilen toplam bitler açısından 100 olay ve 32 işlem sınırı için %85'e varan bir azalma elde edilebileceğini göstermektedir. SGLC'ye daha fazla optimizasyon uygulamak, aynı sayıda olay için %63'lük bir azalma ile sonuçlanabilir.
Özet (Çeviri)
This thesis presents a new logical clock, SGLC, capable of capturing causality relationships in distributed systems. SGLC relies on a succinct graph representation codable and decodable in polynomial time while storing the graphs as integers. What makes SGLC feasible is that directed graphs can be used to implement logical clocks. Consequently, the main goal of introducing SGLC is to reduce the communication overhead of transporting causal history graphs by encapsulating the causality relationships of events as graphs that are decoded at the receiving process. We implemented the new protocol in an ad hoc computing framework and conducted an extensive benchmarking campaign comparing it with the vector clock, which is the most well-established type of logical clock. In addition, we evaluated other ways of further reducing the communication overhead and the overall storage complexity of the proposed clock. Finally, we also studied the application of SGLC in two distributed algorithms. Results obtained from experiments performed on the bare implementation of SGLC show that a reduction of up to 85% is attainable for a limit of 100 events and 32 processes in terms of overall bits exchanged compared to the vector clock. Applying further optimizations to SGLC can result in a further reduction of 63% for the same number of events.
Benzer Tezler
- Sürekliliğin topolojik uzaylarda ayrışımı ve ?-I? irresolute fonksiyonlar
Decomposition of continuity in topological spaces and ?-I?-irresolute functions
ALİ HAYDAR KOCAMAN
- Topolojik ve ideal topolojik uzaylarda süreklilik ve uzay çeşitleri üzerine bir çalışma
A study on types of continuity and space in topological and ideal topological spaces
ESER GÜRSEL ÇAYLAK
- Topolojide bazı genelleştirilmiş sürekli fonksiyonlar
Some generalized continuous functions in topology
CENGİZ FİDANCI
Yüksek Lisans
Türkçe
2006
MatematikSelçuk ÜniversitesiMatematik Ana Bilim Dalı
YRD. DOÇ. DR. YUSUF BECEREN
- Topolojide bazı genelleştirilmiş kapalı kümeler
Some generalized closed sets in topolgy
KENAN ARSLAN
Yüksek Lisans
Türkçe
2006
MatematikSelçuk ÜniversitesiMatematik Ana Bilim Dalı
YRD. DOÇ. DR. YUSUF BECEREN