Tez No	İndirme	Tez Künye	Durumu
531407		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 Yazar:CAN UMUT İLERİ Danışman: DOÇ. DR. ORHAN DAĞDEVİREN Yer Bilgisi: Ege Üniversitesi / Fen Bilimleri Enstitüsü / Uluslararası Bilgisayar Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2018 177 s.
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.
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.