Distributed and self-stabilizing algorithms for capacitated graph theory problems
Kapasite kısıtlı çizge teorisi problemleri içindağıtık ve öz-kararlı algoritmalar
- Tez No: 531407
- Danışmanlar: DOÇ. DR. ORHAN DAĞDEVİREN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2018
- Dil: İngilizce
- Üniversite: Ege Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Uluslararası Bilgisayar Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 177
Özet
Bir dağıtık sistemi oluşturan birimlerden birinde ya da bu birimlerin birbirleriyle iletişim kurdukları bağlantıda bir hatanın meydana gelmesi, sistemin çalışmasında istenmeyen etkiler oluşturabilir. Dağıtık algoritmaların doğası gereği işlem birimlerinin sınırlı (yerel) bilgiye sahip olmaları ve hesaplama kuvveti yönünden birbirlerinden bağımsız olmaları, söz konusu hataların tespit edilip çözülmesini zorlaştırır. Hatayı sistemin kullanıcısının gözlemlemesini önleyecek şekilde örtmeyi hedefleyen hata-toleranslı mekanizmalar hesaplama kaynakları yönünden oldukça masraflıdır. Öte yandan, birimlerin istenmeyen davranışının belirli bir süre için kabul edilebildiği sistemlerde, sistemin öngörülebilir bir süre içinde hatasız ve istenen bir konfigürasyona ulaşması garanti ediliyorsa, hatayı gizleme koşulu esnetilebilir. Öz-kararlılık, önemli bir maskelemesiz hata toleransı kavramıdır. Bir özkararlı algoritma, sistemin istenmeyen bir konfigürasyonda bulunması halinde etkinleştirilip çalıştırılan ve nihayetinde sistemi hiçbir kuralın aktif olmadığı öz-kararlı olarak adlandırılan bir konfigürasyona ulaştıran bir dizi kuraldan oluşur. Bu tez, bazı kapasite kısıtlı çizge teorisi problemleri için geliştirilmiş olan öz-kararlı algoritmalardan oluşur. Klasik çizge teorisi problemlerinin gerçek dünya uygulamaları genelde kapasite kısıtı içermesine rağmen bu problemlerin kapasite kısıtlı versiyonları öz-kararlılık literatüründe hak ettiği kadar dikkat çekmemiştir. Biz bu çalış- mada problemlerin kapasite kısıtlı versiyonlarına odaklanıyoruz. Özellikle kapasite kısıtlı eşleme (b-eşleme), kapasite kısıtlı en küçük kapsayan ağaç ve kapasite kısıtlı çizge bölme problemleriyle ilgilenip bu problemler için özgün öz-kararlı algoritmalar öneriyoruz. Ayrıca bu algoritmaların doğruluk, kapalılık ve yakınsama özelliklerini ispatlıyoruz.
Özet (Çeviri)
Failure of a single element or of a communication medium between more than one elements of a distributed system result in undesired activities toward the common goal of the network. As a nature of distributed algorithms, since the processing elements only have limited (local) information and are independent from each other with respect to the computational powers, these failures are difficult to detect and resolve. Fault tolerant mechanisms which aim at masking the failure so that the fault is not observable to the users of the system are costly in terms of computational resources. On the other hand, the masking constraint can be relaxed in such systems where an undesired behavior of the system is tolerable for a limited time, given that the system is guaranteed to reach a non-faulty and desired state in a foreseeable time. Self stabilization is an important non-masking fault tolerant concept. A self-stabilizing algorithm is a set of rules which are activated and executed in case of an adversarial configuration of the system in such a way that the system eventually reaches a desired configuration in which none of the rules are activated, i.e., system is stabilized. This thesis is a collection of new self-stabilizing algorithms for some of the classical graph theoretical problems. We focus on the capacitated versions of these problems which have not attracted the attention they deserve from the fault tolerance field, even though their real world applications generally come with their own capacity restrictions. We particularly deal with and propose novel self-stabilizing algorithms for capacitated matching (b-matching), capacitated minimum spanning tree (CMST) and capacitated k-way graph partitioning problems. We give formal proofs for the correctness, convergence and closure of this algorithms.
Benzer Tezler
- A study on the algorithms for capacitated domination problems
Kapasite kısıtlı hakimiyet problemleri için algoritmalar üzerine bir çalışma
ÖZKAN ARAPOĞLU
Doktora
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı
DOÇ. DR. ORHAN DAĞDEVİREN
- Telsiz duyarga ağları için hakim küme algoritmaları
Dominating set algorithms for wireless sensor networks
ÖZKAN ARAPOĞLU
Yüksek Lisans
Türkçe
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı
DOÇ. DR. ORHAN DAĞDEVİREN
- Découverte et allocation des ressources pour le traitement de requêtes dans les systèmes grilles
Başlık çevirisi yok
DENİZ ÇOKUSLU
Doktora
İngilizce
2012
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolUniversité Toulouse III Paul SabatierPROF. KAYHAN ERCİYES
PROF. ABDELKADER HAMEURLAİN
- Nesnelerin interneti tabanlı öz-kararlı çok zıplamalı akıllı termostat
An internet of things based self-stabilizing multi-hop smart thermostat
LEVENT ÖZGÜR
Yüksek Lisans
Türkçe
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı
DOÇ. DR. ORHAN DAĞDEVİREN
- A study on self-stabilizing dominating set algorithms
Dağıtık öz-kararlı hakim küme algoritmaları üzerine bir çalışma
HÜSEYİN TOLGA EVCİMEN
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiUluslararası Bilgisayar Ana Bilim Dalı
DOÇ. DR. ORHAN DAĞDEVİREN