Tag Archives: step-by-step

Il problema del consenso distribuito: l’algoritmo Paxos, step-by-step

Nei sistemi distribuiti, una serie di macchine sono in grado di raggiungere un consenso su una decisione che è estremamente importante. I sistemi di database, ad esempio, devono assicurare che tutte le macchine siano d’accorso se effettuare un commit o il rollback di una transazione, in modo che ogni macchina abbia una visione coerente dei dati (si immagini ad esempio il problema sul proprio conto bancario. Una macchina pensa che tu abbia 1000 euro sul tuo conto, ma un’altra macchina crede che tu abbia il conto vuoto).

Il consenso è difficile da raggiungere, perché i messaggi tra le macchine possono essere persi o ritardati in modo indefinito, oppure le macchine stesse possono fallire – come fa una macchina a sapere se un’altra macchina ha elaborato un messaggio?

Solitamente si utilizza il Commit a due fasi (Two-phase commit), ma ha un problema – se il nodo coordinatore di una transazione fallisce, il sistema rimane bloccato fino a quando questo nodo non si riavvia. Il commit a tre fasi risolve questo problema del blocco, ma fa sempre affidamento su un unico coordinatore.

In questo articolo, si discute Paxos, un protocollo distribuito alternativo al commit a due fasi e a quello a tre fasi. Paxos garantisce che i nodi sceglieranno sempre e solo un singolo valore (quindi garantisce la safety), ma non garantisce che un valore verrà scelto se la maggioranza dei nodi non sono disponibili (progress). Gli algoritmi di consenso hanno come obiettivo la safety, perché non importa se si faccia un commit o un rollback – ma è di fondamentale importanza che una sola risposta sia scelta.

Continue reading Il problema del consenso distribuito: l’algoritmo Paxos, step-by-step

Recursive Quicksort Algorithm written in C language [with example step-by-step]

Quicksort is a sorting algorithm developed by C. A. R. Hoare that, on average, makes O(nlogn) (big O notation) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other O(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices that minimize the probability of requiring quadratic time. Additionally, quicksort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Although quicksort is usually not implemented as an in-place sort, it is possible to create such an implementation.
Quicksort (also known as “partition-exchange sort”) is a comparison sort and, in efficient implementations, is not a stable sort.
Continue reading Recursive Quicksort Algorithm written in C language [with example step-by-step]

Bubblesort written in C with example step-by-step

Source code of sorting algorithm “bubblesort” written in C. Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements “bubble” to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.

Step-by-step example
Let us take the array of numbers “5 1 4 2 8”, and sort the array from lowest number to greatest number using bubble sort algorithm. In each step, elements written in bold are being compared.

– First Pass:
( 5 1 4 2 8 ) ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps them.
( 1 5 4 2 8 ) ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.
– Second Pass:
( 1 4 2 5 8 ) ( 1 4 2 5 8 )
( 1 4 2 5 8 ) ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.
Third Pass:
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
( 1 2 4 5 8 ) ( 1 2 4 5 8 )
Finally, the array is sorted, and the algorithm can terminate.

Source Code in C:


// © Codeido - www.codeido.com - Developed by Paolo Musolino

#include <stdio.h>

void swap(int *a, int *b)
{	
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
	
	
}
//---------------//---------------//---------------
int confronto(int x, int y)
{
	if(x<y) return -1;
	else if(x>y) return 1;
	else {
		return 0;
	}
	
}

void bubbleSort(int a[], int n)
{
	int i, j;
	for (i=0; i<n-1; i++) 
	{
		for (j=n-1; j>i; j--) 
		{
			if (confronto(a[j], a[j-1])<0) 
			
				swap(&a[j], &a[j-1]);
			
		}
	}
}


//Main Function
int main ()
{
	int a[14]={5, 10, 11, 9, 7, 8, 4, 5, 7, 2, 45, 1, 4, 20};
	int i;
	bubbleSort(a, 14);
	printf("\n");
	for (i=0; i<14; i++) {
		printf("%d ", a[i]);
	}
	
	
	return 0;
}

[retweet]